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

Раскраской ребер графа G = < V, U > называется разбиение сигнатуры U графа G, при котором каждое подмножество U_i не содержит ни одной пары смежных ребер.

Каждому подмножеству сопоставляется краска, в которую окрашиваются все ребра этого подмножества.

Ребра одного цвета называются соцветными.

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

Если H(G) < q (q – число красок и раскраска удовлетворяет определению), то граф называется реберно q-раскрашиваемым.

Теорема 2.6. Если граф G- двудольный граф и его максимальная степень равна s(G), то

H(G)= s(G). (2.8)

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

H(F_n) = n, если n-нечетное (n 1);

H(F_n) = n – 1, если n- четное.

Хроматический класс H(G) графа G совпадает с хроматическим числом h( ) графа = < , >, определяемого следующим образом: вершины из взаимно однозначно соответствуют ребрам графа G и

_а Г _b. когда соответствующие ребра графа G смежны.

Пример 2. Построить для графа G (рис. 2.3) граф = < >.

Обозначим в графе G ребра буквами (рис. 2.5а). Используя определение графа = < , >, построим этот граф (рис. 2.5б).

2

а b

1 3

k

f g 7 c

6 4

e d

5

G

a)

a b

k c

g d

f e

б)

Рис. 2.5

Согласно определению

H(G)= h( ).

Таким образом, определение H(G) сводится к задаче определения хроматического числа h( ). ■

2.4. Алгоритм минимальной раскраски вершин (ребер) графа 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.■