Жадібне розфарбовування

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

Два розфарбування жадібним алгоритмом одного і того ж графу, в яких використовується різний порядок проходження вершин. Правий приклад показує, що граф з n вершинами, який можна розфарбувати в два кольори, може бути розфарбований жадібним алгоритмом у кольорів.

Жадібні алгоритми не завжди доречні

Корона (повний дводольний граф Kn,n з віддаленими ребрами досконалого парування) є особливо незручним випадком для жадібного алгоритму — якщо в послідовності вершин помістити поспіль дві вершини, що належать віддаленому ребру з парування, жадібний алгоритм використовує n кольорів, в той час як оптимальним числом для такого графу є два кольори. Існують також графи, для яких, з великою ймовірністю, випадково обрана послідовність вершин призведе до використання числа кольорів, значно більшого ніж мінімально необхідної кількості[1]. Таким чином, дуже важливо дуже уважно обирати послідовність, в якій вершини проходяться жадібним алгоритмом.

Оптимальне упорядкування

Вершини будь-якого графу завжди можна впорядкувати таким чином, щоб жадібний алгоритм дав оптимальне розфарбування. Так, для оптимального розфарбування, перенумеруємо спочатку (в порядку спадання) вершини з найменшої за розміром множини однаково розфарбованих вершин. Потім перенумеруємо другу за розміром множину, і так далі. Якщо тепер застосувати жадібний алгоритм з таким порядком вершин, отримане розфарбування буде оптимальним. Більш строго, для графів, що мають досконалий порядок, існує порядок, який є оптимальним як для самого графу, так і для всіх його породжених підграфів[2]. Однак знаходження цього оптимального порядку для довільного графу є NP-повною задачею (хоча б тому, що її рішення можна використовувати для отримання оптимального розфарбування графу, тобто розв'язання NP-повної задачі), і визначення, чи існує в графі досконале впорядкування вершин, теж є NP-повною задачею[3]. З цієї причини для розфарбовування графу з метою зменшення числа кольорів використовуються евристичні алгоритми, хоча вони і не дають оптимальне число кольорів.

Евристичні стратегії упорядкування

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

Для графу з максимальним степенем Δ будь-який жадібний алгоритм використовує максимум Δ + 1 кольорів. Теорема Брукса стверджує, що за винятком двох винятків (кліки та непарні цикли) для розфарбовування необхідно не більше Δ кольорів. Один із доказів теореми Брукса використовує впорядкування вершин, при якому перші дві вершини є суміжними до кінцевої вершині, але не є суміжними між собою. В такій послідовності для кожної вершини є щонайменше одна попередню вершину, що належить околиці. Для послідовності вершин з такими властивостями жадібний алгоритм використовує максимум Δ кольорів.[4].

Альтернативні схеми вибору кольорів

Можна побудувати жадібний алгоритм, в якому вершини заданого графу розфарбовуються у заздалегідь визначеній послідовності, але в якому колір обирається не обов'язково перший доступний з вільних кольорів. Як альтернативна стратегія вибору кольору вивчалися підходи з онлайновими алгоритмами. У задачі онлайнового розфарбовування графу вершини графу піддаються алгоритму розфарбовування послідовно по одній в довільному порядку. Алгоритм повинен обрати колір кожної вершини, спираючись лише на кольори та суміжність вже оброблених вершин. У цьому контексті якість стратегії вибору кольорів вимірюється конкурентним відношенням, відношенням числа використаних кольорів до оптимального числа кольорів розфарбування графу.

Якщо не задано жодних інших обмежень на графі, оптимальне конкурентне відношення є лише дещо сублінійним[5]. Однак для інтервальних графів як конкурентне відношення можлива константа[6], в той час як для дводольних і розріджених графів можна отримати логарифмічне відношення[7]. Більш того, для розріджених графів звичайна стратегія вибору першого доступного кольору дає цю оцінку та можна показати, що ця оцінка є нижньою для конкурентного відношення будь-якого онлайнового алгоритму розфарбовування[7].

Примітки
  1. Kučera, 1991.
  2. Chvátal, 1984.
  3. Middendorf, Pfeiffer, 1990.
  4. Lovász, 1975.
  5. Lovász, Saks, Trotter, 1989; Vishwanathan, 1990.
  6. Kierstead, Trotter, 1981.
  7. Irani, 1994.

Посилання
  • Václav Chvátal. Topics in Perfect Graphs / Claude Berge, Václav Chvátal. — Amsterdam : North-Holland, 1984. — Т. 21. — С. 63-68. — (Annals of Discrete Mathematics). Як цитовано в Maffray, 2003.
  • Sandy Irani. Coloring inductive graphs on-line // Algorithmica. — 1994. — Т. 11, вип. 1. — С. 53-72. — DOI:10.1007/BF01294263..
  • H. A. Kierstead, W. A. Trotter. An extremal problem in recursive combinatorics // Congress. Numer.. — 1981. — Т. 33. — С. 143-153.. Як цитовано в Irani, 1994.
  • Luděk Kučera. The greedy coloring is a bad probabilistic algorithm // Journal of Algorithms. — 1991. — Вип. 4. — С. 674-684. — DOI:10.1016/0196-6774 (91) 90040-6..
  • D. S. Johnson. Proc. 5th Southeastern Conf. Combinatorics, Graph Theory and Computation. — Winnipeg : Utilitas Mathematica, 1979. — С. 513-527.. Як цитовано в Maffray, 2003.
  • L. Lovász. Three short proofs in graph theory // Journal of Combinatorial Theory, Series B. — 1975. — Вип. 3. — С. 269-271. — DOI:10.1016/0095-8956 (75) 90089-1..
  • L. Lovász, M. E. Saks, W. A. Trotter. An on-line graph coloring algorithm with sublinear performance ratio // Discrete Mathematics. — 1989. — Вип. 1-3. — С. 319-325. — DOI:10.1016/0012-365X(89) 90096-4..
  • Frédéric Maffray. Recent Advances in Algorithms and Combinatorics / Bruce A. Reed, Sales Cláudia L. — Springer-Verlag, 2003. — С. 65-84. — (CMS Books in Mathematics) — ISBN 0-387-95434-1. — DOI:10.1007/0-387-22444-0_3..
  • Matthias Middendorf, Frank Pfeiffer. On the complexity of recognizing perfectly orderable graphs // Discrete Mathematics. — 1990. — Вип. 3. — С. 327-333. — DOI:10.1016/0012-365X(90) 90251-C..
  • Maciej M. Sysło. Sequential coloring versus Welsh-Powell bound // Discrete Mathematics. — 1989. — Вип. 1-2. — С. 241-243. — DOI:10.1016/0012-365X(89) 90212-4..
  • S. Vishwanathan. Proc. 31st IEEE Symp. Foundations of Computer Science (FOCS '90). — 1990. — С. 464-469. — ISBN 0-8186-2082-X. — DOI:10.1109/FSCS.1990.89567..
  • D. J. A. Welsh, M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems // The Computer Journal. — 1967. — Вип. 1. — С. 85-86. — DOI:10.1093/comjnl/10.1.85..
  • Manouchehr Zaker. Results on the Grundy chromatic number of graphs // Discrete Mathematics. — 2006. — Вип. 2-3. — С. 3166-3173. — DOI:10.1016/j.disc.2005.06.044..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.