наверх

Теория графов

видеоролик о курсе

Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день.

О курсе

Этот курс служит введением в современную теорию графов. Граф как математический объект оказывается полезным во многих теоретических и практических задачах. Дело, пожалуй, в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. В нашем курсе мы, конечно же, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов.

Формат

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

  1. В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. М.: Книжный дом «Либроком», 2009.
  2. А. А. Зыков. Теория конечных графов. Новосибирск: Наука, 1969.
  3. М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. М.: Мир, 1984.
  4. M. Aigner, G. M. Ziegler. Proofs From THE BOOK. Fourth Edition. Springer, 2009.
  5. B. Bollobás. Modern Graph Theory. Springer, 1998.
  6. J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, 2008.

Требования

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

Программа курса

  1. Понятие графа и виды графов.
  2. Различные применения графов: от Кенигсберских мостов до Интернета.
  3. Связность графа, подграфы и степень вершины.
  4. Эквивалентные определения деревьев.
  5. Планарность и критерий Куратовского
  6. Формула Эйлера.
  7. Хроматическое число планарного графа.
  8. Перечисление деревьев: код Прюфера и формула Кэли.
  9. Формула для числа унициклических графов.
  10. Эйлеровы циклы и критерий эйлеровости.
  11. Гамильтоновы циклы. Критерий Дирака и критерий Хватала.
  12. Паросочетания. Теорема Холла и Кенига.
  13. Экстремальная теория графов. Теорема Турана.
  14. Аналог теоремы Турана для графов на плоскости.
  15. Теория Рамсея. Знакомства среди шести человек.
  16. Определение числа Рамсея.
  17. Нижняя и верхняя оценки чисел Рамсея.

Результаты обучения

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

  • 12 недель

    длительность курса

  • 3 зачётных единицы

    для зачета в своем вузе

Райгородский Андрей Михайлович

Доктор физико-математических наук
Должность: Заведующий кафедрой Дискретной математики ФИВТ, научный руководитель бакалавриата кафедры «Анализ данных», руководитель отдела теоретических и прикладных исследований Яндекса, главный редактор журнала Moscow Journal of Combinatorics and Number Theory

сертификат об окончании курса

Сертификат

Сертификат участника обычно выдается при достижении 60% от общего рейтинга при условии сдачи работ до жесткого дедлайна. Сертификат с отличием, как правило, выдается при достижении 90% от общего рейтинга при условии сдачи работ до мягкого дедлайна.

Похожие курсы