В теории графов полная раскраска — это противоположность гармонической раскраске в том смысле, что это раскраска вершин, в которой каждая пара цветов встречается по меньшей мере на одной паре смежных вершин. Эквивалентно, полная раскраска — это минимальная раскраска, в том смысле, что её нельзя преобразовать в правильную раскраску с меньшим числом цветов путём слияния двух цветов. Ахроматическое число ψ(G) графа G — это максимальное число цветов среди всех полных раскрасок графа G.
Теория сложности Нахождение ψ(G) является задачей оптимизации. Проблема разрешимости для полной раскраски может быть сформулирована как:
ДАНО: Граф и положительное целое число ВОПРОС: Существует ли разбиение множества вершин на или более непересекающихся множеств таких, что каждое является независимым множеством для и таких, что для каждой пары различных множеств независимым множеством не является.
Определение ахроматического числа является NP-трудной. Определение, не будет ли ахроматическое число больше заданного числа является NP-полной, как показали Янакакис и Гаврил (Yannakakis, Gavril) в 1978 году путём преобразования из задачи поиска минимального наибольшего паросочетания A1.1: GT5, pg. 191..
Заметим, что любая раскраска графа с минимальным числом цветов должна быть полной раскраской, так что минимизация числа цветов полной раскраски является просто переформулировкой стандартной задачи раскраски графа.
Алгоритм Оптимизационная задача допускает аппроксимацию с гарантированной эффективностью ..
Специальные случаи графов Задача определения ахроматического числа остаётся NP-полной также для некоторых специальных классов графов: двудольные графы., дополнения двудольных графов (то есть, графы, не имеющие независимого множества с более чем двумя вершинами), кографы, интервальные графы. и даже деревья..
Для дополнений деревьев ахроматическое число может быть вычислено за полиномиальное время.. Для деревьев можно задачу аппроксимировать с постоянным коэффициентом.
Известно, что ахроматическое число n-мерного графа гиперкуба пропорционально , но точная константа пропорциональности не известна..
Примечания
Ссылки A compendium of NP optimization problems A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards
Категория:Теория графов Категория:Раскраска графа