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

Новосибирский государственный университет
Novosibirsk State University (NSU) is a research university located in Novosibirsk Akademgorodok, the world-famous scientific center in Siberia. 80% of NSU teachers are active researchers affiliated with the Russian Academy of Sciences; therefore education is closely linked to world-class science: our students get first-hand knowledge about scientific discoveries before they are published.
Программа курса: что вы изучите
Основы алгебраической теории графов
Основная часть модуля посвящена базовым определениям и понятиям теории графов и теории групп. Вы также узнаете про историю развития этих математических дисциплин и о том, какие задачи лежали в их основе. Кроме того, вы научитесь решать задачи о перекладывании блинчиков и о сборке кубика Рубика. А ещё вы узнаете про задачу поиска пути в лабиринте, которую решил Эдвард Мур, и про целый класс графов Мура.
Графы и матрицы
В этом модуле вы узнаете, что графы можно найти абсолютно везде: например, в социальных сетях, в поисковых системах или в теории шести рукопожатий. Это значит, что множество вопросов можно перевести на язык графов. А там где графы, там и их матрицы — это и есть основа алгебраической теории графов. Мы сфокусируемся на матрицах смежности графов и их спектрах. Вы научитесь слышать, что говорят собственные числа графов и видеть, в каких свойствах графов они себя проявляют. Вы познакомитесь с такими важными классами графов, как сильно регулярные и дистанционно регулярные, узнаете, как операции на графах меняют их спектры. Эти классы графов применяются в теории кодирования, теории комбинаторных дизайнов, квантовой теории информации и даже в финансовой сфере. Кроме того, вы овладеете различными приёмами, как находить спектры графов, не вычисляя корни характеристических полиномов. А ещё вы познакомитесь со славной традицией использовать граф Петерсена в качестве примера или контрпримера.
Графы и группы
Этот модуль посвящен связи между графами и группами. Вы узнаете, как возникают автоморфизмы на множествах вершин и ребёр, как транзитивность графов связана с их регулярностью, всякие ли вершинно-транзитивные графы являются графами Кэли, как графы Кэли возникают в других областях знаний. Например, они активно используются в теории межкоммуникационных сетей. Мы также расскажем о том, как Ричард Хэмминг придумал первый компьютерный код с автоматическим исправлением ошибки и метрику, на основе которой строится целый класс графов.
Спектральная теория графов
На 4-ой неделе нашего курса научитесь решать прикладные задачи, в которых применение спектральной теории графов даёт неожиданные результаты. Например, современные исследования в квантовой химии показывают удивительные связи между структурой химического соединения и спектральными свойствами его молекулярного графа. Вы узнаете, что собственные числа имеют даже конкретный физический смысл на примере музыкальных барабанов. Помимо этого вы увидите, как с помощью собственных чисел и векторов можно рисовать картинки, определять чемпионов в турнирах и доказывать какие-то свойства графов, даже не зная, как именно он выглядит. И хотя главным действующим лицом четвёртого модуля будет уже матрица Лапласа, мы всё же не забудем про матрицу смежности и поговорим о связи коэффициентов её характеристического полинома с локальной структурой графа. Вы узнаете, как переплетаются между собой собственные числа графа и его индуцированных подграфов.
Часто задаваемые вопросы
Когда я получу доступ к лекциям и заданиям?
Что я получу, оплатив сертификацию?
Is financial aid available?
Остались вопросы? Посетите Центр поддержки учащихся.