, . .
, . , . -, vi vj (vi ‑ vj) (vj ‑ vi).
( ) , , . , , . - ( ). , : (, , , ).
26 : () {1,2,3}, {4,5}, {6,7,8} {9}. () , -, {1,2,3}, {4} {5}.
1) , .
2) .
3) .
4) .
. , , . 27 , .
: ( )
G =(V, E) k . :
, , . , ( ). , . - (-) . , - (-) .
28 () , () () -.
g(G), , k. , ‑ g(G) = 1 ‑ g(G) = k . g(G) = ‑ + 1 g(G) = ‑ +k . , , . , - g(G).
|
|
, , .
( k) g*(G). , g(G) +g*(G)= .
, .
() , . , . , .
29 {1,2,5} {3,4,6,7,8} . {1,2} {3,6,7,8} .
, - .
: G, K -. () G , () G K.
.
: .
, S .