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

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

Алгоритм

Жадібне розфарбування для заданого порядку вершин можна виконати за допомогою алгоритму, що виконується за лінійний час. Алгоритм обробляє вершини в заданому порядку, призначаючи колір для кожної з них. Кольори можуть бути представлені цифрами: $0,1,2,\dots$ . Кожній вершині надається колір з найменшим номером, який ще не використовується одним з її сусідів. Щоб знайти найменший доступний колір, можна використати масив для підрахунку кількості сусідів кожного кольору, а потім сканувати масив, щоб знайти індекс його першого нуля, який і вкаже на колір, який має нульову кількість сусідів.^[1]

Приклад алгоритму написаного на Python:

def first_available(color_list):
    """Повертає найменше невід’ємне ціле число, якого немає в заданому списку кольорів."""
    color_set = set(color_list)
    count = 0
    while True:
        if count not in color_set:
            return count
        count += 1
        
def greedy_color(G, order):
    """Знаходить жадібне розфарбування G у заданому порядку.
    Припускається, що представлення G виглядає як https://www.python.org/doc/essays/graphs/
    Що дозволяє перебирати сусідів вузла/вершини за допомогою "for w in G[node]".
    Значення, що повертається, — це словник, який зв'язує вершини з їх кольорами."""
    color = dict()
    for node in order:
        used_neighbour_colors = [color[nbr] for nbr in G[node]
                                 if nbr in color]
        color[node] = first_available(used_neighbour_colors)
    return color

Функція first_available отримує на вхід список кольорів та за допомогою перебору знаходить найменший колір, якого немає у списку. Підпрограма greedy_color перебирає всі вершини і для кожної підраховує список використаних кольорів сусідніми вершинами та викликає метод first_available з цим списком, щоб знайти найменший доступний колір. Таким чином, кожна вершина буде зафарбона іншим кольором ніж її сусіди. Сума довжин списків аргументів first_available та загальний час алгоритму пропорційні кількості ребер у графі.^[1]

Альтернативний алгоритм, який створює жадібне розфарбування,^[2] полягає у виборі множин вершин кожного кольору, по одному кольору за раз. У цьому методі кожен колір класу $C$ обирається скануванням вершин у заданому порядку. Коли це сканування зустрічає незафарбовану вершину $v$ , що немає сусіда, то $v$ додається у $C$ . Таким чином, $C$ стає максимальною незалежною множиною серед вершин, яким ще не були призначені менші кольори. Алгоритм постійно знаходить класи кольорів даним способом, доки всі вершини не будуть зафарбовані. Однак даний метод передбачає виконання кількох сканувань графа, одне сканування для кожного класу кольорів, замість першого методу, що використовує лише одне сканування.^[3]

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

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

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

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

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

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

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

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

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

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

Програмні застосунки

Жадібне фарбування працює швидко і в багатьох випадках може використовувати невелику кількість кольорів. Тому, його можна використовувати в програмах, де потрібне хороше, але не оптимальне розфарбування графа. Один з перших додатків застосовуючих жадібний алгоритм був написаний для вирішення такої проблеми, як планування курсу, у якому набір завдань мав відповідати заданому набору часових інтервалів, уникаючи призначення несумісних завдань одному часовому інтервалу.^[3] Жадібне фарбування також можна використовувати в компіляторах для розподілу регістрів, застосовуючи його до графа, вершини якого відповідають значенням, які призначаються регістрам, а ребра відповідають конфліктам між двома значеннями, які не можуть бути призначені одному регістру.^[11] У багатьох випадках ці інтерференційні графи є хордальними, що дозволяє алгоритму створювати оптимальне призначення регістра. ^[12]

У комбінаторній теорії ігор для неупередженої гри, заданої в явній формі як спрямований ациклічний граф, вершини якого представляють ігрові позиції, а ребра представляють дійсні переходи з однієї позиції в іншу, алгоритм жадібного фарбування (використовуючи зворотнє топологічне сортування графа) обчислює нім-значення кожної позиції. Ці значення можна використовувати для визначення оптимальної гри в будь-якій окремій грі або будь-якій диз’юнктивній сумі ігор. ^[13]

Примітки

Посилання

Chinh T Hoàng , R. Sritharan. Handbook of Graph Theory, Combinatorial Optimization, and Algorithms. — CRC Press, 2016. — Т. 34. — С. 707–750. — (Chapman & Hall/CRC Computer and Information Science Series) — ISBN 9781420011074.
Alan Frieze , Colin McDiarmid. An upper bound for the chromatic number of a graph and its application to timetabling problems // Random Structures & Algorithms. — 1997. — Вип. 1–2. — С. 5–42. — DOI:10.1002/(SICI)1098-2418(199701/03)10:1/2<5::AID-RSA2>3.3.CO;2-6..
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..
Massimiliano Poletto , Vivek Sarkar. Linear scan register allocation // ACM Transactions on Programming Languages and Systems. — Вип. 5. — С. 895–913. — DOI:10.1145/330249.330250..
Fernando Magno Quintão Pereira , Jens Palsberg. Programming Languages and Systems: Third Asian Symposium, APLAS 2005, Tsukuba, Japan, November 2–5, 2005, Proceedings. — Springer, 2005. — Т. 3780. — С. 315–329. — (Lecture Notes in Computer Science) — DOI:10.1007/11575467_21.
Gabriel Nivasch. The Sprague–Grundy function of the game Euclid // Discrete Mathematics. — 2006. — Вип. 21. — С. 2798–2800. — DOI:10.1016/j.disc.2006.04.020..

[FOOTNOTEHoàng_&_Sritharan2016-1] а ^б Hoàng & Sritharan, 2016.

[FOOTNOTEFrieze_&_McDiarmid1997-2] Frieze & McDiarmid, 1997.

[FOOTNOTEWelsh,_Powell1967-3] а ^б Welsh, Powell, 1967.

[FOOTNOTEKučera1991-4] Kučera, 1991.

[FOOTNOTEChvátal1984-5] Chvátal, 1984.

[FOOTNOTEMiddendorf,_Pfeiffer1990-6] Middendorf, Pfeiffer, 1990.

[FOOTNOTELovász1975-7] Lovász, 1975.

[8] Lovász, Saks, Trotter, 1989; Vishwanathan, 1990.

[FOOTNOTEKierstead,_Trotter1981-9] Kierstead, Trotter, 1981.

[FOOTNOTEIrani1994-10] а ^б Irani, 1994.

[FOOTNOTEPoletto_&_Sarkar-11] Poletto & Sarkar.

[FOOTNOTEPereira_&_Palsberg2005-12] Pereira & Palsberg, 2005.

[FOOTNOTENivasch2006-13] Nivasch, 2006.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]