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

Spectral graph theory
Saint Petersburg / spring 2018, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

UPD! ЧТОБЫ ПОЛУЧИТЬ ОЦЕНКУ ЗА КУРС НАДО ДОГОВОРИТЬСЯ СО МНОЙ И С А. КУЛИКОВЫМ. если Вы решите все (два) домашних задания целиком, это гарантирует Вам 5, если каждое наполовину --- то три.

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

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