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

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

Для бесплатного просмотра доступны только часть материалов курса. Полный доступ откроется только после оплаты сертификации. Стоимость сертификации составляет 3600 рублей.

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

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

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

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