course language
course duration
needed to educate
for credit at your university
В курсе “Алгебраическая теория графов” вы узнаете о свойствах графов и о том, как их исследовать. Вы научитесь самостоятельно строить такие структуры, анализировать их и находить ответ на любой вопрос. Вы сможете применять инструменты алгебраической теории графов для оптимального решения задач в химии, биологии, биоинформатике, физике, социологии, теории кодирования, криптографии и многих других областях.
Не секрет, что математика — универсальный язык для исследований. А графы в математике — универсальные высоко симметричные структуры, с помощью которых можно изучать множество объектов различной природы и их свойства.
Вы сталкиваетесь с ними каждый день в повседневных ситуациях. Например, когда строите оптимальный маршрут до университета или работы. Ещё такие объекты встречаются в прикладных научных задачах из разных сфер: графы эффективно используются в теории межкоммуникационных сетей, помогают моделировать эволюционные мутационные процессы в биологии и не только.
Структура графов необходима и при создании биокомпьютера или в квантовой химии — в общем, методы алгебраической теории графов универсальны.
В курсе вы узнаете о свойствах графов и о том, как их исследовать. Вы научитесь самостоятельно строить такие структуры, анализировать их и находить ответ на любой вопрос. Вы сможете применять инструменты алгебраической теории графов для оптимального решения задач в химии, биологии, биоинформатике, физике, социологии, теории кодирования, криптографии и многих других областях.
Первые модули курса помогут вспомнить основы теории графов, теории групп и линейной алгебры, чтобы постепенно познакомить вас с современными математическими исследованиями. В последних модулях вы узнаете об актуальных новых вопросах, которые возникли благодаря алгебраической теории графов и открыты для исследований.
Курс состоит из 10 недель обучения.
Образовательные активности каждой недели включают:
Просмотр видеолекций
Ответы на вопросы после лекций (на закрепление материалов)
Работа с дополнительными источниками (чтение текстов, решение задач по теме недели)
Выполнение оцениваемого теста (ответы на вопросы, решение небольших задач) по итогам недели
Кроме того, студенты должны пройти итоговый тест по материалам всего курса для получения итоговой оценки.
Е.В. Константинова, Комбинаторные задачи на графах Кэли, Учебное пособие, Новосибирск, РИЦ НГУ, 2014. https://www.nsu.ru/n/mathematics-mechanics-department/studentam/uchebnye-materialy/
Topics in Algebraic Graph Theory, In: Encyclopedia of Mathematics and its Applications, Vol.102, Eds.: L.W. Beineke, R.J. Wilson, P.J. Cameron: Cambridge University Press, 2005.
N. Biggs, Algebraic graph theory, (2nd ed.), Cambridge: Cambridge University Press, 1994.
A.E. Brouwer, W.H. Haemers, E. Konstantinova, and R.M. Wilson. Lecture on Combinatorics I, IPM Lecture Notes Series 8, IPM, 2008, Chapter 2, pp.67-144. (see also http://math.ipm.ac.ir/publications/book.htm).
C. Godsil, G.F. Royle, Algebraic Graph Theory, In: Graduate Texts in Mathematics, Vol.207, New York: Springer-Verlag, 2001.
E. Konstantinova, Lecture notes on some problems on Cayley graphs, Koper: Knjiznica za tahniko, medicino in naravoslovje, TeMeNa, 2012, 93 pp. (ISBN 978-961-93076-1- 8) (see also: http://temena.famnit.upr.si/files/files/Lecture_Notes_2012.pdf).
Модуль 1. Введение
Историческое развитие алгебраической теории графов
Базовые понятия теории графов
Дистанционно регулярные графы
Графы Мура
Модуль 2. Немного о группах
Основы теории групп
Блинчиковый граф и биокомпьютер
Кубик Рубика
Модуль 3. Графы и матрицы
Что линейная алгебра говорит о графах?
Собственные числа и векторы графов
Модуль 4. О спектрах графов
Спектры некоторых графов
Спектры после операций над графами
Сильно регулярные графы
Дистанционно регулярные графы
Практикум: считаем спектры
Модуль 5. Графы и группы
Группа автоморфизмов графа
Транзитивные и симметричные графы
Дистанционно-транзитивные графы
Модуль 6. Графы Кэли, Хэмминга и Джонсона
Графы Кэли
Схематическая связь между регулярными и транзитивными графами
Граф Хэмминга: дистанционно-транзитивный граф Кэли
Графы Джонсона: дистанционно-транзитивный граф, но не всегда граф Кэли
Модуль 7. Спектральная теория графов
Алгебраическая теория графов в примерах
Матрица Лапласа
Спектральная визуализация и кластеризация
Теорема Перрона — Фробениуса и задача ранжирования
Характеристический полином и изоспектральные графы
О сплетении/чередовании собственных значений
Граница весового распределения, и о чём ещё говорят графы?
Модуль 8. Star граф, перестановки и симметрическая группа
Star граф и его основные свойства
Перестановки и их классы сопряжённости
Разбиения, цикловой тип перестановок и таблицы Юнга
Модуль 9. Теория представлений симметрической группы
Представление конечной группы
Представление симметрической группы через элементы Юциса — Мёрфи
Элементы Юциса — Мёрфи и спектр Star графа
Формула крюка и кратности собственных значений
Модуль 10. Схемы отношений и когерентные конфигурации
Отношения как разбиения
Схемы отношений на языке графов
Через мир матриц к дистанционно регулярным графам
Алгебра Боуза — Меснера
Параметры Крейна, P- и Q-полиномиальность
Возвращение к графу Мура на 3250 вершинах
Когерентные конфигурации как обобщение схем отношений
Итоги
Развитие навыков анализа графов с алгебраической точки зрения, в частности, при исследовании их спектральных свойств, а также на при анализе дискретных структур, обладающих высокой симметрией;
установление междисциплинарных связей между графами и группами, между группами и их матрицами, между спектрами матриц и графами;
знакомство с применением алгебраической теории графов как в других математических дисциплинах (теория кодирования, алгебраическая геометрия, топология), так и в компьютерных науках, химии, биологии, биоинформатике.
Способен формулировать и решать актуальные и значимые проблемы математики (ОПК-1 ФГОС ВО 3++ 01.04.01)
Способен решать актуальные задачи фундаментальной и прикладной математики (ОПК-1 ФГОС ВО 3++ 01.04.02)
Способен находить, формулировать и решать актуальные проблемы механики и математики (ОПК-1 ФГОС ВО 3++ 01.04.03)
Способен обобщать и критически оценивать опыт и результаты научных исследований в области прикладной математики (ОПК-1 ФГОС ВО 3++ 01.04.04)
Способен находить, формулировать и решать актуальные и значимые проблемы прикладной и компьютерной математики (ОПК-1 ФГОС ВО 3++ 02.04.01)
Способен находить, формулировать и решать актуальные проблемы прикладной математики, фундаментальной информатики и информационных технологий (ОПК-1 ФГОС ВО 3++ 02.04.02, 02.04.03)
course language
course duration
needed to educate
for credit at your university
Стоимость — 3600 рублей. Оплатить обучение можно через раздел "Мои курсы" в личном кабинете. Преподаватель отвечает на вопросы на форуме.
Кандидат технических наук, доцент
Position: Доцент кафедры теоретической кибернетики ММФ НГУ
Кандидат физико-математических наук
Position: Преподаватель кафедры теоретической кибернетики ММФ НГУ