stringtranslate.com

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

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

В теории графов полная раскраска — это раскраска вершин , при которой каждая пара цветов встречается хотя бы на одной паре соседних вершин . Аналогично, полная раскраска минимальна в том смысле, что ее нельзя преобразовать в правильную раскраску с меньшим количеством цветов путем слияния пар цветовых классов. Ахроматическое число ψ( 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]

Рекомендации

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

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