City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Spectral graph theory


Спектральная теория графов позволяет судить о свойствах графа по свойствам связанных с ним матриц (смежности, лапласиана, инцидентности). Дело в том, что у неориентированного графа матрица смежности и лапласиан симметричны, то есть для них существуют полные наборы вещественных собственных чисел.

Мы обсудим наиболее известные математические (сильно регулярные графы, количество остовных деревьев, экспандеры, связь с паросочетаниями) и компьютерные (рисование планарных графов, Google page rank, экспандеры) сюжеты.

Course Offerings

Semester Branch
spring 2018 Saint Petersburg