Повне розфарбування

Не плутати з тотальним розфарбуванням.

У теорії графів повне розфарбування — це протилежність гармонійному розфарбуванню в тому сенсі, що це розфарбування вершин, у якому кожна пара кольорів зустрічається принаймні на одній парі суміжних вершин. Еквівалентно, повне розфарбування — це мінімальне розфарбування, в тому сенсі, що його не можна перетворити на правильне розфарбування з меншим числом кольорів злиттям двох кольорів. Ахроматичне число ${\displaystyle \psi (G)}$ графа ${\displaystyle G}$ — це найбільше число кольорів серед усіх повних розфарбувань графа ${\displaystyle G}$.

Повне розфарбування графа Клебша вісьмома кольорами. Кожна пара кольорів з'являється принаймні на одному ребрі. Ніяких повних розфабувань із більшим числом кольорів не існує — за будь-якого розфарбування в 9 кольорів деякі кольори можуть з'явитися тільки на одній вершині, і сусідніх вершин не вистачить, щоб залучити всі пари кольорів. Таким чином, ахроматичне число графа Клебша дорівнює 8.

Теорія складності

Знаходження ${\displaystyle \psi (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-повною задачею, як показали Янакакіс і Гаврил (Yannakakis, Gavril) 1978 року, перетворивши з задачі пошуку мінімального найбільшого парування.

Зауважимо, що будь-яке розфарбування графа з найменшим числом кольорів має бути повним розфарбуванням, так що мінімізація числа кольорів повного розфарбування є просто переформулюванням стандартної задачі розфарбовування графа.

Алгоритм

Оптимізаційна задача допускає апроксимацію з гарантованою ефективністю ${\displaystyle O\left(|V|/{\sqrt {\log |V|}}\right)}$.

Окремі випадки графів

Задача визначення ахроматичного числа залишається NP-повною також для деяких класів графів: двочасткових графів, доповнення двочасткових графів (тобто, графи, які не мають незалежної множини з більш ніж двома вершинами), кографи, інтервальні графи і навіть дерева.

Для доповнень дерев ахроматичне число можна обчислити за поліноміальний час. Для дерев задачу можна апроксимувати зі сталим коефіцієнтом.

Відомо, що ахроматичне число n-вимірного графа гіперкуба пропорційне ${\displaystyle {\sqrt {n2^{n}}}}$, але точний коефіцієнт пропорційності невідомий.

Див. також

• Гармонійне розфарбування
• Тотальне розфарбування
• Т-розфарбування

Примітки

1. ^[en] and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman, 1979. — . A1.1: GT5, pg. 191.
2. Amitabh Chaudhary, Sundar Vishwanathan. Approximation algorithms for the achromatic number // Journal of Algorithms. — 2001. — Т. 41, вип. 2. — С. 404—416. — DOI:10.1006/jagm.2001.1192..
3. M. Farber, G. Hahn, P. Hell, D. J. Miller. Concerning the achromatic number of graphs // Journal of Combinatorial Theory, Series B. — 1986. — Т. 40, вип. 1. — С. 21—39. — DOI:10.1016/0095-8956(86)90062-6..
4. H. Bodlaender. Achromatic number is NP-complete for cographs and interval graphs // Inform. Proc. Lett.. — 1989. — Т. 31, вип. 3. — С. 135—138. — DOI:10.1016/0020-0190(89)90221-4..
5. D. Manlove, C. McDiarmid. The complexity of harmonious coloring for trees // Discrete Applied Mathematics. — 1995. — Т. 57, вип. 2-3. — С. 133—144. — DOI:10.1016/0166-218X(94)00100-R..
6. M. Yannakakis, F. Gavril. Edge dominating sets in graphs // SIAM Journal on Applied Mathematics. — 1980. — Т. 38, вип. 3. — С. 364—372. — DOI:10.1137/0138030..
7. Y. Roichman. On the Achromatic Number of Hypercubes // Journal of Combinatorial Theory, Series B. — 2000. — Т. 79, вип. 2. — С. 177—182. — DOI:10.1006/jctb.2000.1955..

Посилання

• A compendium of NP optimization problems Архівовано травень 10, 2014 на сайті Wayback Machine.
• Кейта Едвардса