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

Полная раскраска графа Клебша в 8 цветов. Каждая пара цветов появляется как минимум на одном краю. Полной раскраски с большим количеством цветов не существует: в любой 9-раскраске некоторый цвет появлялся бы только в одной вершине, и не было бы достаточно соседних вершин, чтобы покрыть все пары, включающие этот цвет. Следовательно, ахроматическое число графика Клебша равно 8.

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

Теория сложности [ править ]

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

ЭКЗЕМПЛЯР: график и положительное целое число

{\ Displaystyle G = (V, E)}

{\ displaystyle k}

Вопрос: существует ли раздел из в или более непересекающихся множеств , таких , что каждый является независимым множеством для и таким образом, что для каждой пары различных множеств не является независимым множеством.

{\ displaystyle V}

{\ displaystyle k}

{\ Displaystyle V_ {1}, V_ {2}, \ ldots, V_ {k}}

{\ displaystyle V_ {i}}

{\ displaystyle G}

{\ displaystyle V_ {i}, V_ {j}, V_ {i} \ cup V_ {j}}

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

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

Алгоритмы [ править ]

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

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

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

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

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

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

Ссылки [ править ]

^ ^a b Майкл Р. Гэри и Дэвид С. Джонсон (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5 A1.1: GT5, стр. 191.
^ а б Фарбер, М .; Hahn, G .; Ад, П .; Миллер, DJ (1986), «Относительно ахроматического числа графиков», Журнал комбинаторной теории, серия B , 40 (1): 21–39, DOI : 10.1016 / 0095-8956 (86) 90062-6.
^ a b Чаудхари, Амитабх; Вишванатан, Сундара (2001 год), "Аппроксимация алгоритмы для ахроматической числа", журнал алгоритмов , 41 (2): 404-416, CiteSeerX 10.1.1.1.5562 , DOI : 10,1006 / jagm.2001.1192 , S2CID 9817850 .
^ Bodlaender, H. (1989), "номер ахроматический является NP-полной для cographs и интервальных графов", Inf. Процесс. Lett. , 31 (3): 135-138, DOI : 10,1016 / 0020-0190 (89) 90221-4 , ЛВП : 1874/16576.
^ Manlove, D .; МакДирмид, С. (1995), "Сложность гармоничных окрасок для дерев", Дискретная прикладная математика , 57 (2-3): 133-144, DOI : 10.1016 / 0166-218X (94) 00100-R.
^ Yannakakis, M .; Гаврила, F. (1980), "Край доминирующие множества в графах", SIAM журнал по прикладной математике , 38 (3): 364-372, DOI : 10,1137 / 0138030.
^ Ройхман, Y. (2000), "О ахроматических Количество Гиперкубы", Журнал комбинаторной теории, серии B , 79 (2): 177-182, DOI : 10,1006 / jctb.2000.1955.

Внешние ссылки [ править ]

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

[gj-1] Майкл Р. Гэри и Дэвид С. Джонсон (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5 A1.1: GT5, стр. 191.

[fhhm-2] а б Фарбер, М .; Hahn, G .; Ад, П .; Миллер, DJ (1986), «Относительно ахроматического числа графиков», Журнал комбинаторной теории, серия B , 40 (1): 21–39, DOI : 10.1016 / 0095-8956 (86) 90062-6.

[cv-3] Чаудхари, Амитабх; Вишванатан, Сундара (2001 год), "Аппроксимация алгоритмы для ахроматической числа", журнал алгоритмов , 41 (2): 404-416, CiteSeerX 10.1.1.1.5562 , DOI : 10,1006 / jagm.2001.1192 , S2CID 9817850 .

[4] Bodlaender, H. (1989), "номер ахроматический является NP-полной для cographs и интервальных графов", Inf. Процесс. Lett. , 31 (3): 135-138, DOI : 10,1016 / 0020-0190 (89) 90221-4 , ЛВП : 1874/16576.

[5] Manlove, D .; МакДирмид, С. (1995), "Сложность гармоничных окрасок для дерев", Дискретная прикладная математика , 57 (2-3): 133-144, DOI : 10.1016 / 0166-218X (94) 00100-R.

[6] Yannakakis, M .; Гаврила, F. (1980), "Край доминирующие множества в графах", SIAM журнал по прикладной математике , 38 (3): 364-372, DOI : 10,1137 / 0138030.

[7] Ройхман, Y. (2000), "О ахроматических Количество Гиперкубы", Журнал комбинаторной теории, серии B , 79 (2): 177-182, DOI : 10,1006 / jctb.2000.1955.

[1]