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

Novosibirsk State University via Coursera

Go to class Write review

This course may be unavailable.

Details

This course may be unavailable.

Go to class

Provider

Coursera
Pricing

Free Online Course (Audit)
Languages

Russian
Certificate

Paid Certificate Available
Duration & workload

6 weeks
Sessions

Finished
Level

Intermediate
Subtitles

Russian

Found in

Overview

Class Central Tips

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

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

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

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

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

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

Syllabus

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

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

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

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

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

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

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

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

Спектр Star графа и теория представлений симметрической группы

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

Схемы отношений и когерентные конфигурации

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