Книги и конспекты / Шпоры / 14
.pdf14.Раскраска графа. Хроматическое число. m-раскрашиваемый, m- хроматический граф. Критические и реберно-критические графы. Теорема о хроматическом числе композиции графов.
Вершинной раскраской графа называется такое приписывание цветов его вершинам, что никакие 2 смежные вершины не окрашиваются в один цвет.
Раскраской графа G = (X,F) в m цветов, или m-раскраской, называется разбиение его вершин X на классы C1 , С2 ,..., Сm попарно несмежных вершин.
Классы Ci называются одноцветными классами.
Хроматическое число (G) графа G определяется как наименьшее m, для которого граф G имеет m-раскраску.
Граф G называется m-раскрашиваемым, если (G) m , и m-хpоматическим, если (G) m .
Хроматическое число для некоторых простых графов легко вычисляется. Если Fm — полный m-вершинный граф, то (Fm ) m , (Сk ) 3 , где Сk -
простой цикл нечетной длины k, (С2n ) 2 .
Граф G называется критическим, если (G x) (G) для любой вершины x;
если при этом (G) m , то граф G называется m-критическим.
Другое определение: граф называется критическим, если при удалении из него любой его вершины изменяется его хроматическое число.
Очевидно, что если G — критический граф, то (G) 1 (G x) для каждой его вершины x.
Критический граф может обладать еще одним свойством: (G u) (G) 1
для любого ребра u графа G. В этом случае граф G называется реберно-
критическим. При (G) n граф G называется n-реберно-критическим.
Другое определение: рѐберно-критический граф – граф, если при удалении из которого любого ребра меняется его хроматическое число.
Теорема о хроматическом числе композиции графов.
G ( X , F ), H (Y , P) |
|
Q G H (Z, R) |
(Q G H ) (G) (H ) |
||||||||||||||
► Z X Y Rz |
(Fx Y ) ( X Py ) |
Z1 (x1 y1 ) ; Z 2 (x2 y2 ) |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
F Y |
|
x |
|
F |
|
|
Z 2 Rz1 (Fx1 Y ) ( X Py1 ) |
(x2 y2 ) |
x1 |
или |
|
2 |
x1 |
или |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
X P |
|
y |
2 |
P |
|
|
|
|
|
|
|
|
|
|
|
|
y1 |
|
|
y1 |
|
||
G C1...Сn |
n > m |
|
Z (Ci S j ) |
|
|
|
|
|
|
|
|||||||
H S1...Sm |
|
|
|
|
|
ij |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C1 S1 ..............C1 Sm |
|
|
|
|
|
|
|
|
|
|
|||||||
.......... |
|
|
|
|
|
|
Z |
|
|
|
|
|
|
|
|
||
|
|
|
......... |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C |
n |
S |
.............С |
n |
S |
m |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
n m цветов (Q) n m (G) (H )
◄