Эвристический алгоритм раскраски графа

Эвристический алгоритм раскраски графа

Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами).

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

Рис.1 пример графа «звезда».

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

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

Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретаютнаправление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней.

Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).

Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.

Последовательности вершин (рис. 2): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур.

Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).

Читайте также:  Продажи apple в китае

Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем). На рис. 2 изображен связный граф.

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

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

Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.

2. Раскраска графа

Раскраской вершин графа называется назначение цветов его вершинам. Обычно цвета — это числа . Тогда раскраска является функцией, определенной на множестве вершин графа и принимающей значения в множестве . Раскраску можно также рассматривать как разбиение множества вершин , где — множество вершин цвета . Множества называют цветными классами. Раскраска называется правильной, если каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета. Задача о раскраске состоит в нахождении правильной раскраски данного графа в наименьшее число цветов. Это число называется хроматическим числом графа и обозначается .

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

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

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

Читайте также:  Нам не стать привыкать

Эвристический алгоритм раскраски вершин графа имеет следующий вид:

Шаг 1. Сортировать вершины графа по степеням убывания:

Шаг 3. i=i+1. Выбрать очередную не раскрашенную вершину xi и проверить условие смежности: xi Г(Xp)=, где Xp – множество вершин, уже раскрашенных в цвет p. Если вершина xi не является смежной с данными вершинами, то также присвоить ей цвет p: col(xi)=p.

Шаг 4. Повторить п.3, пока не будет достигнут конец списка (i=n).

Шаг 5. Если все вершины графа раскрашены, то – конец алгоритма;

2.4 Контрольный пример

Раскрасим граф G, изображенный на рисунке 15. Промежуточные данные для решения задачи будем записывать в таблицу. Отсортируем вершины графа по убыванию их степеней. В результате получается вектор отсортированных вершин X * =<x1, x5, x6, x4,x2,x3>.

Соответствующие данным вершинам степени образуют второй вектор:

D

Алгоритмы
обхода графа

Алгоритмы поиска
кратчайшего пути

Нахождения наименьшего
остового дерева

Максимальные потоки
и паросочетания

Алгоритм раскраски графа

Алгоритм раскраски графа позволяет находить (точное или приближенное) значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин.

Граф G называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое, что граф G является r-хроматическим, называется хроматическим числом графа G. Задача нахождения хроматического числа графа называется задачей о раскраске (или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на r подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.

Рассмотрим последовательный метод, основанный на упорядочивании множества вершин.

Формальное описание [вверх]

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

Читайте также:  Как восстановить пароль в гугл плей аккаунте

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

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

Оценка сложности [вверх]

Не учитывая время, затраченное на сортировку вершин в порядке невозрастания степеней, необходимо сделать цикл по всем вершинам графа. Для каждой необходимо найти минимальный цвет, что в худшем случае может занять o(V 2 ) для случая с полным графом. Значит, общее время составит o(V 3 ) в худшем случае.

Ссылка на основную публикацию
Шарик равноускоренно скатывается по наклонной плоскости
За каждую секунду, путь пройденный шариком,увеличивается на 20см. Следовательно за 4 секунду он пройдет 70см. Ответ:(2) Если ответ по предмету...
Что такое ogg формат
Ogg — Dateiendung: .ogg, .oga, .ogv, .ogx MIME Type … Deutsch Wikipedia .ogg — Dateiendung .ogg, .oga, .ogv, .ogx MIME...
Что такое pppoe соединение на роутере
PPPoE (англ. Point-to-point protocol over Ethernet ) — сетевой протокол канального уровня (второй уровень сетевой модели OSI) передачи кадров PPP...
Шарнирная стойка для дрели
Стойка для дрели с тисками FIT 37861 Стойка для дрели Калибр 96203 Стойка для дрели RedVerg DS-43 Стойка для дрели...
Adblock detector