Алгоритм минимальной раскраски вершин (ребер) графа G

Рассмотрим алгоритм определения хроматического числа h(G) (хроматического класса H(G)) графа G.

1. Выделяем множество вершинно пустых (реберно пустых) подграфов графа G.

2. Строим двумерную таблицу, каждой строек которой сопоставим взаимно однозначно пустой подграф, столбцу – вершину (ребро); в клетке (i, j) записываем единицу, если j-ая вершина (j – ое ребро) содержится в i-ом пустом подграфе, в противном случае клетку оставляем пустой.

3. Определяем покрытие столбцов строками. Каждое покрытие порождает раскраску. Покрытие минимальной мощности определяет хроматическое число (хроматический класс) графа G.

Пример 3. Определить хроматическое число графа G (рис. 2.3).

Для определения h(G) необходимо выделить все вершинно пустые подграфы заданного графа G (рис. 2.4).

 

1 2 3 4 5 6 7

1. {1,3,5} 1 1 1

2. {1,5,7} 1 1 1

3. {1,4,7} 1 1 1

4. {2,4,7} 1 1 1

5. {2,5,7} 1 1 1

6. {2,4,6} 1 1 1

7. {3,6} 1 1

Определяем минимальное число строк, покрывающих все столбцы таблицы. Такими строками могут быть строки 1,4,7. Значит

h(G) = |{{1,3,5} {2,4,7}, {3,6}}| = 3.

Зададимся красками: для множества вершин {1,3,5} - краска а, для множества вершин {2,4,7} - краска b, для множества вершин {3,6} - краска с.

Раскрасим вершины графа G (рис. 2.6).

2 b

a 1 3 a,c

b

7

c 6 4 b

5 a

G

Рис. 2.6

Отметим, что вершину 3 можно раскрасить в две краски: а или с.

Сравним значение хроматического числа h(G) с оценками этого числа (пример 1). Видно, что т. 2.2 и т. 2.3 дали для заданного графа G хорошее приближение, а т.2.4 – удовлетворительное приближение.■

Пример 4. Определить хроматический класс H(G) графа G, у которого

V = {1,2,3,4,5,6,7}, U= {(1,2),(1,6), (2,3), (3,4),(3,7) (4,5),(5,6), (6,7)}.

Выделяем реберно пустые подграфы заданного графа G, предварительно обозначив ребра буквами (рис. 2.7)

2

a b

1 k 3

f g c

6 7

4

e d

5

 

b

k

g k c

d f

e g d

e

d

g b

k f

e g e d g Ø k Ø

 

E₈ E₁₀

 

Ø Ø Ø Ø Ø Ø Ø Ø

 

 

E₁ E₂ E₃ E₄ E₅ E₆ E₇ E₉

 

Рис. 2.7

Строим двумерную таблицу:

A b c d e f g k

1. {a,c,e} 1 1 1

2. {a,c,g} 1 1 1

3. {a,d,g} 1 1 1

4. {a,d,k} 1 1 1

5. {a,e,k} 1 1 1

6. {b,d,f} 1 1 1

7. {b,d,g} 1 1 1

8. {b,e} 1 1

9. {d,f,k} 1 1 1

10. {c,f} 1 1

Определяем минимальное число строк, покрывающих все столбцы таблицы. Такими строками могут быть строки 1,7,9. Значит

Н(G) = |{{a,c,e},{b,d,g}, {d,f,k}} | = 3.

Зададимся красками: {a,c,e} - краска I, {b,d,g} – краска II, {d,f,k} – краска III.

Раскрасим ребра заданного графа G (рис. 2.8)

A b

k

f g c

 

 

e d

 

G

Рис. 2.8

Отметим, что ребро d можно раскрасить в два цвета.■

Пример 5. Показать, что хроматический класс Н(G) графа G (рис. 5а) равен хроматическому классу h() графа (рис. 2.5б).

Хроматический класс Н(G) графа G найден в примере 4: Н(G)=3.

Найдем хроматическое число h() графа .

Выделяем вершинно пустые подграфы графа (рис. 2.9)

 

 

b

a k c

 

g d

f e

5

 

k c

b g

g d d

k c

e f e

d

g g

d b g

e e k k Ø Ø

e f

E₈ E₁₀

 

Ø Ø Ø Ø Ø Ø Ø Ø

 

 

E₁ E₂ E₃ E₄ E₅ E₆ E₇ E₉

 

Рис. 2.9

Строим двумерную таблицу:

A b c d e f g k

1. {a,c,e} 1 1 1

