up

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

Добавить в избранное
  • Russian

    course language

  • от 8 до 10 недель

    course duration

  • from 8 to 12 hours per week

    needed to educate

  • 3 credit points

    for credit at your university

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

About

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

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

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

 

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

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

Format

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

Course program

Модуль 1. Введение

  • Историческое развитие алгебраической теории графов

  • Базовые понятия теории графов

  • Дистанционно регулярные графы

  • Графы Мура

 

Модуль 2.  Немного о группах

  • Основы теории групп

  • Блинчиковый граф и биокомпьютер

  • Кубик Рубика

 

Модуль 3. Графы и матрицы

  • Что линейная алгебра говорит о графах?

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

 

Модуль 4. О спектрах графов

  • Спектры некоторых графов

  • Спектры после операций над графами

  • Сильно регулярные графы

  • Дистанционно регулярные графы

  • Практикум: считаем спектры

 

Модуль 5. Графы и группы

  • Группа автоморфизмов графа

  • Транзитивные и симметричные графы

  • Дистанционно-транзитивные графы

 

Модуль 6. Графы Кэли, Хэмминга и Джонсона

  • Графы Кэли

  • Схематическая связь между регулярными и транзитивными графами

  • Граф Хэмминга: дистанционно-транзитивный граф Кэли

  • Графы Джонсона: дистанционно-транзитивный граф, но не всегда граф Кэли

 

Модуль 7. Спектральная теория графов

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

  • Матрица Лапласа

  • Спектральная визуализация и кластеризация

  • Теорема Перрона — Фробениуса и задача ранжирования

  • Характеристический полином и изоспектральные графы

  • О сплетении/чередовании собственных значений

  • Граница весового распределения, и о чём ещё говорят графы?

 

Модуль 8. Star граф, перестановки и симметрическая группа

  • Star граф и его основные свойства

  • Перестановки и их классы сопряжённости

  • Разбиения, цикловой тип перестановок и таблицы Юнга

 

Модуль 9. Теория представлений симметрической группы

  • Представление конечной группы

  • Представление симметрической группы через элементы Юциса — Мёрфи

  • Элементы Юциса — Мёрфи и спектр Star графа

  • Формула крюка и кратности собственных значений

 

Модуль 10. Схемы отношений и когерентные конфигурации

  • Отношения как разбиения

  • Схемы отношений на языке графов

  • Через мир матриц к дистанционно регулярным графам

  • Алгебра Боуза — Меснера

  • Параметры Крейна, P- и Q-полиномиальность

  • Возвращение к графу Мура на 3250 вершинах

  • Когерентные конфигурации как обобщение схем отношений

Итоги

Education results

  • Развитие навыков анализа графов с алгебраической точки зрения, в частности, при исследовании их спектральных свойств, а также на при анализе дискретных структур, обладающих высокой симметрией;

  • установление междисциплинарных связей между графами и группами, между группами и их матрицами, между спектрами матриц и графами;

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

Formed competencies

Способен формулировать и решать актуальные и значимые проблемы математики (ОПК-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)

Education directions

Стоимость — 3600 рублей. Оплатить обучение можно через раздел "Мои курсы" в личном кабинете. Преподаватель отвечает на вопросы на форуме.

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

Кандидат технических наук, доцент
Position: Доцент кафедры теоретической кибернетики ММФ НГУ

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

Кандидат физико-математических наук
Position: Преподаватель кафедры теоретической кибернетики ММФ НГУ

Similar courses