Полная окраска

В теории графов полная раскраска — это (правильная) раскраска вершин , в которой каждая пара цветов появляется по крайней мере на одной паре смежных вершин . Эквивалентно, полная раскраска минимальна в том смысле, что ее нельзя преобразовать в правильную раскраску с меньшим количеством цветов путем слияния пар цветовых классов. Ахроматическое число $ψ(G)$ графа $G$ — это максимальное количество цветов, возможное в любой полной раскраске $G$ .

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

Теория сложности

Нахождение $ψ(G)$ является задачей оптимизации . Задача принятия решения для полной раскраски может быть сформулирована как:

ПРИМЕР: граф

G = (V, E)

и положительное целое число

k

ВОПРОС: существует ли разбиение V на

k

или более непересекающихся множеств

V

1

,

V

2

, \dots,

V

k

такое, что

каждое

V

i

является независимым множеством для

G

и такое, что для каждой пары различных множеств

V

i

,

V

j

,

V

i

\cup

V

j

не является независимым множеством.

Определение ахроматического числа является NP-трудной задачей ; определение того, больше ли оно заданного числа, является NP-полной задачей , как показали Яннакакис и Гаврил в 1978 году с помощью преобразования из задачи минимального максимального соответствия. ^[1]

Обратите внимание, что любая раскраска графа минимальным количеством цветов должна быть полной раскраской, поэтому минимизация количества цветов при полной раскраске — это просто переформулировка стандартной задачи раскраски графа .

Алгоритмы

Для любого фиксированного k можно определить, является ли ахроматическое число данного графа по крайней мере k , за линейное время. ^[2]

Задача оптимизации допускает аппроксимацию и аппроксимируется в пределах аппроксимационного отношения . ^[3] $O\left(|V|/{\sqrt {\log |V|}}\right)$

Специальные классы графов

NP-полнота задачи ахроматического числа справедлива также для некоторых специальных классов графов: двудольных графов , ^[2]дополнений двудольных графов (то есть графов, не имеющих независимого множества из более чем двух вершин), ^[1] кографов и интервальных графов , ^[4] и даже для деревьев. ^[5]

Для дополнений деревьев ахроматическое число может быть вычислено за полиномиальное время. ^[6] Для деревьев его можно аппроксимировать с точностью до постоянного множителя. ^[3]

Известно, что ахроматическое число n -мерного гиперкубического графа пропорционально , но константа пропорциональности точно не известна. ^[7] ${\sqrt {n2^{n}}}$

Ссылки

^ ab Майкл Р. Гэри и Дэвид С. Джонсон (1979), Компьютеры и неразрешимость: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5A1.1: GT5, стр.191.
^ ab Farber, M.; Hahn, G.; Hell, P .; Miller, DJ (1986), «Относительно ахроматического числа графов», Журнал комбинаторной теории, Серия B , 40 (1): 21–39, doi : 10.1016/0095-8956(86)90062-6.
^ ab Чаудхари, Амитабх; Вишванатан, Сундар (2001), «Алгоритмы аппроксимации для ахроматического числа», Журнал алгоритмов , 41 (2): 404–416, CiteSeerX 10.1.1.1.5562 , doi :10.1006/jagm.2001.1192, S2CID 9817850 .
^ Bodlaender, H. (1989), "Ахроматическое число является NP-полным для кографов и интервальных графов", Inf. Process. Lett. , 31 (3): 135–138, doi :10.1016/0020-0190(89)90221-4, hdl : 1874/16576.
^ Мэнлав, Д.; МакДиармид, К. (1995), «Сложность гармоничной раскраски деревьев», Дискретная прикладная математика , 57 (2–3): 133–144, doi : 10.1016/0166-218X(94)00100-R.
^ Яннакакис, М.; Гаврил, Ф. (1980), «Наборы, доминирующие рёбра в графах», SIAM Journal on Applied Mathematics , 38 (3): 364–372, doi :10.1137/0138030.
^ Ройхман, Ю. (2000), «Об ахроматическом числе гиперкубов», Журнал комбинаторной теории, Серия B , 79 (2): 177–182, doi : 10.1006/jctb.2000.1955.

Внешние ссылки

Сборник задач оптимизации NP
Библиография гармонических цветов и ахроматических чисел Кейта Эдвардса