У теорії графів повне розфарбування — це протилежність гармонійному розфарбуванню в тому сенсі, що це розфарбування вершин, у якому кожна пара кольорів зустрічається принаймні на одній парі суміжних вершин. Еквівалентно, повне розфарбування — це мінімальне розфарбування, в тому сенсі, що його не можна перетворити на правильне розфарбування з меншим числом кольорів злиттям двох кольорів. Ахроматичне число графа — це найбільше число кольорів серед усіх повних розфарбувань графа .
Теорія складності
Знаходження є задачею оптимізації. Проблему розв'язності для повного розфарбування можна сформулювати як:
- ДАНО: Граф і додатне ціле число
- Питання: Чи існує розбиття множини вершин на або більше неперетинних множин таких, що кожне є незалежною множиною для і таких, що для кожної пари різних множин незалежною множиною не є.
Визначення ахроматичного числа є NP-складною задачею. Визначення, чи не буде ахроматичне число більшим від заданого числа є NP-повною задачею, як показали Янакакіс і Гаврил (Yannakakis, Gavril) 1978 року, перетворивши з задачі пошуку мінімального найбільшого парування.
Зауважимо, що будь-яке розфарбування графа з найменшим числом кольорів має бути повним розфарбуванням, так що мінімізація числа кольорів повного розфарбування є просто переформулюванням стандартної задачі розфарбовування графа.
Алгоритм
Оптимізаційна задача допускає апроксимацію з гарантованою ефективністю .
Окремі випадки графів
Задача визначення ахроматичного числа залишається NP-повною також для деяких класів графів: двочасткових графів, доповнення двочасткових графів (тобто, графи, які не мають незалежної множини з більш ніж двома вершинами), кографи, інтервальні графи і навіть дерева.
Для доповнень дерев ахроматичне число можна обчислити за поліноміальний час. Для дерев задачу можна апроксимувати зі сталим коефіцієнтом.
Відомо, що ахроматичне число n-вимірного графа гіперкуба пропорційне , але точний коефіцієнт пропорційності невідомий.
Див. також
- Гармонійне розфарбування
- (Тотальне розфарбування)
- (Т-розфарбування)
Примітки
- [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.
- Amitabh Chaudhary, Sundar Vishwanathan. Approximation algorithms for the achromatic number // Journal of Algorithms. — 2001. — Т. 41, вип. 2. — С. 404—416. — DOI: ..
- 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: ..
- H. Bodlaender. Achromatic number is NP-complete for cographs and interval graphs // Inform. Proc. Lett.. — 1989. — Т. 31, вип. 3. — С. 135—138. — DOI: ..
- D. Manlove, C. McDiarmid. The complexity of harmonious coloring for trees // Discrete Applied Mathematics. — 1995. — Т. 57, вип. 2-3. — С. 133—144. — DOI: ..
- M. Yannakakis, F. Gavril. Edge dominating sets in graphs // SIAM Journal on Applied Mathematics. — 1980. — Т. 38, вип. 3. — С. 364—372. — DOI: ..
- Y. Roichman. On the Achromatic Number of Hypercubes // Journal of Combinatorial Theory, Series B. — 2000. — Т. 79, вип. 2. — С. 177—182. — DOI: ..
Посилання
- A compendium of NP optimization problems Архівовано травень 10, 2014 на сайті Wayback Machine.
- Кейта Едвардса
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет