Полная окраска - Complete coloring

Полная окраска Граф Клебша с 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-жесткий; определение того, больше ли оно заданного числа, НП-полный, как показали Яннакакис и Гаврил в 1978 году путем преобразования из задачи минимального максимального согласования.^[1]

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

Алгоритмы

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

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

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

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

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

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

использованная литература

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

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

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

[fhhm-2] а ^б Farber, M .; Hahn, G .; Черт, П.; Миллер, Д. Дж. (1986), "Относительно ахроматического числа графов", Журнал комбинаторной теории, серия B, 40 (1): 21–39, Дои:10.1016/0095-8956(86)90062-6.

[cv-3] а ^б Чаудхари, Амитабх; Вишванатан, Сундар (2001), «Алгоритмы приближения для ахроматического числа», Журнал алгоритмов, 41 (2): 404–416, CiteSeerX 10.1.1.1.5562, Дои:10.1006 / jagm.2001.1192, S2CID 9817850.

[4] Бодландер, Х. (1989), «Ахроматическое число NP-полно для кографов и интервальных графов», Инф. Обработать. Lett., 31 (3): 135–138, Дои:10.1016/0020-0190(89)90221-4, HDL:1874/16576.

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

[6] Yannakakis, M .; Гаврил, Ф. (1980), "Множества с преобладанием ребер в графах", Журнал SIAM по прикладной математике, 38 (3): 364–372, Дои:10.1137/0138030.

[7] Ройхман Ю. (2000), "Об ахроматическом числе гиперкубов", Журнал комбинаторной теории, серия B, 79 (2): 177–182, Дои:10.1006 / jctb.2000.1955.

[1]

[2]

[3]

[4]

[5]

[6]

[7]