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

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

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

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


Для кого этот курс:
- для студентов математических специальностей;
- для специалистов в сфере IT;
- для студентов факультетов естественных наук: химиков, биологов, физиков, геологов, инженеров;
- для всех, кому интересна математика и кто хочет развивать математическое мышление и логику

Материалы курса разработаны группой исследователей Математического центра в Академгородке (соглашение с Министерством науки и высшего образования РФ номер 075-15-2019-1675)

Узнать об образовательных программах Новосибирского государственного университета: https://education.nsu.ru/bachelor/

• Основы алгебраической теории графов
• Основная часть модуля посвящена базовым определениям и понятиям теории графов и теории групп. Вы также узнаете про историю развития этих математических дисциплин и о том, какие задачи лежали в их основе. Кроме того, вы научитесь решать задачи о перекладывании блинчиков и о сборке кубика Рубика. А ещё вы узнаете про задачу поиска пути в лабиринте, которую решил Эдвард Мур, и про целый класс графов Мура.
• Графы и матрицы
• В этом модуле вы узнаете, что графы можно найти абсолютно везде: например, в социальных сетях, в поисковых системах или в теории шести рукопожатий. Это значит, что множество вопросов можно перевести на язык графов. А там где графы, там и их матрицы — это и есть основа алгебраической теории графов. Мы сфокусируемся на матрицах смежности графов и их спектрах. Вы научитесь слышать, что говорят собственные числа графов и видеть, в каких свойствах графов они себя проявляют. Вы познакомитесь с такими важными классами графов, как сильно регулярные и дистанционно регулярные, узнаете, как операции на графах меняют их спектры. Эти классы графов применяются в теории кодирования, теории комбинаторных дизайнов, квантовой теории информации и даже в финансовой сфере. Кроме того, вы овладеете различными приёмами, как находить спектры графов, не вычисляя корни характеристических полиномов. А ещё вы познакомитесь со славной традицией использовать граф Петерсена в качестве примера или контрпримера.
• Графы и группы
• Этот модуль посвящен связи между графами и группами. Вы узнаете, как возникают автоморфизмы на множествах вершин и ребёр, как транзитивность графов связана с их регулярностью, всякие ли вершинно-транзитивные графы являются графами Кэли, как графы Кэли возникают в других областях знаний. Например, они активно используются в теории межкоммуникационных сетей. Мы также расскажем о том, как Ричард Хэмминг придумал первый компьютерный код с автоматическим исправлением ошибки и метрику, на основе которой строится целый класс графов.
• Спектральная теория графов
• На 4-ой неделе нашего курса научитесь решать прикладные задачи, в которых применение спектральной теории графов даёт неожиданные результаты. Например, современные исследования в квантовой химии показывают удивительные связи между структурой химического соединения и спектральными свойствами его молекулярного графа. Вы узнаете, что собственные числа имеют даже конкретный физический смысл на примере музыкальных барабанов. Помимо этого вы увидите, как с помощью собственных чисел и векторов можно рисовать картинки, определять чемпионов в турнирах и доказывать какие-то свойства графов, даже не зная, как именно он выглядит. И хотя главным действующим лицом четвёртого модуля будет уже матрица Лапласа, мы всё же не забудем про матрицу смежности и поговорим о связи коэффициентов её характеристического полинома с локальной структурой графа. Вы узнаете, как переплетаются между собой собственные числа графа и его индуцированных подграфов.
• Спектр Star графа и теория представлений симметрической группы
• Продолжаем погружение в исследования современной математики и знакомимся с наиболее продвинутым модулем этого курса. Основной объект исследования в этом модуле — Star граф — наиболее изучен в теории межкоммуникационных сетей. На его примере вы увидите связь между спектральной теорией и теорией представлений конечных групп. Вы научитесь работать со стандартными таблицами Юнга, представлением симметрической группы, элементами Юциса — Мёрфи, спектром Star графа и с тем, как вычислять кратности собственных значений.
• Схемы отношений и когерентные конфигурации
• В заключительном модуле курса вы продолжите знакомство с самыми актуальными математическими вопросами и познакомитесь с такими новыми понятиями, как схемы отношений и когерентные конфигурации. Однако при ближайшем рассмотрении вы довольно быстро сможете узнать в них объекты, которые уже изучали ранее. Помимо старых знакомых, вас ждёт встреча с алгебрами Боуза — Меснера и параметрами Крейна, новый взгляд на дистанционно регулярные графы и возвращение к тому самому графу Мура, про который всё ещё неизвестно, существует он или нет. Вы научитесь с помощью разных методов описывать один и тот же объект и визуализировать его (например, цветными табличками и треугольниками или набором матриц). И, конечно, уже точно будете знать, как вам проводить эксперименты наиболее удобным способом. Кстати, граф Петерсена тут тоже будет, но уже в новом амплуа.