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

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

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

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

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

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

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

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

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

Продолжаем погружение в исследования современной математики и знакомимся с наиболее продвинутым модулем этого курса. Основной объект исследования в этом модуле — Star граф — наиболее изучен в теории межкоммуникационных сетей. На его примере вы увидите связь между спектральной теорией и теорией представлений конечных групп. Научитесь работать со стандартными таблицами Юнга, представлением симметрической группы, элементами Юциса — Мёрфи, спектром Star графа и поймёте, как вычислять кратности собственных значений.

• 1. Star граф и его основные свойства
  2. Перестановки и их классы сопряжённости
  3. Разбиения, цикловой тип перестановок и таблицы Юнга
  4. Представление конечной группы
  5. Представление симметрической группы через элементы Юциса — Мёрфи
  6. Элементы Юциса — Мёрфи и спектр Star графа
  7. Формула крюка и кратности собственных значений

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

• 1. Отношения как разбиения
  2. Схемы отношений на языке графов
  3. Через мир матриц к дистанционно регулярным графам
  4. Алгебра Боуза — Меснера
  5. Параметры Крейна, P- и Q-полиномиальность
  6. Возвращение к графу Мура на 3250 вершинах
  7. Когерентные конфигурации как обобщение схем отношений
  8. Алгебраическая теория графов: что дальше?