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

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

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

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

Формат

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

Требования

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

Сертификат

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