Раскраска вершин графа. Глава 7

в один цвет.
Раскраска не зависит от ориентации графа.

 

нет циклов нечетной длины

Пример

ресурсов.

Распределение памяти в вычислительной системе. Вершины соответствуют процессам. Смежность означает обращение к одной области памяти.

k непересекающихся
классов

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

Минимальную раскраску можно интерпретировать как минимальное покрытие вершин графа максимальными пустыми подграфами.

максимальные пустые под-графы (например, как дополнение к вершинно-реберному покрытию), а затем находится минимальное покрытие вершин
графа максимальными пустыми подграфами.

покрытия вершин максимальными пустыми подграфами

Раскраска вершин произвольного графа является типичным примером NP – полной задачи, точное решение которой реально осуществимо только при небольшом количестве вершин.

Идея точного алгоритма:

вершин), однако нет жестких требований к минимизации количества цветов.
В таких случаях можно использовать приближенные алгоритмы раскраски.
Существует несколько приближенных алгоритмов.
Метод заключается в последовательном преобразовании графа: на каждом шаге происходит объединение двух вершин в одну.

алгоритмом поиска и поглощения соцветных вершин.

b

a

Г(a)

Г(b)

 

{a, b}

- поглощающая вершина

- поглощаемая вершина

с точки зрения раскраски, он не приводит к увеличению хроматического числа.

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

6, 28}
Стягивание

Г(3)={28, 157, 4}
Г(6)={157, 4}
Поглощение

Г(28)={36, 157}
Г(4)={36, 157}
Поглощение

Пример [Кристофидес, с. 95]

Раскраска все равно минимальная

существуют свойства, зависящие от вида наглядного представления.

Определение. Граф называется планарным – planar graph, если его можно разместить на плоскости таким образом, что никакие два ребра не пересекаются

Практический пример – размещение электрической схемы устройства на печатной плате. Проводники не должны пересекаться.

приводятся друг к другу путем гомеоморфных преобразований.

Слияние ребер

века.
Академик АН СССР, Герой Социалистичес-кого Труда, многократный лауреат Государственных премий.
В 14 лет в результате несчастного случая потерял зрение. Благодаря героическим усилиям матери, не имевшей специальной математической подготовки, при полной

Куратовский, Казимеж (1896-1980). Польский математик, вице-президент Польской академии наук. Научные труды в области топологии.

слепоте окончил среднюю школу и получил высшее образование на математическом отделении физико-математического факультете МГУ.

сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. Эта теорема была сформулирована Френсисом Гутри еще в 1852 г., однако доказать её не удавалось более 100 лет. В течение этого времени было предпринято множество попыток как доказательства, так и опровержения, и эта задача носила название проблемы четырёх красок.
Теорема о четырёх красках была доказана в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном из Иллинойского университета.