2. {a,c,g} 1 1 1

3. {a,k, e} 1 1 1

4. {a,k,d} 1 1 1

5. {a,d,g} 1 1 1

6. {f,d,k} 1 1 1

7. {f,d,b} 1 1 1

8. {f,c} 1 1

9. {b,d,g} 1 1 1

10. {b,e} 1 1

 

Минимальное число строк, покрывающих все столбцы таблицы, три. Например, строки 1,6,9. Значит

h()== | { {a,c,e}, {f,d,k}, {b,d,g}} | = 3,

т.е. H(G)= h() = 3.■

Задачи для самостоятельного решения.

1. Оценить хроматическое число h(G) графа G = < V, U >, у которого

V = {1,2,3,4,5,6}, U= {(1,2),(1,6), (2,3), (2,4),(2,6) (3,4),(4,5), (4,6), (5,6)}.

2. Определить хроматическое число графа G, заданного в задаче 1.

3. Найти хроматический класс графа G, заданного в задаче 1.

4. Построить для графа G, заданного в задаче 1, граф = < , > и показать, что H(G)= h().

5. Построить граф F₅ и проверить на нем т.2.7.

ПЛАНАРНОСТЬ ГРАФА.

Графы G и изоморфны, если для них сохраняется отношение инцидентности (коинцидентности).

Пример 1. Являются ли графы G (рис. 3.1а) и (рис. 3.1б) изоморфными?

v₃ u₄ v₄ u₃

u₃ u₅

u₁ u₆ u u₆ u₆

v₃ v₁

v₁ u₂ v₂

u₅ u₅ u₅ u₅

u₄ uu u₁

G

v₄

а)

б)

Рис. 3.1

Проверим, например, для этих графов сохранение отношения коинцидентности.

Граф G:

вершина v₁ коинцидентна ребрам u₁, u₂, u₃;

вершина v₂ коинцидентна ребрам u₂, u₅, u₆;

вершина v₃ коинцидентна ребрам u₃, u₄, u₆;

вершина v₄ коинцидентна ребрам u₁, u₄, u₅.

Граф :

вершина v₁ коинцидентна ребрам u₁, u₂, u₃;

вершина v₂ коинцидентна ребрам u₂, u₅, u₆;

вершина v₃ коинцидентна ребрам u₃, u₄, u₆;

вершина v₄ коинцидентна ребрам u₁, u₄, u₅.

 

Отношение коинцидентности выполняется, значит, графы G и

изоморфны. ■

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

В рассмотренном примере граф G является планарным, т.к. граф , ему изоморфный, не имеет пересечения ребер.

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

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

Граф, гомеоморфный планарному графу, также является планарным.

Пример 2. Являются ли граф G (рис. 3.2а) и граф (рис. 3.2б) гомеоморфными?

v₃ u₄ v₆ u₇ v₄ v₅

u₂ u₉ u₈ u₃

v₅ v₇

u u₆ u₆

u₆ v₃ v₁

u₃ u₁

u₅ u₅ u₅ u₅

v₁ u₂ v₂ u₄ u u₁

G

v₄

а)

б)

Рис. 3.2

Графы G и являются гомеоморфными, т.к. после удаления в графе G

вершин второй степени v₅, v₆, v₇ и объединения инцидентных этим вершинам ребер u₃ и u₈, u₄ и u₇, u₁ и u₉ и после удаления в графе вершин второй степени v₅, v₆ и объединения инцидентных этим вершинам вебер u₃ и u₈, u₅ и u₇ рафы G и оказываются изоморфными. Это следует из примера 1. ■

Теорема 3.1 (теорема Л.С. Понтрягина). Граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного F₅ или К_3,3.

Граф F₅ – минимальный полный граф, который не является планарным (рис. 3.3а). Удаление одного ребра делает этот граф планарным.

Граф К_3,3 – минимальный полный граф, который не является планарным (рис. 3.3б). Удаление одного ребра делает этот граф планарным.

Графы F₅ и К_3,3 называют часто запрещенными фигурами.

К_3,3

F₅

Рис. 3.3

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

Толщина графа G называется наименьшее число планарных графов, объединение которых дает G.

Толщина планарного графа равна 1.

Нижняя оценка толщины t(G) графа G = < V, U > определяется неравенством

t(G) 1 + , (3.1)

 

где - ближайшее целое число, n=|v|, S_i - степень i–ой вершины.

Отметим, что для строгого доказательства планарности графа используется теорема Понтрягина, соотношение (3.1) лишь только нижняя оценка толщины графа.

