Содержание
- 2. У Ч Е Б Н Ы Е В О П Р О С Ы 1. Основные
- 3. 1. Основные понятия. Хроматическое число Характерным специфическим направлением теории графов является цикл задач, связанный с раскрасками
- 4. Каждый многоугольный граф можно представить себе как некоторую географическую карту, где грани - это страны, а
- 5. Задача эта приобрела известность с 1879 г., когда английский математик Артур Кэпи привел ее формулировку на
- 6. Другое применение раскраски в графах может быть использовано при: распределение памяти в ЭВМ; проектирование сетей телевизионного
- 7. Терминология, в которой метки называются цветами, происходит от раскраски политических карт. Такие метки как красный или
- 8. Рёберная раскраска Рёберная 3-цветная раскраска В теории графов рёберной раскраской графа называется назначение «цветов» рёбрам графа
- 9. Пример - Построение раскраски графа K8 в 7 цветов Рисунок 2 - Граф может быть раскрашен
- 10. Хроматический многочлен Хроматический многочлен считает число возможных вариантов раскраски графа с использованием не более чем заданного
- 11. 2. Алгоритмы раскраски графа Алгоритм раскраски графа позволяет находить (точное или приближенное) значение хроматического числа произвольного
- 12. Правильная раскраска графа G может выглядеть следующим образом: Рассмотрим последовательный метод, основанный на упорядочивании множества вершин.
- 13. Раскраска графа по степеням вершин Алгоритм Упорядочить вершины по степеням начиная с наибольшей степени вершины. Задать
- 14. Пример: задан граф Раскрасить по степеням вершин Раскрасить по степеням вершин Составим таблицу:
- 15. В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней. Первая вершина окрашивается
- 16. Приведенный алгоритм можно модифицировать. Для этого после каждого шага нужно упорядочивать неокрашенные вершины. Простая модификация описанной
- 17. Примеры раскрасок графов
- 18. Алгоритм с использованием независимого множества вершин Независимое множество вершин S – это такое подмножество вершин, в
- 19. Алгоритм определения независимого множества S Выбирается начальная вершина v0 и заносится в S. Рассматривается следующая вершина
- 21. Скачать презентацию