Оценки химического числа h(G).

Теорема 2.2. Если максимальная степень вершины графа G равна S(G), то

h(G) S(G) + 1. (2.1)

Для большинства графов эту оценку можно улучшить.

Теорема 2.3. Граф G с максимальной степенью S(G) является S-раскрашиваемым, за исключением двух случаев:

1) при S(G)>2 граф содержит компоненту , являющуюся полным графом плотности p()=S(G) +1;

2) при S(G)=2 граф G содержит компоненту, являющуюся циклом нечетной длины.

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

Теорема 2.4. Для любого графа G = < V, U >

h(G) | V | - ε₀ + 1, (2.2)

где ε_{0 –} вершинное число независимости графа.

Теорема 2.5 Хроматическое число h(G) графа G удовлетворяет соотношениям:

h(G) h(G_a) h(G_b), где G= G_a G_b; (2.3)

h(G) = h(G_a) + h(G_b), где G= G_a+G_b; G_a G_b= Ø; (2.4)

h(G) min (h(G_a), h(G_b)), где G= G_a G_b. (2.5)

Пример 1. Оценить хроматическое число графа G (рис. 2.3), используя рассмотренные теоремы.

 

1 3

7

6 4

G

 

Рис. 2.3

По т.2.2 h(G) s(G) + 1, если s(G) – максимальная степень вершин графа G. в заданном графе G максимальная степень s(G) = s(3) = s(6) = 3, значит

h(G) 4. (2.6)

Перейдем к т. 2.3. Пункты 1 и 2 этой теоремы не выполняются, значит заданный граф G является 3-раскрашиваемым.

Для использования т.2.4 необходимо определить ε₀ (G) заданного графа G. Найдем ε₀ (G) (рис. 2.4)

2

1 3

7

6 4

3

7 7 2

4 4

6 3

5 5

4

4

3

7 4 4

5 Ø

7

Ø Ø Ø Ø Ø Ø Е₇

 

Е₁ Е₂ Е₃ Е₄ Е₅ Е₆

 

Рис.2.4

Одним из решений является ε₀ (G) = | {1,5,3} | = 3.

Подставляем ε₀ = 3 и | V | = 7 в формулу (2.2):

h(G) 7-3+1,

2,3 3 … h(G) 5,

2 h(G) 5, (2.7),

т.е. хроматическим числом заданного графа может являться одно из чисел 2,3,4,5. ■

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

Раскраской ребер графа 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б).

а b

1 3

k

f g 7 c

6 4

e d

G

a)

a b

k c

g d

f e

б)

Рис. 2.5

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

H(G)= h().

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