More Related Content
Viewers also liked (12)
More from Alex Dainiak (19)
Раскраски и укладки графов
- 1. Дискретные структуры МФТИ, осень 2013 Александр Дайняк www.dainiak.com
- 2. Раскраски вершин и рёбер
- 3. Раскраски вершин и рёбер
- 4. Примеры задач о раскраске • Сотовый оператор установил в городе свои антенны. Некоторые пары антенн расположены близко друг к другу и вынуждены использовать разные частоты. Сколько радиочастот придётся выкупить сотовому оператору у городских властей? • Лидеры стран G-20 собрались на саммит. Некоторые пары участников хотят побеседовать друг с другом наедине. У каждого участника на одну такую встречу уходит один день. Во сколько дней можно уложить саммит?
- 5. Примеры задач о раскраске Исторически первая задача о раскраске: • Сколько цветов достаточно использовать в типографии, чтобы можно было напечатать любую географическую карту (так, чтобы граничащие друг с другом страны не сливались на карте)?
- 6. Примеры задач о раскраске Задачу о раскраске карт можно переформулировать на языке раскрасок, рассмотрев планарный граф, двойственный карте: • Сколькими цветами можно правильно раскрасить любой планарный граф?
- 8. Хроматическое число Хроматическое число — это минимальное количество независимых множеств, на которое можно разбить множество вершин графа. Хроматический индекс — это минимальное количество паросочетаний, на которое можно разбить множество рёбер графа.
- 14. Теорема Брукса
- 17. Теорема Визинга
- 18. На заметку
- 19. Укладки графов
- 20. Укладки графов
- 21. Планарные графы Планарный граф — это граф, для которого существует плоская укладка. Например, граф планарный
- 22. Планарные графы Грань укладки — это область поверхности, отделяемая укладкой. Пример:
- 23. Планарные графы на сферах Утверждение. Граф планарен т. и т.т., когда его можно уложить на сфере. Идея доказательства. Используем стереографическую проекцию. Единственное требование — чтобы центр проекции не совпадал с вершиной графа и не лежал на ребре.
- 24. Циклы в планарных графах
- 25. Циклы в планарных графах Затем выполняем инверсию плоскости относительно этой окружности.
- 26. Циклы в планарных графах
- 27. Формула Эйлера
- 28. Формула Эйлера
- 29. Формула Эйлера
- 30. Формула Эйлера
- 31. Рёбра и грани
- 32. Число рёбер в планарных графах
- 35. Стягивание рёбер
- 36. Стягивание рёбер
- 37. Стягивание рёбер
- 38. Миноры
- 39. Планарные графы и миноры
- 40. Планарные графы и миноры