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

Раскраской вершин графа G = < V, U > называется разбиение носителя V

графа G, при котором каждое подмножество V_i не содержит ни одной пары смежных вершин.

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

Вершины, окрашенные в один цвет, называют соцветными.

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

Если h(G)= n, то граф называется n-хроматическим.

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

I – хроматический граф это пустой граф.

Теорема 2.1. Граф является 2-хроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.

Двудольный граф – 2-хроматический граф.

Любое дерево – 2-хроматический граф.

Оценки химического числа 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), используя рассмотренные теоремы.

2

1 3

7

6 4

5

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

5

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. ■