Алгебраическая теория графов

Основная часть модуля посвящена базовым определениям и понятиям теории графов и теории групп. Вы также узнаете про историю развития этих математических дисциплин и о том, какие задачи лежали в их основе. Кроме того, вы научитесь решать задачи о перекладывании блинчиков и о сборке кубика Рубика. А ещё вы узнаете про задачу поиска пути в лабиринте, которую решил Эдвард Мур, и про целый класс графов Мура.

В этом модуле вы узнаете, что графы можно найти абсолютно везде: например, в социальных сетях, в поисковых системах или в теории шести рукопожатий. Это значит, что множество вопросов можно перевести на язык графов. А там где графы, там и их матрицы — это и есть основа алгебраической теории графов. Мы сфокусируемся на матрицах смежности графов и их спектрах. Вы научитесь слышать, что говорят собственные числа графов и видеть, в каких свойствах графов они себя проявляют. Вы познакомитесь с такими важными классами графов, как сильно регулярные и дистанционно регулярные, узнаете, как операции на графах меняют их спектры. Эти классы графов применяются в теории кодирования, теории комбинаторных дизайнов, квантовой теории информации и даже в финансовой сфере. Кроме того, вы овладеете различными приёмами, как находить спектры графов, не вычисляя корни характеристических полиномов. А ещё вы познакомитесь со славной традицией использовать граф Петерсена в качестве примера или контрпримера.

Этот модуль посвящен связи между графами и группами. Вы узнаете, как возникают автоморфизмы на множествах вершин и ребёр, как транзитивность графов связана с их регулярностью, всякие ли вершинно-транзитивные графы являются графами Кэли, как графы Кэли возникают в других областях знаний. Например, они активно используются в теории межкоммуникационных сетей. Мы также расскажем о том, как Ричард Хэмминг придумал первый компьютерный код с автоматическим исправлением ошибки и метрику, на основе которой строится целый класс графов.

На 4-ой неделе нашего курса научитесь решать прикладные задачи, в которых применение спектральной теории графов даёт неожиданные результаты. Например, современные исследования в квантовой химии показывают удивительные связи между структурой химического соединения и спектральными свойствами его молекулярного графа. Вы узнаете, что собственные числа имеют даже конкретный физический смысл на примере музыкальных барабанов. Помимо этого вы увидите, как с помощью собственных чисел и векторов можно рисовать картинки, определять чемпионов в турнирах и доказывать какие-то свойства графов, даже не зная, как именно он выглядит. И хотя главным действующим лицом четвёртого модуля будет уже матрица Лапласа, мы всё же не забудем про матрицу смежности и поговорим о связи коэффициентов её характеристического полинома с локальной структурой графа. Вы узнаете, как переплетаются между собой собственные числа графа и его индуцированных подграфов.