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

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

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

Структура графов необходима и при создании биокомпьютера или в квантовой химии — в общем, методы алгебраической теории графов универсальны.

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

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

Курс состоит из 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)