UPD! ЧТОБЫ ПОЛУЧИТЬ ОЦЕНКУ ЗА КУРС НАДО ДОГОВОРИТЬСЯ СО МНОЙ И С А. КУЛИКОВЫМ. если Вы решите все (два) домашних задания целиком, это гарантирует Вам 5, если каждое наполовину --- то три.
Спектральная теория графов позволяет судить о свойствах графа по свойствам связанных с ним матриц (смежности, лапласиана, инцидентности). Дело в том, что у неориентированного графа матрица смежности и лапласиан симметричны, то есть для них существуют полные наборы вещественных собственных чисел.
Мы обсудим наиболее известные математические (сильно регулярные графы, количество остовных деревьев, экспандеры, связь с паросочетаниями) и компьютерные (рисование планарных графов, Google page rank, экспандеры) сюжеты.
| Дата и время | Занятие | Место | Материалы |
|---|---|---|---|
| 18 марта 11:15–12:45 |
Лекция 1. Введение, Лекция | ПОМИ РАН | видео |
| 18 марта 13:00–14:30 |
Лекция 2. Теорема Куранта -- Фишера, раскраски графов, Лекция | ПОМИ РАН | видео |
| 25 марта 11:15–12:45 |
Лекция 3. Вокруг формулы Хоффмана, Лекция | ПОМИ РАН | видео |
| 25 марта 13:00–14:30 |
Лекция 4. Кнезеровский граф., Лекция | ПОМИ РАН | видео |
| 15 апреля 11:15–12:45 |
Лекция 5, стабильность в теореме Эрдёша -- Ко -- Радо, Лекция | ПОМИ РАН | видео |
| 15 апреля 13:00–14:30 |
Лекция 6, неравенство Чигера., Лекция | ПОМИ РАН | видео |
| 22 апреля 11:15–12:45 |
Лекция 7. Рисование планарных графов. Google page rank., Лекция | ПОМИ РАН | видео |
| 22 апреля 13:00–14:30 |
Лекция 8. Экспандеры., Лекция | ПОМИ РАН | видео |
