up
  • 12 weeks

    course duration

  • 3 credit points

    for credit at your university

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

About

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

Format

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

  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.

Requirements

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

Course program

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

Education results

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

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

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

course completion certificate

Certificate

It is possible to get a certificate for this course.

The cost of passing the procedures for assessing learning outcomes with personal identification - 1800 Р.

Similar courses