Loading AI tools
З Вікіпедії, вільної енциклопедії
Жадібне розфарбування в теорії графів — розфарбування вершин неорієнтованого графа, створене жадібним алгоритмом, який проходить вершини графа в деякій визначеній послідовності та призначає кожній вершині перший доступний колір. Жадібні алгоритми, в загальному випадку, не дають мінімально можливе число кольорів, однак вони використовуються в математиці як техніка доказів інших результатів, що належать до розфарбування, а також у комп'ютерних програмах для отримання розфарбування з невеликим числом кольорів.
Жадібне розфарбування для заданого порядку вершин можна виконати за допомогою алгоритму, що виконується за лінійний час. Алгоритм обробляє вершини в заданому порядку, призначаючи колір для кожної з них. Кольори можуть бути представлені цифрами: . Кожній вершині надається колір з найменшим номером, який ще не використовується одним з її сусідів. Щоб знайти найменший доступний колір, можна використати масив для підрахунку кількості сусідів кожного кольору, а потім сканувати масив, щоб знайти індекс його першого нуля, який і вкаже на колір, який має нульову кількість сусідів.[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] полягає у виборі множин вершин кожного кольору, по одному кольору за раз. У цьому методі кожен колір класу обирається скануванням вершин у заданому порядку. Коли це сканування зустрічає незафарбовану вершину , що немає сусіда, то додається у . Таким чином, стає максимальною незалежною множиною серед вершин, яким ще не були призначені менші кольори. Алгоритм постійно знаходить класи кольорів даним способом, доки всі вершини не будуть зафарбовані. Однак даний метод передбачає виконання кількох сканувань графа, одне сканування для кожного класу кольорів, замість першого методу, що використовує лише одне сканування.[3]
Корона (повний двочастковий граф Kn,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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
