Лекция
Привет, сегодня поговорим про раскраска графов, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое раскраска графов, алгоритм раскраски графа, практическое применение раскраски графов , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
Корректная раскраска вершин графа наименьшим набором цветов — тремя.
В теории графов раскраска графов является частным случаем разметки графов. При раскраске элементам графа ставятся в соответствие метки с учетом определенных ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называетсяраскраской вершин. Аналогично раскраска ребер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Раскраска вершин — главная задача раскраски графов, все остальные задачи в этой области могут быть сведены к ней. Например, раскраска ребер графа — это раскраска вершин его реберного графа, а раскраска областей планарного графа — это раскраска вершин его двойственного графа. Тем не менее, другие проблемы раскраски графов часто ставятся и решаются в изначальной постановке. Причина этого частично заключается в том, что это дает лучшее представление о происходящем и более показательно, а частично из-за того, что некоторые задачи таким образом решать удобнее (например, раскраска ребер).
Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломке Судоку. В этой области все еще ведутся активные исследования.
Первые результаты были получены для плоских графов в задаче раскрашивания карт. Пытаясь раскрасить карту округов Англии, Францис Гутри сформулировалпроблему четырех красок, отметив, что четырех цветов достаточно, чтобы раскрасить карту так, чтобы любые два смежных региона имели разные цвета. Его брат передал вопрос своему учителю по математике, Огастесу де Моргану, который упомянул о нем в своем письме Уильяму Гамильтону в 1852 году. Артур Кэли поднял эту проблему на встрече Лондонского математического сообщества в 1878 году. В том же году Тэйтом было предложено первое решение этой задачи. Раскраску вершин первоначального графа он свел к раскраске ребер двойственного графа и предположил, что эта задача всегда имеет решение. В 1880 году Альфред Кемпеопубликовал статью, в которой утверждалось, что ему удалось установить результат, и на десятилетие проблема четырех цветов считалась решенной. За это достижение Кемпе был избран членом Лондонского Королевского общества и позже — президентом Лондонского математического сообщества.
В 1890 году Хивуд нашел ошибку в доказательстве Кемпе. В этой же статье он доказал теорему пяти красок, показав, что любая плоская карта может быть раскрашена не более, чем пятью цветами. При этом он опирался на идеи Кемпе. В следующем столетии было разработано большое количество теорий в попытках уменьшить минимальное число цветов. Теорема четырех красок была окончательно доказана в 1977 году учеными Кеннетом Аппелем и Вольфгангом Хакеном с использованием компьютерного перебора. Идея доказательства во многом опиралась на идеи Хивуда и Кемпе и игнорировала большинство промежуточных исследований. Доказательство теоремы четырех красок является одним из первых доказательств, в которых был использован компьютер.
В 1912 году Джордж Дэвид Биркхоф предложил использовать для изучения задач раскраски хроматический многочлен, являющийся важной частью в алгебраической теории графов. Хроматический многочлен впоследствии был обобщен Уильямом Татом (многочлен Татта). Кемпе в 1879 году уже обращал внимание на общий случай, когда граф не являлся плоским. Много результатов обобщений раскраски плоских графов на поверхности более высоких порядков появилось в начале 20 века.
В 1960 году Клод Бердж сформулировал гипотезу о совершенных графах, мотивированное понятием из теорим информации, а именно нулевой ошибкой емкости графа , представленным Шенноном. Утверждение оставалось неподтвержденным на протяжении 40 лет, пока не было доказано как знаменитая строгая теорема о совершенных графах математиками Чудновской, Робертсоном, Сэймуром и Томасом в 2002 году.
Раскраска графов как алгоритмическая проблема начала изучаться с 1970-х годов: определение хроматического числа — входит в число 21 NP-полных задач Карпа(1972). И примерно в то же время были разработаны разнообразные алгоритмы на базе поиска с возвратом и рекурсивного удаления и стягивания Зыкова. С 1981 года раскраска графа применяется для распределения регистров в компиляторах.
Этот граф может быть раскрашен 3 цветами 12 способами.
Когда говорят о раскраске графов, почти всегда подразумевают под этим раскраску их вершин, то есть присвоение цветовых меток вершинам графа так, чтобы любые две вершины, имеющие общее ребро, имели разные цвета. Так как графы, в которых есть петли, не могут быть раскрашены таким образом, они не являются предметом обсуждения.
Терминология, в которой метки называются цветами, происходит от раскраски политических карт. Такие метки как красный или синий используются, только когда число цветов мало, обычно же подразумевается, что метки являются целыми числами 
.
Раскраска с использованием 
цветов называется -раскраской. Наименьшее число цветов, необходимое для раскраски графа 
, называется его хроматическим числом и часто записывается как 
. Иногда используется 
, с тех пор как обозначает Эйлерову характеристику. Подмножество вершин, выделенных одним цветом, называется цветовым классом, каждый такой класс формирует независимый набор. Таким образом, -раскраска — это то же самое, что и разделение вершин на независимых наборов.
Хроматический многочлен — это функция 
, которая считает число t-раскрасок графа . Из названия следует, что для заданных эта функция — полином, зависящий от t. Этот факт был обнаружен Биркгофом и Льюисом при попытке доказать гипотезу четырех красок.
Все не изоморфныеграфы из 3 вершин и их хроматические многочлены. Пустой графE3 (красный) допускает раскраску одним цветом, остальные — нет. Зеленый граф может быть раскрашен 3 цветами 12 способами.
Например, граф на изображении справа может может быть раскрашен 12 способами с использованием 3 цветов. Двумя цветами он не может быть окрашен в принципе. Используя 4 цвета, мы получаем 24+4*12 = 72 вариантов раскраски: при использовании всех 4 цветов, есть 4! = 24 корректных способа (каждое присвоение 4 цветов для любого графа из 4 вершин является корректным); и для каждых 3 цветов из этих 4 есть 12 способов раскраски. Тогда, для графа в примере, таблица чисел корректных раскрасок будет начинаться так:
| Доступное число цветов | 1 | 2 | 3 | 4 | … |
| Количество способов раскраски | 0 | 0 | 12 | 72 | … |
Для графа в примере, 
, и конечно, 
.
Хроматический многочлен содержит по меньшей мере столько же информации о раскрашиваемости , сколько и хроматическое число. В самом деле, 
— наименьшее целое положительное число, не являющееся корнем хроматического многочлена.
Треугольный  |
 |
