4817
правок
Точный алгоритм раскраски графа с использованием метода включения-исключения: различия между версиями
Перейти к навигации
Перейти к поиску
Точный алгоритм раскраски графа с использованием метода включения-исключения (посмотреть исходный код)
Версия от 10:23, 17 февраля 2014
, 17 февраля 2014нет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == раскраска вершин графа == Постановка задачи == Алгоритм k…») |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
[[ | [[Раскраска вершин графа]] | ||
== Постановка задачи == | == Постановка задачи == | ||
Алгоритм k-раскраски графа G = (V, E) присваивает один из k цветов каждой вершине графа таким образом, чтобы соседние вершины имели разные цвета. Также используется название «раскраска вершин». | Алгоритм [[k-раскраска|k-раскраски]] графа G = (V, E) присваивает один из k цветов каждой вершине графа таким образом, чтобы соседние вершины имели разные цвета. Также используется название «раскраска вершин». | ||
Наименьшее целочисленное значение k, для которого существует k-раскраска графа G, называется хроматическим числом графа и обозначается | Наименьшее целочисленное значение k, для которого существует k-раскраска графа G, называется [[хроматическое число графа|хроматическим числом графа]] и обозначается <math>\chi(G) \; </math>. Число k-раскрасок графа G, обозначаемое P(G;k), называется [[хроматический многочлен|хроматическим многочленом]]. | ||
== Основные результаты == | == Основные результаты == | ||
Отмечено, что | Отмечено, что <math>\chi(G) \; </math> и P(G;k) могут быть выражены при помощи формулы включения-исключения, члены которой определяются набором независимых множеств порожденных подграфов G. Пусть X С V и пусть s(X) – число непустых независимых подмножеств вершин, не пересекающихся с X; пусть sr(X) обозначает число способов выбора r непустых независимых подмножеств S1…, …, Sr (возможно, перекрывающихся с повторениями), не пересекающихся с X, таких, что jS1j + ---+ jSrj = jVj. | ||
| Строка 43: | Строка 43: | ||
2. время O(2:2461n) и полиномиальный объем памяти. | 2. время O(2:2461n) и полиномиальный объем памяти. | ||
Оптимальную раскраску, дающую | Оптимальную раскраску, дающую <math>\chi(G) \; </math>, можно найти с теми же затратами времени и объема памяти. | ||
Эти техники можно распространить на произвольные семейства подмножеств над совокупностью размера n, при условии, что членство в семействе можно определить за полиномиальное время. | Эти техники можно распространить на произвольные семейства подмножеств над совокупностью размера n, при условии, что членство в семействе можно определить за полиномиальное время. | ||