Пример 3. Является ли граф G (рис. 3.4) планарным? Если нет, то определить, какие ребра необходимо удалить (реализовать на других плоскостях) для преобразования графа G в планарный.

 

 

G

Рис. 3.4

Согласно теореме 3.1 проверим графа G на содержание подграфа, гомеоморфного F₅.

Проверку можно сделать следующим образом: удаляя минимальное количество вершин и некоторое количество ребер, попытаться привести заданный граф G к виду графа F₅. В приведенном графе могут присутствовать вершины второй степени.

В графе F₅ все вершины имеют степень, равную 4, значит, в графе

G можно удалить вершину 1 с инцидентным ей ребрами, т.к. степень вершины 1 равна 3. Дальнейшие преобразования показаны на рис. 3.5.

 

 

Рис. 3.5

В результате получили подграф, гомеоморфный F₅ , т.е. заданный

граф G не является планарным. Удаление любого ребра в полученном подграфе делает его (подграф) планарным.

Теперь проверим граф G на содержание подграфа, гомеоморфного

К_3,3. Попытаемся привести граф G к виду К_3,3.

В графе К_3,3 все вершины имеют степень, равную 3. В графе G степень вершин больше или равна 3, поэтому в процессе преобразования графа G вершины удалять не будем. Сведение графа G к виду графа К_3,3 показано на рис. 3.6.

 

 

 

 

Рис. 3.6

В результате получен подграф, гомеоморфный К_3,3. Удаление любого ребра в полученном подграфе делает его планарным.

Определим нижнюю оценку графа G:

t(G) 1+ =2, т.е. t(G) 2.

 

Вывод: заданный граф G содержит подграфы, гомеоморфные F₅ и К_3,3, толщина графа G не меньше двух, значит, граф G непланарный.

Так как удаление любого ребра выводит запрещенную фигуру (полученные подграфы) из класса подграфов, гомеоморфных F₅ и К_3,3, то граф G станет планарным; если удалить ребро, входящее как в подграф, гомеоморфный F₅ , так и в подграф, гомеоморфный К_3,3.

Такими общими ребрами являются ребра (2,3), (2,4), (3,6), (4,5),(4,6), (5,7). Удаление любого из этих ребер делает граф планарным.

После удаления, например, для определенности ребра (3,6) получаем планарный граф, плоское представление которого изображено на рис. 3.7. Соединение, которое соответствует удаленному ребру (показано пунктирной линией), реализуется на второй плоскости. Толщина t(G) графа G равна 2. ■

 

 

 

 

G

Рис.3.7

 

 

Задачи для самостоятельного решения.

1. Изоморфны ли графы, изображенные на рис. 3.8?

b

a d b f c

c c e

g e

g f d g d

b a a

e

G₁ G₂ G₃

Рис. 3.8

2. Покажите, что графы, изображенные на рис. 3.9., гомеоморфные.

 

 

Рис. 3.9

3. Покажите, что приведенные на рис. 3.9 графы непланарные. Какое минимальное число ребер необходимо удалить, чтобы они стали планарными.

4. Найти нижнюю оценку толщины графов, изображенных на рис. 3.9.

5. Задача о трех домах и трех колодцах: можно ли продолжить от домов к каждому колодцу дороги так, чтобы они не пересекались (враждующие соседи должны иметь возможность пользоваться всеми колодцами, но не хотят встречаться на дороге)?

 

СПИСОК ЛИТЕРАТУРЫ

1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.

2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1986 – 480с.

3. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатомиздат, 1987 – 496с.

4. Сигорский В.П. Математический аппарат инженера. – Киев: Технiка, 1975. – 768 с.

 

 

СОДЕРЖАНИЕ.

1. Устойчивость, покрытия, паросочетания…………………………….

1.1. Основные определения……………………………………………...

1.2. Определение чисел ε₀(G), π₀(G), π₁(G)……………………………..

1.3. Определение чисел β₀(G), β₁(G)……………………………………..

1.4. Определение чисел β₀⁺(G), β₀^-(G)……………………………………

1.5. Плотность p(G) графа G………………………………………………

1.6. Максимальный поток через сеть…………………………………….

2. Раскраска вершин и ребер графа………………………………………

2.1. Понятие раскраски вершин и ребер графа………………………….

2.2. Раскраска вершин графа……………………………………………

2.3. Раскраска ребер графа……………………………………………….

2.4. Алгоритм минимальной раскраски вершин ребер (графа)………..

3. Планарность графа………………………………………………………

Список литературы…………………………………………………………

 

Учебное издание