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

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

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

Алгоритм

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

Приклад алгоритму написаного на 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 займає час, пропорційний довжині списку її аргументів, оскільки вона виконує два цикли, один над самим списком, а інший над списком лічильників, який має таку ж довжину. Час загального алгоритму розфарбовування перебільшує виклики цієї підпрограми. Кожне ребро в графі сприяє лише одному з цих викликів. В свою чергу виклик відбувається для кінцевої точки ребра, яке є пізнішим у порядку вершин. Таким чином, сума довжин списків аргументів first_available та загальний час алгоритму пропорційні кількості ребер у графі.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Посилання

• 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.