Полная раскраска
В теории графов полная раскраска — это (правильная) раскраска вершин , при которой каждая пара цветов появляется хотя бы на одной паре соседних вершин . Аналогично, полная раскраска минимальна в том смысле, что ее нельзя преобразовать в правильную раскраску с меньшим количеством цветов путем слияния пар цветовых классов. Ахроматическое число ψ( G ) графа G — это максимальное количество цветов, возможное в любой полной G. раскраске
Полная раскраска является противоположностью гармоничной раскраски , которая требует, чтобы каждая пара цветов появлялась не более чем на одной паре соседних вершин.
Теория сложности
[ редактировать ]Нахождение ψ( G ) является задачей оптимизации . Задачу решения для полной окраски можно сформулировать следующим образом:
- ПРИМЕР: граф G = ( V , E ) и целое положительное число k
- ВОПРОС: существует ли разбиение V что на k или более непересекающихся множеств V 1 , V 2 , …, V k каждое V i является независимым множеством для G и такое, что для каждой пары различных множеств Vi , такое , V j , V i ∪ V j не является независимым множеством.
Определить ахроматическое число NP-трудно ; определение того, больше ли оно заданного числа, является NP-полным , как показали Яннакакис и Гаврил в 1978 году путем преобразования из задачи о минимальном максимальном сопоставлении. [1]
Обратите внимание, что любая раскраска графа в минимальное количество цветов должна быть полной раскраской, поэтому минимизация количества цветов в полной раскраске — это просто повторная формулировка стандартной задачи раскраски графа .
Алгоритмы
[ редактировать ]Для любого фиксированного k можно определить, равно ли ахроматическое число данного графа хотя бы k за линейное время. [2]
Задача оптимизации допускает аппроксимацию и аппроксимируется в пределах коэффициент приближения . [3]
Специальные классы графов
[ редактировать ]NP-полнота проблемы ахроматических чисел справедлива и для некоторых специальных классов графов: двудольные графы , [2] дополнения двудольных графов (то есть графов, не имеющих независимого множества, состоящего более чем из двух вершин), [1] кографы и интервальные графики , [4] и даже для деревьев. [5]
Для дополнений деревьев ахроматическое число можно вычислить за полиномиальное время. [6] Для деревьев его можно аппроксимировать с точностью до постоянного множителя. [3]
Известно , что ахроматическое число n -мерного графа гиперкуба пропорционально , но константа пропорциональности точно не известна. [7]
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б Майкл Р. Гари и Дэвид С. Джонсон (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5 A1.1: GT5, стр. 191.
- ↑ Перейти обратно: Перейти обратно: а б Фарбер, М.; Хан, Г.; Черт, П .; Миллер, DJ (1986), «Относительно ахроматического числа графов», Журнал комбинаторной теории, серия B , 40 (1): 21–39, doi : 10.1016/0095-8956(86)90062-6 .
- ↑ Перейти обратно: Перейти обратно: а б Чаудхари, Амитабх; Вишванатан, Сундар (2001), «Алгоритмы аппроксимации ахроматического числа», Journal of Algorithms , 41 (2): 404–416, CiteSeerX 10.1.1.1.5562 , doi : 10.1006/jagm.2001.1192 , S2CID 9817850 .
- ^ Бодлендер, Х. (1989), «Ахроматическое число NP-полно для кографов и интервальных графов», Inf. Процесс. Летт. , 31 (3): 135–138, doi : 10.1016/0020-0190(89)90221-4 , hdl : 1874/16576 .
- ^ Мэнлав, Д.; МакДиармид, К. (1995), «Сложность гармоничной окраски деревьев», Discrete Applied Mathematics , 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 .