Книги и конспекты / Шпоры / 15
.pdf15.Теорема о хроматическом числе произведения графов. Теорема о
хроматическом числе суммы графов. |
|
||||
Теорема о хроматическом числе произведения графов. |
|
||||
Хроматическое число (G H ) min( (G), (H )) , где G ( X , F) , |
H (Y , P) . |
||||
►Пусть G : n (С1 ,...Cn ) |
H : n (S1 ,...Sm ) |
|
|||
G H Q(Z, R) |
|
Z X Y , |
Rz Fx Py |
|
|
Z (C1 S1 ) (С2 |
S2 ) ... (Cn Sm ) |
|
|||
С1 S1 |
..........С1Sm |
|
|
|
|
|
|
|
(n m) - число возможных |
|
|
|
|
|
|||
|
|
|
|
|
|
Cn S1 |
..........Cn Sm |
|
|
|
xSy – x смежно с y
ASB – 2 множества смежны, если хотя бы 2 значения из них смежны.
пусть n>m |
Z1 |
(x1 |
, y1 ) |
смежны, если Z |
|
Rz |
Fx |
Py , x2 |
Fx |
, y2 Py |
|
Z2 |
(x2 |
, y2 ) |
2 |
||||||||
|
|
|
1 |
|
1 |
1 |
1 |
1 |
|||
|
|
|
|
|
|
|
|||||
Получаем раскраски: |
|
|
|
|
|
|
|
|
|||
m |
|
|
|
n |
|
|
|
|
|
|
|
Ti (Сi S j ) |
n штук Tj (Ci S j ) m штук |
|
|
||||||||
j 1 |
|
|
|
i 1 |
|
|
|
|
|
|
|
в Ti или T j нет смежных вершин, можно раскрасить |
|
|
|||||||||
(G H ) m n , или m ,или n, но так как m<n |
(G H) m , то есть |
минимальная.◄
Теорема о хроматическом числе суммы графов.
(G H ) max( (G), (H )) , где G ( X , F) , |
H (Y , P) . |
|
|||||||||||
► Пусть G : n |
(С1 ,...Cn ) |
H : n (S1 ,...Sm ) |
|
|
|||||||||
G H Q(Z, R) |
|
Z X Y , |
R Fx {y} {x} Py |
|
|
||||||||
пусть n>m |
|
|
|
|
|
|
|
|
|||||
Z1 |
(x1 |
, y1 ) |
смежны, если (x2 , y2 ) Z 2 Rz |
Fx |
{y1} {x1} Py |
|
|||||||
Z2 (x2 , y2 ) |
|||||||||||||
|
|
|
|
1 |
1 |
1 |
|
||||||
|
|
|
|
|
|
|
|
|
|
||||
x2 Fx , y2 y1 |
|
С1 S1 |
..........С1Sm |
|
|
|
|||||||
|
|
|
|
|
|
|
|||||||
x |
x , y |
|
P |
или |
|
|
|
|
|
||||
|
1 |
|
|
|
|
|
|
|
|
|
|
||
2 |
1 |
|
2 |
|
y1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Cn S1 |
..........Cn Sm |
|
|
|
||
(C1S1 )(C1S2 ) - могут содержать смежные вершины |
|
||||||||||||
(C1S1 )(C2 S3 )(C3 S4 ) -несмежные |
|
|
|
||||||||||
(Ci |
S j ) |
i i...n,1...i 1 несмежные вершины |
|
|
|||||||||
|
|
j j...m,1... j 1 |
|
|
|
|
|
(G H ) max(n, m) n , так как n>m.
◄