1. G = (X, U) .
2. G = (X, U) G r, , , .
3. .
4. .
5. G .
6. 10 , .
7. .
8. .
9. .
10. .
, , , , .
T = (X, U), |X| = n. T n 1 . , . , xi, xj . G . n ³ 2 .
16.8. n . :
,
n 1 ,
n 1 ,
,
,
, , , .
, , . () . 16.33 K4 16 .
1- 䠠
2- 䠠
3- 䠠
4- 䠠
. 16.33. K 4
, 4 . , -.
G , , . , G . , G. () .
, , . m G = (X, U), |X| = n, |U| = m, , .
|
|
, . 16.34, G, . 16.34, ( ).
ࠠ
. 16.34. G () ()
16.4. G = (X, U) G = (X, U), X Í X, U Í U O G (O = (X, U), G = (X, U), U Í U).
16.5. O1 = (X1, U1) O2 = (X2, U2) G = =(X, U) (X = X1 = X2, U1 Í U, U2 Í U), ui Î U1 O1 uj Î U2 O2, O1 - ui + uj . , G (. 16.35, ) O1 (. 16.35, ) O2 (. 16.35, ). ui = u 3,4, uj = u 5,6, ui Î U1 O1 uj Î U2 O2. O1 - ui + uj = O1 - u 3,4 + u 5,6 (. 16.35, ).
ࠠ
⠠
. 16.35. G
16.9 (). nn-2 n .
16.1. Kn nn-2.
. . 16.36 , 3 T1 - T3.
. 16.36.
, , , .
G = (X, U) , xi Î X xj Î X, .
, n , , . , , , , , . nn-2 , , . . G = (X, U) ui Î U n(ui), . , , , . (). .
.
1. G = (X, U), . G1 = O + u 1, O X u 1 Î U .
2. G i i < n 1, G i +1 = G i + ui +1,
ui +1 G, , G i G i. i = n 1, 3.
|
|
3. .
16.10. i < n 1 G i +1 . G n -1 G.
, G (. 16.37).
. 16.37. G (); G ()
u 1,4 1. u 1,5 1. u 4,5, , .. u 1,4 u 1,5. u 3,6 u 5,6 2. , 8 (. 16.37, )
() :
A0A1¯2¯1A2p11p22A,
0 ;
1 , i = 1;
2 , ui ;
1 ui . p1 = 0, i = i + 1 A2, p1 = 1 p2;
p2 , n 1. p2 = 0, i = i + 1 2, p2 = 1 ;
.
() . . T = (X, U) T = (X, U), X Í X, U Í U. T . Ғ (xi, xj), (xi Î T, xj Ï T). . , T n 1. G. :
1 | 2 | 3 | 4 | 5 | 6 | |||
R = | 1 | 0 | 5 | 8 | 0 | 37 | 0 | . |
2 | 5 | 0 | 0 | 7 | 10 | 0 | ||
3 | 8 | 0 | 0 | 3 | 0 | 0 | ||
4 | 0 | 7 | 3 | 0 | 11 | 20 | ||
5 | 37 | 10 | 0 | 11 | 0 | 12 | ||
6 | 0 | 0 | 0 | 20 | 12 | 0 |
x 1 T = (X, U), X = { x 1}, U = Æ. , x 1. .
ui | n(ui) | ||
L= | (1, 2) | 5 | . |
(1, 3) | 8 | ||
(1, 5) | 37 |
(1, 2) (.. (x 1, x 2)). T = (X, U), X = { x 1, x 2}, U = {(1, 2)}. L , x 2. ,
ui | n(ui) | ||
(2, 4) | 7 | . | |
L= | (1, 3) | 8 | |
(2, 5) | 10 | ||
(1, 5) | 37 |
(2, 4) T, T. , X , L; X = { x 1, x 2, x 4}, U = {(1, 2), (2, 4)}. |X| = |X|, , x 4 , , L:
ui | n(ui) | ||
(4, 3) | 3 | . | |
(1, 3) | 8 | ||
L= | (2, 5) | 10 | |
(4, 5) | 11 | ||
(4, 6) | 20 | ||
(1, 5) | 37 |
, U = {(1, 2), (2, 4), (4, 3), (2, 5), (5, 6)}, |X| = |X|, , S1n-1n(ui) = 32. . 16.38 .
. 16.38. G
:
;
|
|
( ) ( ).
, ( ) . : x 1, x 2,..., xn n ³ n (). . n £ 5 , , () . , , ().
, , .
16.1. n , , , gi .
16.2. { x 1, x 2, x 3}, , g, S3 i = 1 d (g, ni), S, S3 i = 1 d (g, ni) = 1/2 P(x 1, x 2, x 3), S, S i (i = 1, 2, 3) T j (j = 1, 2, 3); P(x 1, x 2, x 3) , x 1, x 2, x 3; d (g, ni) g ni.
. 16.39 , 16.2 , x 1, x 2, x 3. g S g = 3,T g = 5.
. 16.39.
16.3. , xi . g x 1, x 2, x 3. g , x 1, x 2, x 3, .
16.2. x 1, x 2, x 3 g c (S, ), x 1, x 2, x 3 1/2P(x 1, x 2, x 3).
16.4. X = { x 1, x 2,..., xn }, G = { g 1, g 2,..., gk }. g 1 Ì G gi Î I, g 1 g 1.k, I, g 1 . I .
.
16.11. X = { x 1, x 2,..., xn } G = { g 1, g 2,..., gk }. G , (" g i Î G )(g i Î I).
I. , . .
1.
1. xi Î X S(T).
2. , i Î I ( ).
3. xi Î X .
4. . .
.
, -, G , G r .
|
|
, . , , , .
, .
, O(n), .
2 ( ).
1. xi Î X S0, S1,..., S i S i , S i.
2. S0, Smin S.
3. I, I, xi, xi .
4. S i +1, S. im Î I xj Î S i +1,
d (im, xj) ³ d (iq, xj), " iq Î I, " xj Î S i +1.
, xi S i +1. im (sm, tm) xj (si, ti) . S T.
5. xk Î S i +1 , 4. xk I.
6. 4 5 S j .
, . S(T), S(T). 2 O(n2). . 2.39, 2 1 S. 22 , 2.
.
, , , (. 16.40) :
(2+)*7, *+27, *(2+)7, 2+7*, (2+)7* ..
, , . *+27. .
. 16.40.
1. G = (X, U), . 16.41,. .
: . 16.41,. 16.41,, .
. 16.41. G : ; ; ; .
2. , . 16.42,.
: : t = n n - 2.
, , t = 3 3 - 2 =31 = 3.
, . 16.42,.
ࠠ
. 16.42. () ()
3. G = (X, U), . 16.43,. (), .
. 16.43. G
: R .
1 | 2 | 3 | 4 | 5 | |||
R = | 1 | 0 | 4 | 0 | 6 | 5 | . |
2 | 0 | 8 | 4 | 2 | |||
3 | 0 | 9 | 3 | ||||
4 | 0 | 7 | |||||
5 | 0 |
1.1. . u 25. M = { u 25}.
|
|
1.2. , 3.
1.3. |M| ¹ n - 1, 1.
2.1. u 35, M = { u 25, u 35}.
2.2. , .
2.3. |M| ¹ n - 1, 1.
3.1. u 12, M = { u 25, u 35, u 12}.
3.2. . , 3.
3.3. |M| ¹ n - 1, 1.
4.1. u 24, M = { u 25, u 35, u 12, u 24}.
4.2. . , 3.
4.3. |M| = 4. 4 = 5 1, . () (. 16.43,). S = 2 + 3 + 4 + 4 = 13.
. 16.43. () G (. 6.43 )
4. G, . 16.44, .
. 16.44.
1.1. . x 1. :
1.2. L1 (1, 2) T =
={(1, 2)}.
1.3. , 4.
1.4. |X| ¹ |X|, , 5.
1.5. L1 , x 2 L1 L2.
.
2.2. L2 (2, 3) T = {(1, 2); (2, 3)}.
2.3. , 4.
2.4. |X| ¹ |X|, 5.
2.5. L , x 3, . 2.
.
3.2. L3 (3, 4) T = {(1, 2); (2, 3); (3, 4)}.
3.3. , 4.
3.4. |X| ¹ |X|, 5.
3.5. L , x 4, . (1, 4) L4, . 2.
.
4.2. L4 (4, 5) T = {(1, 2); (2, 3); (3, 4); (4, 5)}.
4.3. , 4.
4.4. | X| ¹ |X|, 5.
4.5. L , x 5, . (2, 5) L5, .. . 2.
.
5.2. L5 (3, 6) T = {(1, 2); (2, 3); (3, 4); (4, 5); (3, 6)}.
5.3. , 4.
5.4. |X| = |X|, 6.
5.6. (. 16.45): T = {(1, 2); (2, 3); (3, 4); (4, 5); (3, 6)} c S = 2 + 5 + 1 + 3 + 4 = 15.
.
. 16.45.
5. G r, . 16.46, .
. 16.46.
: :
s: 10 - 1 = 9,
t: 9 - 2 = 7.
t , , t.
, . , , , t = 6. , .
, , , (. 16.47). :
Lå = 1 + 2 + 1 + 2 + 4 + 3 + 3 + 9 = 25.
. 16.47.
1. .
2. , .
3. , , ?
4. ?
5. .
6. .
7. .
8. .
9. ?
10. .