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

Содержание курса

Каждый модуль курса посвящён отдельному разделу теории графов и проиллюстрирован примерами их практического применения в разных сферах. Модули завершаются упражнениями для отработки навыков. Материалы курса разработала группа исследователей Математического центра в Академгородке (соглашение с Министерством науки и высшего образования РФ № 075−15−2019−1675)

• 6 модулей
• 6 тем
• 12 часов

• Основы алгебраической теории графов

  Основная часть модуля посвящена базовым определениям и понятиям теории графов и теории групп. Вы также узнаете об истории развития этих математических дисциплин и о том, какие задачи лежали в их основе. 

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

  • Вводное видео. О чём этот курс и как он устроен.
  • Историческое развитие алгебраической теории графов.
  • Базовые понятия теории графов.
  • Дистанционно-регулярные графы.
  • Графы Мура.
  • Основы теории групп.
  • Блинчиковый граф и биокомпьютер.
  • Кубик Рубика.

• Графы и матрицы

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

  Мы сфокусируемся на матрицах смежности графов и их спектрах. Вы научитесь слышать, что говорят собственные числа графов, и видеть, в каких свойствах они себя проявляют. 

  Познакомитесь с такими важными классами, как сильно регулярные и дистанционно-регулярные графы. Узнаете, как операции на графах меняют их спектры. Эти классы графов применяются в теории кодирования, теории комбинаторных дизайнов, квантовой теории информации и даже в финансовой сфере. 

  Кроме того, вы овладеете различными приёмами поиска спектров графов без вычисления корней характеристических полиномов. А ещё познакомитесь со славной традицией использовать граф Петерсена в качестве примера или контрпримера.

  • Что линейная алгебра говорит о графах.
  • Собственные числа и векторы графов.
  • Спектры некоторых графов.
  • Спектры после операций над графами.
  • Сильно регулярные графы.
  • Дистанционно-регулярные графы.
  • Практикум: считаем спектры.

• Графы и группы

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

  Мы также расскажем о том, как Ричард Хэмминг придумал первый компьютерный код с автоматическим исправлением ошибки и метрику, на основе которой строится целый класс графов.

  • Группа автоморфизмов графа.
  • Транзитивные и симметричные графы.
  • Дистанционно-транзитивные графы.
  • Графы Кэли.
  • Схематическая связь между регулярными и транзитивными графами.
  • Граф Хэмминга: дистанционно-транзитивный граф Кэли.
  • Графы Джонсона: дистанционно-транзитивный граф, но не всегда граф Кэли.

• Спектральная теория графов

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

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

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

  • Алгебраическая теория графов в примерах.
  • Матрица Лапласа.
  • Спектральная визуализация и кластеризация.
  • Теорема Перрона — Фробениуса и задача ранжирования.
  • Характеристический полином и изоспектральные графы.
  • О сплетении/чередовании собственных значений.
  • Граница весового распределения и о чём ещё говорят графы.