Теория графов от МФТИ

Этот курс служит введением в современную теорию графов. Граф как математический объект оказывается полезным во многих теоретических и практических задачах.  

Теория графов от МФТИ
Бесплатно
12 недель12 недель
Платный сертификатПлатный сертификат
РусскийРусский
МФТИ
Открытое Образование

Описание:

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

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

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

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