. G , , , .
, .
, . .
2 :
1) min () ().
2) .
. , , , .
. , .
. , , 1 .
:
. Max .
. .
. Min .
. Min .
. Min , .
. min , .
: G = (x, G)
4 + 6 = 5 + 5 = 10
. , , , . a, m, 0
ʸ: G . .
.
G , G. 1.
t (G)
, (9.3)
, | X | = n, Si i - .
.
G=(X, U) , , , , .. (. 9.1).
, , (. 9.2).
, , , , . . , , (f6 . 9.1).
, n, m f :
|
|
n m + f = 2.
. , , K5 K3,3 (. 9.3,,).
, , , . , a b, , (. 9.3,,). , a, b ( ).
. , , K5 K3,3.
-.
, , , Q(G).
Kn c n ³ 4 Q(G)
.
.
(u1, u2,..., uq) , u1 uq.
, , , . 3.1, :
m1 ={ u1, u5, u2 }, m2 ={ u1, u5, u2, u3, u10, u4 }, m3 ={ u1, u5, u8, u10, u4 },
m4 ={ u1, u5, u8, u10, u4, u2, u9, u7, u6, u3 } .
, .
(). , .
, , . 3.1, (m4), , . 3.2, .
, , , ( , ).
, m1 m3 , m2 , x1 .
, , . , . , , m3 , . 3.1, . 3.2 . .
. ,
(x1, x2,..., xq), , . . x1 = xq.
. 3.3
,
.
n (G) , . :
n (G) = m n + 1. (3.1)
, .