Раскраска графа дискретная математика


Договоренности

  1. Графы, рассматриваемые далее, являются неориентированными и не имеют петель. Если специально не оговаривается иное, то под словом «граф» понимается именно такой граф.
  2. Чтобы не затруднять восприятие текста читателем, уже имеющим некоторый запас знаний в области графов, для большинства определений отведен отдельный раздел.

Основные теоремы

Нижние оценки для γ(G)

Для начала можно ограничить хроматическое число графа G снизу кликовым числом графа. Это очевидно потому, что для раскраски клики графа потребуется число цветов, равное количеству вершин этой клики.

γ(G) ≥ ρ(G)

Теперь введем более точную оценку. Воспользуемся для этого количеством вершин в максимальном независимом множестве графа G. α(G) = ρ(G′), где граф G′ является дополнением графа G.

γ(G) ≥ [n/α(G)] или γ(G) ≥ [n/ρ(G′)],

где [] означает целую часть числа. Рассмотрим еще две оценки, введенные в [2].

γ(G) ≥ ]2n0.5[−γ(G′)
γ(G) ≥ n/γ(G′),

где ][ означает наименьшее целое число, которое не меньше аргумента. Существует и еще одна оценка, менее точная, чем первая, но использующая лишь количество вершин и ребер графа.

γ(G) ≥ n2/(n2−2m)

В итоге, можно сказать, что приведенные оценки достаточно неточны. Например, в [3] показано, что можно построить такой граф, который не содержит даже полного подграфа третьего порядка и будет иметь произвольно большое значение хроматического числа. В то же время, эти оценки дают приблизительно одинаковую точность. Поэтому выбор из них следует осуществлять, исходя из уже вычисленных данных.

Верхние оценки для γ(G)

Нижние оценки хроматического числа безусловно более интересны, чем верхние, поскольку (если они достаточно близки к истинному значению) они могут быть использованы в процедуре вычисления γ(G), включающей дерево поиска. В то же время верхние оценки хроматического числа подобного применения не находят. Тем не менее в литературе приводятся формулы для вычисления верхних оценок хроматического числа. Например, в [1] предложена следующая легко вычисляемая оценка:

γ(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. Окрасить xi в цвет 1.
  2. Каждую из оставшихся вершин окрашивать последовательно: вершина xi окрашивается в цвет с наименьшим возможным «номером» (т. е. выбираемый цвет должен быть первым в данном упорядочении цветом, не использованным при окраске какой-либо вершины, смежной xi).

Данный алгоритм можно ускорить, используя следующие замечания:

  1. При любом упорядочении вершин допустимые цвета j для вершины xi удовлетворяют условию j≤i.
  2. С вычислительной точки зрения выгодно размещать вершины так, чтобы первые вершины образовывали максимальную клику графа. Тогда все вершины, входящие в эту клику будут окрашены в цвет 1 и алгоритм может закончить работу раньше.

Приближенные алгоритмы раскрашивания

В этом простейшем из методов вершины вначале располагаются в порядке невозрастания их степеней.

Алгоритм

Первая вершина окрашивается в цвет 1. Затем список вершин просматривается сверху вниз (по невозрастанию степеней) и в цвет 1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет. Потом возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет 2 и снова просматриваем список вершин сверху вниз, окрашивая в цвет 2 любую неокрашенную вершину, которая не соединена ребром с другой, уже окрашенной в цвет 2 вершиной. Аналогично действуем с цветами 3, 4 и т. д., пока не будут окрашены все вершины. Число использованных цветов будет тогда приближенным значением хроматического числа графа.

Приведенный выше алгоритм можно модифицировать. Для этого после каждого шага нужно упорядочивать неокрашенные вершины. Простая модификация описанной выше эвристической процедуры состоит в переупорядочивании неокрашенных вершин по невозрастанию их относительных степеней. Под относительными степенями понимаются степени соответствующих вершин в неокрашенном подграфе исходного графа.

В данной модификации предполагалось, что если две вершины имеют одинаковые степени, то порядок таких вершин случаен. Такие вершины можно также упорядочить, но уже по двухшаговым степеням. Двухшаговую степень определим как сумму относительных степеней инцидентных вершин. Аналогично можно поступать и далее.

Также можно изначально упорядочивать вершины по двухшаговым или трехшаговым степеням.

Применение задачи о раскраске

Теория расписаний

В задачах теории расписаний осмотры представляются в виде временных интервалов. Каждому осмотру можно сопоставить вершину некоторого графа, причем две любые вершины графа будут соединены ребром лишь тогда, когда соответствующие им осмотры нельзя осуществлять одновременно. Требуется составить такой график осмотра, который связан с наименьшими временными затратами (с учетом приведенных выше ограничений на «совместимость» осмотров). Эта задача эквивалентна задаче о раскраске вершин графа с использованием наименьшего числа цветов. Хроматическое число графа как раз и соответствует осмотру, требующему наименьших временных затрат.

Распределение ресурсов

Пусть для выполнения каких-то n работ надо распределить m имеющихся в наличии ресурсов. Считаем, что каждая из работ выполняется за некоторый (одинаковый для всех работ) промежуток времени и что для выполнения i-й работы требуется подмножество ресурсов Si.

Построим граф G: каждой работе соответствует определенная вершина графа, а ребро (xi, xj) существует в графе тогда и только тогда, когда для выполнения i-й и j-й работ требуется хотя бы один общий ресурс, т. е. когда Si∩Sj≠Ø. Это означает, что i-я и j-я работы не могут выполняться одновременно. Раскраска графа G определяет тогда некоторое распределение ресурсов (по выполняемым работам), причем такое, что работы, соответствующие вершинам одного цвета, выполняются одновременно. Наилучшее использование ресурсов (т. е. выполнение всех n работ за наименьшее время) достигается при оптимальной раскраске вершин графа G.

Естественно, что круг применения не ограничен приведенными примерами.

Литература

  1. Brooks R. L. On colouring the nodes of a network. Proc. Cambridge Philosophical Soc., 37. 1941, p. 194.
  2. Nordhous E. A., Gaddum J. W. On complementary graphs. American Mathematical Monthly, 63. 1956, p. 175.
  3. Tutte W. T. (B. Descartes). Solution of advanced problem N°. American Mathematical Mothly, 61. 1954, p. 352.
  4. Математика. Большой энциклопедический словарь. — М.: Большая Российская Энциклопедия. 2000.
  5. Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.

Термины

Дополнение графа граф, полученный из исходного обращением инцидентности вершин. То есть если какая-то пара вершин была инцидентна в исходном графе, то в дополнении эти вершины не соединены друг с другом. И если какая-то пара вершин не была инцидентна в исходном графе, то в дополнении эти вершины соединены друг с другом. Клика максимальный полный подграф. Кликовое число графа число вершин в клике графа. Максимальное независимое множество максимальное множество вершин такое, что никакие две вершины не инцидентны друг другу. Планарный граф граф, который можно изобразить на плоскости так, чтобы линии, изображающие ребра графа, не пересекались. Раскраска граф называют раскрашенным в n цветов, если каждой из его вершин сопоставлен цвет. Хроматическое число графа минимальное количество цветов, в которое можно раскрасить граф так, чтобы не нашлось пары инцидентных вершин с одинаковым цветом.

Александр Горюнов, Татьяна Коломейцева

Иван / 2009-06-25 18:41:49

Где книга по теории графов? У меня в поисковике написано, что тут.

Извините, в Ваш поисковик мы не заглядывали. А "тут", как видите, книги нет.

Юлия / 2010-01-27 19:53:33

Очень полезный проект! Огромное спасибо разработчикам! Помогло! :)

Олег / 2011-01-01 00:30:28

Существуют ли какие-либо уже написанные алгоритмы оптимальной "дораскраски" (некоторые вершины уже закрашены определенными цветами) графов?

Иначе говоря, Ваша постановка задачи допускает увеличение хроматического числа. На нашем сайте такая задача не обсуждается. Но в современных приложениях эта тематика находит достаточно широкое применение. Обратитесь к wiki-странице http://ru.wikipedia.org/wiki/..._Практическое_применение_раскраски_графов. Там есть интересующие Вас ссылки.


Источник: http://rain.ifmo.ru/cat/view.php/theory/graph-coloring-layout/coloring-2004



Рекомендуем посмотреть ещё:


Закрыть ... [X]

Учебник по дискретной математике. Раскраска графа Игры трансформеры раскраска


Раскраска графа дискретная математика

Раскраска графа Викиконспекты



Раскраска графа дискретная математика

Графы



Раскраска графа дискретная математика

Tea pots, Relax, breathe, color визуальные заметки Pinterest



Раскраска графа дискретная математика

Детские игры Раскраски онлайн Умные раскраски



Раскраска графа дискретная математика

Детские раскраски, книжки-раскраски для детей



Раскраска графа дискретная математика

Домашние животные Раскраски распечатать бесплатно



Раскраска графа дискретная математика

Здоровый образ жизни, ЗОЖ



Раскраска графа дискретная математика

Игра Грузовик-монстр: Раскраска онлайн



Раскраска графа дискретная математика

Игра Рукопашный Бой Самолетов онлайн (Dogfight Sim)



Раскраска графа дискретная математика

Игра Урок математики - играть онлайн и бесплатно



Раскраска графа дискретная математика

Игра Щенячий патруль раскраска



Раскраска графа дискретная математика

Игры по мультфильмам для девочек - играй бесплатно



Раскраска графа дискретная математика

Математические раскраски, васелиса и кощей



Раскраска графа дискретная математика

Просмотр коллекций - Ножи CS:GO Items