10.1. , , () .
10.2. , .
, .
. 17 , .
.
10.1. G = (S, U) = n, = m. :
1) G ;
2) G m = n - 1;
3) G m = n - 1;
4) ;
5) G , , - , .
10.2 (). n .
10.3. ()
G = (S, U), :
1) xiÎ S, , (. . );
2) xj, xi, G (. . ).
10.4. , .
10.5. x ,
10.6. .
10.7. .
10.8. .
, 0.
10.9. .
10.1. , . . 18 x7.
10.1. , ë . 18. : , x7, ; x1, x5, x8, x10, x11, x12 ; x7 x6 x3 x2 x10 ; 5; { x1, x5, x9, x10 } 4 .
10.10. G = (S, U) G¢ = (S¢, U¢), , S¢ = S G¢ , G.
10.10 , G , G¢ , G.
10.11. G G¢, , G¢ F(G¢) F(G).
.
10.2. 1) , , , .. ë.
2) .
10.2. . 19 G G¢.
|
|
.
10.3 (). G n ³ 2 .
.
10.4. G = (S, U) , = n, = m, k G. ë, , m n + k.
. i - Gi ni mi ë. G . , Gi ¢ Gi , , (ni 1) . , Gi ¢ i - Gi mi (ni 1) .
, ,
10.12. n (G) = m - n + k G.
10.13. n* (G) = n - k .
, n * (G) ë, G. , n (G) +n* (G) = m.
10.4 .
10.4.1. G ,
n (G) =0.
10.4.2. G , n (G) =1.
10.3. G, . 19, .
. G 8 , 14 1 . , 10.4, n (G) = 14 8 +1 = 7, n * (G) = 8 1 = 7.
G .
11.1. () G (), () G.
11.2. G , .
, , .
11.1. , , ë.
11.2. , , ë .
, .
11.1 ( ë ). ë, ë
. 1, G, ë . 20, , , . : G.
11.1. , G, ë . 20,
deg (x1) = 5, deg (x2) = deg (x3) = deg (x4) = 3, .. , , G .
|
|
1857 . ( ), . , , (). ë, , , . , . 21.
, . , , .
12.1. () G (), () G.
. 21 12.2. , -
, .
, . , .
, . , .
. ë , .. , .
3.1 , . , , , . , .
, .
13.1. , , ë , ë , , , .
13.2. , .
( ).
13.1. . 22 ë G ( G).
, :
1) ;
2) , .
13.3. , , ë .
13.4. ë, .
13.2. . 22 : 1, 2, 3, 4, 5. 1 , : 2, 3, 4, 5 .
13.1 (). G = (S, U) n = n, = m, f .
(13.1)
. G ¢ G. , n (n 1) , (13.1)
|
|
G ¢ . ë G ¢ G. , .
, (13.1) , , G , (13.1) .
. ë .
13.5. , ë.
. 23 ë G G1 G2.
13.2 ( ). , , K5 K3,3.
13.2.
13.3. , ë , K5 K3,3.
, .
13.6. ë sk (G) G ë, .
n :
(13.2)
13.7. t (G) G G, ë .
k, G G1, G2,, Gk.
, . n :
t (Kn) = (13.3)