Открываем 110+ курсов на неделю за 1 ₽Узнать больше
Партнёры Академика Pro
  • Для всех
  • С сертификатом
  • На русском языке
  • 12 часов
  • 3 000

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

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

  • Для всех
  • С сертификатом
  • На русском языке
  • 12 часов
  • 3 000
Посмотреть программу

Трейлер курса

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

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

  • 6 модулей
  • 6 тем
  • 12 часов
  • Основы алгебраической теории графов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Спикеры

  • Евгения Сотникова

    Евгения Сотникова

    Кандидат физико-математических наук, преподаватель кафедры теоретической кибернетики
  • Елена Константинова

    Елена Константинова

    Кандидат технических наук, доцент кафедры теоретической кибернетики

Сертификат от НГУ

Подтвердит, что вы прошли курс, и усилит ваше портфолио или резюме.