Полный граф  |
 |
Дерево с  ребрами |
 |
Цикл  |
 |
| Граф Петерсена |  |
Реберная раскраска графа подразумевает под собой назначение цветов ребрам так, что никакие два ребра одного цвета не принадлежат одной вершине. Эта задача эквивалентна разделению множества граней на множества независимых граней. Наименьшее число цветов, необходимое для реберной раскраски графа — это его хроматический индекс, или реберное хроматическое число, 
.
Тотальная раскраска — это один из видов раскраски вершин и ребер графа. Под ней подразумевают такое присвоение цветов, что ни соседние вершины, ни смежные ребра, ни вершины и ребра, которые их соединяют, не имеют одинакового цвета. Полное хроматическое число 
графа — это наименьшее число цветов, необходимое для любой полной раскраски.
— пустой граф [],
— объединение непересекающихся подграфов 
и 
[10],
есть петля [],
, состоящий из вершин требует 
цветов.
ребер графа между каждыми двумя цветовыми классами, так что [11]
является объединением непересекающихся подграфов и , то
содержит клики размера k, тогда необходимо минимум k цветов для раскраски этой клики, другими словами хроматическое число больше, либо равнокликовому числу:
Для интервальных графов это ограничение точно.
Граф является двудольным в том и только в том случае, если он не содержит циклов нечетной длины.[10]
и 
, графы-циклы имеют 
и 
, так что для них это ограничение является наилучшим, во всех других случаях, ограничение может быть улучшено: теорема Брукса[12] утверждает, что
для связанного, простого граф , если не является ни полным графом, ни графов-циклом.
Теорема Мычельского (Александр Зыков 1949, Ян Мычельский,1955): Существуют графы без треугольников со сколь угодно большими хроматическими числами.
Теорема Эрдеша: Существуют графы со сколь угодно большим обхватом и хроматическим числом. Об этом говорит сайт https://intellect.icu . [11]
— это раскраска вершин его линейного графа 
. То есть
Теорема Кенига: 
, если — двудольный.
Теорема Визинга: Граф с максимальной степенью вершины 
имеет реберное хроматическое число или 
.
k-хроматические, то и тоже является k-хроматическим (доказывается при предположении аксиомы выбора). Это — формулировка теоремы Де Брейна–Эрдеша[15].
, то он допускает бесконечную полную раскраску.[Хроматическое число плоскости, в которой две точки являются смежными, если между ними единичное расстояние, неизвестно. Оно может быть равным 4, 5, 6, или 7. Другие открытые вопросы о хроматическом числе графов включают в себя гипотезу Хадвигера, утверждающую, что любой граф с хроматическим числом k имеет полный граф из k вершин, как его минор, гипотезу Эрдеша–Фабера–Ловаса, которая ограничивает хроматическое число полных графов, которые имеют ровно одну общую вершину для каждой пары графов, и гипотезу Альбертсона о том, что среди k-хроматических графов полными являются те, которые имеют наименьшеечисло пересечений.
Когда Бирков и Льюис представили хроматический многочлен в их попытке решить теорему четырех цветов, они утверждали, что для плоских графов многочлен не имеет нулей в области 
. Хотя известно, что такой хроматический многочлен не имеет нулей в области 
, и что 
, их утверждение остается недоказанным. Так же остается открытым вопрос, как отличать графы с одинаковым хроматическим многочленом, и как определять, что многочлен является хроматическим.
Для двудольного графа задача раскраски вычисляется за линейное время с помощью поиска в ширину. В случае совершенных графов, хроматическое число и соответствующая ему раскраска может быть найдена за полиномиальное время при использовании полуопределенного программирования. Точные формулы для нахождения хроматического числа известны для многих классов графов (леса, циклы, колеса, хордальные графы) и так же могут быть вычислены за полиномиальное время.
Алгоритм полного перебора для случая k-раскраски рассматривает все }
комбинаций расстановки цветов в графе с n вершинами и проверяет их на корректность. Чтобы вычислить хроматическое число и хроматический полином, данный алгоритм рассматривает каждое k от 1 до n. Такой алгоритм на практике может быть применим только для небольших графов.
Используя динамическое программирование и оценку размера наибольшего независимого множества, в графе возможность k-раскраски может быть разрешена за время 
[17]. Известны более быстрые алгоритмы для 3- и 4-раскрасок, работающие за время 
[18] и 
[19] соответственно.
Стягивание вершин — это операция, которая из графа делает граф 
, отождествляя вершины 
и 
, удаляя соединяющих их ребра, и заменяя на одну вершину 
, куда перенаправляются ребра инцидентные вершинам и . Эта операция играет важную роль в анализе раскраски графов.
Хроматическое число удовлетворяет рекуррентному соотношению:
,
где и несмежные вершины, 
граф с добавленным ребром 
. Некоторые алгоритмы основаны на данном соотношении, выдавая как результат дерево, иногда называемое деревом Зыкова. Время выполнения зависит от метода выбора вершин и .
Хроматический полином удовлетворяет рекуррентному соотношению:
,
где и смежные вершины, 
граф с удалением ребра . 
представляет собой число возможных правильных раскрасок графа, когда вершины и могут иметь одинаковые или различные цвета. Если и имеют разные цвета, тогда мы можем рассмотреть граф, где и смежные. Если и имеют одинаковые цвета, мы можем рассмотреть граф, где и объединены.
Выражения данные выше приводят к рекурсивной процедуре, названной алгоритм удаления и стягивания, сформировавшей основу для многих алгоритмов раскраски графов. Время работы удовлетворяет такому же рекуррентному соотношению, как и числа Фибоначчи, поэтому в наихудшем случае алгоритм будет работать за время 
для n вершин и m ребер.[20] На практике, метод ветвей и границ и отбрасывание изоморфных графов позволяет избежать некоторых рекурсивных вызовов, время работы зависит от метода подбора пары вершин.
Два результата работы жадного алгоритма при выборе разных порядков вершин.
Жадный алгоритм упорядочивает вершины 
,…, 
и последовательно присваивает вершине 
наименьший доступный цвет, не использовавшийся для окраски соседей среди ,…,{ 
, либо добавляет новый. Качество полученной раскраски зависит от выбранного порядка. Всегда существует такой порядок, который приводит жадный алгоритм к оптимальному числу красок. С другой стороны, жадный алгоритм может быть сколь угодно плохим; например, корона с n вершинами может быть раскрашена 2 цветами, но существует порядок вершин, который приводит к жадной раскраске из }
цветов.
Для хордального графа и для его особых случаев (например, интервальный граф) алгоритм жадной раскраски может быть использован для нахождения оптимальной раскраски за полиномиальное время, выбирая порядок вершин обратным ксовершенному порядку исключения. Этот алгоритм может применен и к более широкому классу графов (совершенно упорядочиваемые графы), однако найти такой порядок для таких графов — NP-сложная задача.
Если вершины упорядочены в соответствии с их степенями, алгоритм жадной раскраски использует не более чем 
цветов, что максимум на 1 больше, чем (здесь 
— степень вершины ). Этот эвристический алгоритм иногда называют алгоритмом Уэлша-Пауэлла.[21] Другой алгоритм устанавливает порядок динамично, выбирая следующую вершину той, которая имеет наибольшее число смежных вершин разных цветов. Многие другие алгоритмы раскраски графов основаны на жадной раскраске и используют статические или динамические стратегии выбора порядка вершин.
В области распределенных алгоритмов встречается аналогичная задача. Допустим, вершины графа — это компьютеры, которые могут общаться между собой, если они соединены ребром. Задача состоит в том, чтобы каждый компьютер выбрал для себя «цвет», так, чтобы соседние компьютеры выбрали разные цвета. Эта задача тесно связана с проблемой нарушения симметрии. Наиболее развитые вероятностные алгоритмы работают быстрее, чем детерминированные алгоритмы для графов с достаточно большой максимальной степени вершин . Наиболее быстрые вероятностные алгоритмы используют технику множественных попыток[22].
В симметричных графах детерминированные распределенные алгоритмы не могут найти оптимальную раскраску вершин. Нужна дополнительная информация, чтобы избежать симметрии. Делается стандартное предположение, что первоначально каждая вершина имеет уникальный идентификатор, например, из множества 
. Иными словами, предполагается, что нам дана n-раскраска. Задача состоит в том, чтобы уменьшить количество цветов от n до, например, 
. Чем больше цветов используются (например, 
вместо }), тем меньше обменов сообщений потребуется[22].
Простая версия распределенного жадного алгоритма для -раскраски требует 
раундов связи в худшем случае — информации, возможно, придется проходить с одного конца стороны сети до другого.
Наиболее простым интересным случаем является n-цикл. Ричард Коул и Узи Вишкин[23] показали, что существует распределенный алгоритм, который уменьшает количество цветов от n до 
, используя лишь один раз обмен сообщениями между соседями. Повторяя ту же процедуру, можно получить 3-раскраску n-цикла за 
раундов связи (при условии, что даны уникальные идентификаторы узлов).
Функци 
, итерированный логарифм, является чрезвычайно медленно растущей функцией, «почти константа». Следовательно, результаты Коула и Вишкина поднимают вопрос о том, есть ли распределенный алгоритм 3-раскраски n-цикла, который выполняется за константное время. Натан Линиал показал, что это невозможно: любой детерминированный распределенный алгоритм требует 
раундов связи для уменьшения N-раскраски до 3-раскраски в n-цикле.[24]
Техника Коула и Вишкина также может быть применена для произвольного графа с ограниченной степенью вершин, в этом случае время работы составляет 
.[25] Этот метод был обобщен для графа единичных кругов Шнайдером и др.[26]
Проблема раскраски ребер также изучалась в распределенной модели. Пансонецци и Рицци достигли 
-раскраски за 
в этой модели.[27]Нижняя граница для распределенной раскраски вершин, достигнутая Линиалом, также применима для задачи распределенной раскраски ребер.[24]
Децентрализованными называются алгоритмы, в которых не разрешена внутренняя передача сообщений (в отличие от распределенных алгоритмов, где процессы обмениваются между собой данными). Существуют эффективные децентрализованные алгоритмы, успешно справляющиеся с задачей раскраски графов. Эти алгоритмы работают в предположении, что вершина способна «чувствовать», что какая-либо из ее соседних вершин раскрашена в тот же цвет, что и она. Другими словами, есть возможность определить локальный конфликт. Такое условие довольно часто выполняется в реальных прикладных задачах — например, при передаче данных по беспроводному каналу передающая станция, как правило, имеет возможность детектировать, что другая станция пытается передавать одновременно в тот же канал. Способности к получению подобной информации достаточно для того, чтобы алгоритмы, основанные на обучающихся автоматах, с вероятностью единица правильно решат задачу раскраски графа
Раскраска графа является вычислительно сложной задачей. Узнать, допускает ли граф k7-раскраску для заданного k — это NP-полная задача, кроме случаев k = 1 и k = 2. В частности, задача вычисления хроматического числа NP-сложна.[30] Задача о 3-раскраске NP-полная даже для случая планарного графа степени 4
Также NP-сложной задачей является раскраска 3-раскрашиваемого графа 4 цветами [32] и k-раскрашиваемого графа 
при достаточно больших значениях k.[33]
Вычисление коэффициентов хроматического полинома #P-сложная задача. Доказано, что не существует ни одного FPRAS-алгоритма для вычисления хроматического полинома ни для какого рационального числа k ≥ 1,5, кроме k = 2, если только не выполнится, что NP = RP.
Раскраска вершин моделирует многие проблемы планирования.[35] В своей простейшей постановке заданный набор работ должен быть распределен по временным отрезкам, каждая такая работа занимает один отрезок. Они могут быть выполнены в любом порядке, но две работы могут конфликтовать в том смысле, что не могут быть выполнены одновременно, так как, например, используют общие ресурсы. Соответствующий граф содержит вершину для каждой из работ и ребро для каждой конфликтующий пары. Хроматическое число построенного графа — это минимальное время выполнения всех работ без конфликтов.
Детали проблемы планирования определяют структуру графа. Например, когда идет распределение самолетов по рейсам, результирующий граф конфликтов являетсяинтервальным графом, так что проблема раскраски может быть решена эффективно. При распределении радиочастот получается граф единичных кругов конфликтов, и для такой задачи существует 3-аппроксимационный алгоритм.
Компилятор — это компьютерная программа, которая переводит один компьютерный язык в другой. Для улучшения времени выполнения результирующего кода одной из техник компиляторной оптимизации, является распределение регистров, в которой наиболее часто используемые переменные компилируемой программы хранятся в быстродействующих регистрах процессора. В идеальном случае переменные хранятся в регистрах так, что они все находятся в регистрах во время их использования.
Стандартный подход к этой задаче состоит в сведении ее к задаче раскраски графов. Компилятор строит интерференционный граф, где вершины соответствуют регистрам, а грань соединяет две из них, если они нужны в один и тот же момент времени. Если этот граф k-хроматический, то переменные могут храниться в k-регистрах.
Технология цифровых водяных знаков (англ. digital watermarking) позволяет вместе с данными (будь то медиафайлы, исполняемые файлы и прочие) передать некое скрытое сообщение («водяной знак», Watermark). Такое скрытое сообщение может быть применено в защите авторских прав для идентификации владельца данных.
Это важно, например, для установления источника их распространения нелегальным образом. Или же для подтверждения прав на данные, например — программное обеспечение систем на кристалле (system-on-chip).
Сообщение можно закодировать в том числе и в способе распределения регистров. Одну из таких техник предложили Qu и Potkonjak[36] (поэтому ее иногда называют QP-алгоритмом).
Состоит она вот в чем: пусть — граф несовместимости (интерференционный граф) распределения регистров процессора, о котором говорилось выше. Его раскраска используется в программе — причем, используется так, что допустимо поменять содержимое графа с небольшим увеличением его хроматического числа. Оказывается возможно закодировать послание в программном продукте с помощью раскраски графа , то есть распределения регистров.
Извлечь это сообщение можно путем сравнением распределения регистров с исходной раскраской;[37] существуют и способы удостовериться в том, было ли некое сообщение закодировано в программе без использования исходного.
В дальнейшем разные авторы развивали и уточняли идеи Qu и Potkonjak.
Задача раскраски графов была поставлена во многих других областях применения, включая сопоставление с образцом.
Решение головоломки Судоку можно рассматривать как завершение раскраски 9 цветами заданного графа из 81 вершины.
Раскраски графов(продолжение) алгоритм раскраски графа .
Разнообразные задачи, возникающие при планировании производства, составлении графиков осмотра, хранении и транспортировке товаров и т. д., могут быть представлены часто как задачи теории графов, тесно связанные с так называемой «задачей раскраски». Графы, рассматриваемые в этой части, являются неориентированными и не имеют петель.
Пусть G = (V, Е) — произвольный граф и {ci, ..., ct} — некоторое множество, элементы которого будем называть красками. t-раскраской графа G называется отображение ф из V В {ci, ..., ct} такое, что для любых двух различных смежных вершин и и v графа G выполняется ф(u) != ф(v).
Отметим, что здесь не предполагается, что ф отображает V на все множество красок {ci, ..., ct}. Будем говорить, что цвет ф(v) приписан вершине v G V или вершина v имеет цвет ф(v). Мы видим, что t-раскраска графа G приписывает каждой его вершине один из t заданных цветов таким образом, что любые две различные смежные вершины имеют разный цвет.
Трехцветовая раскраска графа Петерсена
Граф называется t-раскрашиваемым, если он обладает t-раскраской. Граф называется t-хроматическим, если он t-раскрашиваемый, но не является (t — 1)-раскрашиваемым; число t в таком случае называют хроматическим числом графа G и обозначают через x(G).
Заметим, что
1) 1-хроматичсскис графы — это нулевые графы и только они;
2) 2-хроматические графы — это ненулевые двудольные графы и только они;
3) х(Kn) = n и x(G) >= n если граф G содержит в качестве подграфа граф Кn для натурального числа n.
Задача нахождения хроматического числа произвольного графа явилась предметом многих исследований в конце XIX и в текущем столетии. Сейчас по этому вопросу известно большое количество интересных результатов. В этом разделе мы рассмотрим «приближенный» алгоритм, позволяющий находить значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин.
«приближенный» алгоритм раскраски графа
Алгоритм раскраски графа позволяет находить (точное или приближенное) значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин.
Граф G называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое, что граф G является r-хроматическим, называется хроматическим числом графа G. Задача нахождения хроматического числа графа называется задачей о раскраске (или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на r подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.
Рассмотрим последовательный метод, основанный на упорядочивании множества вершин.
Colourize(G)
1. Упорядочить вершины по невозрастанию степени.
2. Окрасить первую вершину в цвет 1.
3. Выбрать цвет окраски 1.
4. Пока не окрашены все вершины, повторять п.4.1.-4.2.:
4.1. Окрасить в выбранный цвет всякую вершину, которая не смежна
с другой, уже окрашенной в этот цвет.
4.2. Выбрать следущий цвет.
В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней. Первая вершина окрашивается в цвет 1; затем список вершин просматривается сверху вниз (по невозрастанию степеней) и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа.
Приведенный выше алгоритм можно модифицировать. Для этого после каждого шага нужно упорядочивать неокрашенные вершины. Простая модификация описанной выше эвристической процедуры состоит в переупорядочивании неокрашенных вершин по невозрастанию их относительных степеней. Под относительными степенями понимаются степени соответствующих вершин в неокрашенном подграфе исходного графа.
В данной модификации предполагалось, что если две вершины имеют одинаковые степени, то порядок таких вершин случаен. Такие вершины можно также упорядочить, но уже по двухшаговым степеням. Двухшаговую степень определим как сумму относительных степеней инцидентных вершин. Аналогично можно поступать и далее.
Не учитывая время, затраченное на сортировку вершин в порядке невозрастания степеней, необходимо сделать цикл по всем вершинам графа. Для каждой необходимо найти минимальный цвет, что в худшем случае может занять o(V2) для случая с полным графом. Значит, общее время составит o(V3) в худшем случае.
Визуализатор алгоритма:
Для начала можно ограничить хроматическое число графа G снизу кликовым числом графа. Это очевидно потому, что для раскраски клики графа потребуется число цветов, равное количеству вершин этой клики.
γ(G) ≥ ρ(G)
Теперь введем более точную оценку. Воспользуемся для этого количеством вершин в максимальном независимом множестве графа G. α(G) = ρ(G′), где граф G′ является дополнением графаG.
γ(G) ≥ [n/α(G)] или γ(G) ≥ [n/ρ(G′)],
где [] означает целую часть числа. Рассмотрим еще две оценки, введенные в .
γ(G) ≥ ]2n0.5[−γ(G′)
γ(G) ≥ n/γ(G′),
где ][ означает наименьшее целое число, которое не меньше аргумента. Существует и еще одна оценка, менее точная, чем первая, но использующая лишь количество вершин и ребер графа.
γ(G) ≥ n2/(n2−2m)
В итоге, можно сказать, что приведенные оценки достаточно неточны. Например, в показано, что можно построить такой граф, который не содержит даже полного подграфа третьего порядка и будет иметь произвольно большое значение хроматического числа. В то же время, эти оценки дают приблизительно одинаковую точность. Поэтому выбор из них следует осуществлять, исходя из уже вычисленных данных.
Нижние оценки хроматического числа безусловно более интересны, чем верхние, поскольку (если они достаточно близки к истинному значению) они могут быть использованы в процедуре вычисления γ(G), включающей дерево поиска. В то же время верхние оценки хроматического числа подобного применения не находят. Тем не менее в литературе приводятся формулы для вычисления верхних оценок хроматического числа. Например, в предложена следующая легко вычисляемая оценка:
γ(G) ≤ 1+max(d(xi+1)), xi ∈ X
Приведем также две оценки, связывающие хроматическое число графа и хроматическое число дополнения для данного графа.
γ(G) ≤ n+1−γ(G′)
γ(G) ≤ [(n+1)2/4]/γ(G′)
Вышеприведенные верхние и нижние оценки, использующие хроматическое число дополнения рассматриваемого графа являются наиболее точными в том смысле, что можно построить графы, на которых эти оценки достигаются. Но в большинстве случаев они настолько неточны, что не имеют практического значения.
Долгое время лучшей оценкой для планарных графов была следующая теорема.
Каждый планарный граф можно так раскрасить, используя пять цветов, что любые две смежные вершины будут окрашены в разные цвета.
А в 1850 году появились первые упоминания о гипотезе четырех красок, которая являлась улучшенной оценкой для планарных графов. Данная гипотеза была обоснована с помощью ЭВМ в 1976 году, а позже доказана аналитически и получила статус теоремы.
Каждый планарный граф можно так раскрасить, используя четыре цвета, что любые две смежные вершины будут окрашены в разные цвета.
Если граф G является r-хроматическим, то он может быть раскрашен с использованием r (или меньшего числа) красок с помощью следующей процедуры: сначала в один цвет окрашивается некоторое максимальное независимое множество S(G), затем окрашивается в следующий цвет множество S(X\S(G)) и так далее до тех пор, пока не будут раскрашены все вершины.
Доказательство. Тот факт, что такая раскраска, использующая только r цветов, всегда существует, может быть установлен следующим образом. Пусть существует раскраска в r цветов, такая, что одно или больше множеств, окрашенных в один и тот же цвет, не являются максимальными независимыми множествами в смысле, упомянутом выше. Перенумеруем цвета произвольным способом. Очевидно, что мы можем всегда покрасить в цвет 1 те вершины (пусть это множество Vi′), которые не были окрашены в этот цвет и которые образуют максимальное независимое множество вместе с множеством Vi всех вершин графа, уже окрашенных в цвет 1. Эта новая раскраска возможна потому, что никакая вершина из множества Vi′ не является смежной ни с какой вершиной из Vi′ и, следовательно, всякая вершина, которая смежна хотя бы с одной вершиной из Vi′, окрашена в цвет, отличный от цвета 1, и поэтому не затрагивается процедурой перемены цвета вершин из Vi′. Рассматривая теперь подграф (X − Vi′) и проводя с ним аналогичные манипуляции, мы окрасим в цвет 2 какое-то (новое) максимальное независимое множество и т. д.
С помощью процедуры, описанной в этой теореме можно получить раскраску с минимальным количеством цветов для данного графа. Такая раскраска называется оптимальной независимой раскраской.
Поскольку при любой допустимой раскраске графа G множество вершин, окрашиваемых в один и тот же цвет, должно быть независимым множеством, то всякую допустимую раскраску можно интерпретировать как разбиение всех вершин графа G на такие независимые множества. Далее, если каждое независимое множество расширить до максимального (путем добавления к нему других вершин), то раскраска графа G может быть тогда истолкована как покрытие вершин графа G максимальными независимыми множествами. Очевидно, что в последнем случае некоторые вершины графа G могут принадлежать более чем одному максимальному независимому множеству. Это говорит о возможности существования различных допустимых раскрасок (использующих одно и то же число цветов), так как вершину, принадлежащую разным максимальным множествам, можно окрасить в любой из цветов, соответствующих тем максимальным независимым множествам, которым она принадлежит.
Итак, пусть построены все максимальные независимые множества графа G (пусть таких множеств t), и пусть задана (n×t) матрица M = {mij}, у которой mij=1, если вершина xiпринадлежит j-му максимальному независимому множеству, и mij=0 в противном случае. Если теперь каждому максимальному независимому множеству сопоставить единичную стоимость, то задача раскраски сведется просто к задаче нахождения наименьшего числа столбцов в матрице М, покрывающих все ее строки х). Каждый столбец из решения этой ЗНП соответствует определенному цвету, который может быть использован для окраски всех вершин максимального независимого множества, представленного этим столбцом.
Приведем пример
Для данного графа матрица M будет иметь следующий вид:
Решениями будут являться такие комбинации столбцов, чтобы столбец, состоящий из дизъюнкций соответствующих элементов представлял бы собой столбец из единиц. Например такими множествами будут {4,6,10,14}, {4,6,10,12}, {4,6,10,11}, {4,6,10,8} и {4,6,10,2}.
Для определения хроматического числа графа может быть использован достаточно эффективно простой метод неявного перебора.
Предположим, что множество вершин как-то упорядочено и xi — i-я вершина этого множества. Тогда первоначальная допустимая раскраска может быть получена так:
Данный алгоритм можно ускорить, используя следующие замечания:
В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней.
Первая вершина окрашивается в цвет 1. Затем список вершин просматривается сверху вниз (по невозрастанию степеней) и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа.
Приведенный выше алгоритм можно модифицировать. Для этого после каждого шага нужно упорядочивать неокрашенные вершины. Простая модификация описанной выше эвристической процедуры состоит в переупорядочивании неокрашенных вершин по невозрастанию их относительных степеней. Под относительными степенями понимаются степени соответствующих вершин в неокрашенном подграфе исходного графа.
В данной модификации предполагалось, что если две вершины имеют одинаковые степени, то порядок таких вершин случаен. Такие вершины можно также упорядочить, но уже по двухшаговым степеням. Двухшаговую степень определим как сумму относительных степеней инцидентных вершин. Аналогично можно поступать и далее.
Также можно изначально упорядочивать вершины по двухшаговым или трехшаговым степеням.
В задачах теории расписаний осмотры представляются в виде временных интервалов. Каждому осмотру можно сопоставить вершину некоторого графа, причем две любые вершины графа будут соединены ребром лишь тогда, когда соответствующие им осмотры нельзя осуществлять одновременно. Требуется составить такой график осмотра, который связан с наименьшими временными затратами (с учетом приведенных выше ограничений на «совместимость» осмотров). Эта задача эквивалентна задаче о раскраске вершин графа с использованием наименьшего числа цветов. Хроматическое число графа как раз и соответствует осмотру, требующему наименьших временных затрат.
Пусть для выполнения каких-то n работ надо распределить m имеющихся в наличии ресурсов. Считаем, что каждая из работ выполняется за некоторый (одинаковый для всех работ) промежуток времени и что для выполнения i-й работы требуется подмножество ресурсов Si.
Построим граф G: каждой работе соответствует определенная вершина графа, а ребро (xi, xj) существует в графе тогда и только тогда, когда для выполнения i-й и j-й работ требуется хотя бы один общий ресурс, т. е. когда Si∩Sj≠Ø. Это означает, что i-я и j-я работы не могут выполняться одновременно. Раскраска графа G определяет тогда некоторое распределение ресурсов (по выполняемым работам), причем такое, что работы, соответствующие вершинам одного цвета, выполняются одновременно. Наилучшее использование ресурсов (т. е. выполнение всех nработ за наименьшее время) достигается при оптимальной раскраске вершин графа G.
Естественно, что круг применения не ограничен приведенными примерами.
Дополнение графа
граф, полученный из исходного обращением инцидентности вершин. То есть если какая-то пара вершин была инцидентна в исходном графе, то в дополнении эти вершины не соединены друг с другом. И если какая-то пара вершин не была инцидентна в исходном графе, то в дополнении эти вершины соединены друг с другом.
Клика
максимальный полный подграф.
Кликовое число графа
число вершин в клике графа.
Максимальное независимое множество
максимальное множество вершин такое, что никакие две вершины не инцидентны друг другу.
Планарный граф
граф, который можно изобразить на плоскости так, чтобы линии, изображающие ребра графа, не пересекались.
Раскраска
граф называют раскрашенным в n цветов, если каждой из его вершин сопоставлен цвет.
Хроматическое число графа
минимальное количество цветов, в которое можно раскрасить граф так, чтобы не нашлось пары инцидентных вершин с одинаковым цветом
На этом все! Теперь вы знаете все про раскраска графов, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое раскраска графов, алгоритм раскраски графа, практическое применение раскраски графов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов