3. , 2 ■
(xi, xj) p ( ). (xi, xj) p, xi p -, xj, p, . , . p , uj < cj, uj > 0, .
4. p , 2 , - 1, ■
3. . p = z 1→ z 2→...→ zk .
1. D = , i = 0.
2. i = i + 1.
3.
Di =
4. D = min{ D, Di }.
5. i < k -1, 2; 3 ■
D , p ( ).
9. p = x 1→ x 3 → x 5→ x 6, 8 (. 2.5). D = = 12.
:
i = 1, vj = (x 1, x 3), cj = 2, uj = 0, D 1 = cj - uj = 2, D = min(D, D 1) = 2;
i = 2, vj = (x 3, x 5), cj = 1, uj = 0, D 2 = cj - uj = 1, D = min(D, D 2) = 1;
i = 3, vj = (x 5, x 6), cj = 4, uj = 0, D 3 = cj - uj = 4, D = min(D, D 3) = 1.
, p = x 1→ x 3→ x 5→ x 6 1. , 1 ■
4. , 3 ■
4. u'. u' u, p D :
= (j = 1, 2,..., m). (9)
10. u' , 7 - 9. p = x 1→ x 3→ x 5→ x 6 . 0, 1. (. .2), u' = (2, 1, 1, 1, 1, 1, 0, 2, 1).
5. 1 , - 4 ■
5.
1. u' , (9), S;
2. (u') = (u) + D, (10)
(u) u (. 1 2) ■
, u, , u' ó (u'). ( - ) .
|
|
6. u = (0, 0,..., 0) ■
- ()
1. u = (0, 0,..., 0).
2. u. 7 ; u . 3 3 .
3. p , .
4. D , u.
5. u' (9), u, p D.
6. u = u' 2 ■
7. j (j = 1, 2,..., m) -, , , - ■
, . , ( -) 1 - - , .
11. , , .10.
\
.10
.
1. u = (0, 0, 0, 0, 0).
2. , 7. , - :
3.
:
3.1. 1
3.2. 2
( 4) , . 3.2.
3. (. 2). : 1→2→4.
4. (. 3). D = 8; D 1 = 8, D 2 = 6.
5. (. 4). u' = (6, 0, 0, 6, 0) 2.
2. , 7. , - :
4.
:
|
|
4.1. 1
4.2. 2
, 2, . 4 -, (2, 4) , 3 , . 2- , 2 3 2.
4.3. 3
, . 4.3.
3. (. 2). : 1→3→4.
4. (. 3). D = 5; D 1 = 5, D 2 = 4.
5. (. 4). u' = (6, 4, 0, 6, 4) 2.
2. , 7. , - :
5.
:
5.1. 1
5.2. 2
5.3. 3
4 (), : (2, 4) (3, 4) - ( ). - 2. , u = (6, 4, 0, 6, 4), - , , .. , (u) . , , 10, (u) = 10 ■
|
|
6. , , . . 11.
01 | 02 |
03 | 04 |
05 | 06 |
07 | 08 |
09 | 10 |
11 | 12 |
13 | 14 |
15 | 16 |
■
7. , , .1, :
1) (12,7,3,1,2,11,14,13,5,6,12,7).
2) (3,4,18,4,5,19,3,4,8,2,7,3).
3) (1,9,4,27,8,33,5,25,3,2,5,20).
4) (9,6,4,28,3,2,31,4,22,5,2,7,).
5) (24,5,8,9,29,3,2,6,33,41,2,21).
6) (9,28,27,10,8,9,6,19,8,3,7,24).
7) (5,8,7,8,5,2,11,2,3,8,18,9).
8) (10,3,2,29,35,41,8,5,27,10,7,9).
9) (44,15,8,3,32,39,8,7,25,29,3,12).
10) (22,5,28,19,4,6,8,1,19,7,4,4).
11) (5,8,1,4,15,33,4,22,5,30,1,2).
12) (11,14,13,5,8,18,9,10,3,27,10,8).
13) (9,6,19,8,3,2,31,33,4,22,5,5).
14) (4,6,8,1,19,7,4,8,7,3,12,22) ■
, ()
,
,
,
,
,
,
1-
2-
,
- ()
8.
1.
2.
3. -
4.
5.
, , -. , . , , , , , , , ( 4). : -. , ; -, . , , , , , - . - , ( ).
. , (), - ( ). . ( - ), ( ).
|
|
() (x, y) G l (x, y), . , , - .; , , .. ( ), l (x, y) = ¥.
P () G L (P) ( - P). , . G P L (P). : P, a b, -, P', a b, , L (P) ≤ L (P'). , , . , (. 6-3), .. , - .
, , -:
1) , - G;
2) G .
, , , , . - , , -. (), - ().
. 2 . 3 . - . 4 - (). , , ( ), - (), .
, -.
, - 1959. . , . - S , -. S b , , b, S.
, G = á X, ñ n . - , 0 n 1 - 0. (i, j) i j l (i, j); , , l (i, j) = ¥. L (P) . , , X0, X1, .. 0, 1, ..
(). - G. ∞.
, - . ∞, , . ( ). - P, - T. ( ) - , R (x) - , x 0 x.
|
|
0 ().
P (0) = 0, c = 0, T (x) = ¥ ( x ≠ 0); R (x) , ).
i. :
. x :
1)
Z = P (c) + l (c, x); (1)
2) Z < T (x), T (x) = Z, R (x) = c. T (x) R (x) .
. x ( - , ); c = x; - P () T ().
. , i = i +1 i. F.