4.1 (n = 10), , .
( ) S(S = 1,..,n) .
( ) T0 = 2. , .
, , , , , 1, .
. , S . , S t.
(Lsj,i), Lsj S j, I .
. , :
:
0. S Lss = 0, Lsj = ∞. (Lsj,i).
1. r, Lsr = min(Lsj). r .
2. .
3. , r, 1, Lsj = min(Lsj, Lsr + Lrj). 1.
. :
0. , S. , S. aij = 1. , S.
1. . :
) , ;
)
) ( ), . ( ) .
|
|
2. (T0 + 1) . 1.
4.1 -
( 1)
1:
2→1 4.2 -
3→7→1 ( 1)
4→1
5→1
6→3→7→1
7→1
8→10→7→1
9→10→7→1
10→7→1
- | - | - | - | - | - | |||||
- | 50/4 | 16/7 | 45/2 | 106/8 | 55/4 | - | 88/5 | 56/8 | 133/8 | |
- | 111/7,3 | 67/4,6 | 91/7,6 | 126/4,6 | 28/7,3 | 79/8,10 | 42/7,10 | 37/7,10 | 103/5,8 |
4.1- ( 1)
4.3 -
( 2)
2:
1→2
3→7→1→2
4→2
5→1→2 4.4 -
6→3→7→1→2 ( 2)
7→1→2
8→10→7→1→2
9→10→7→1→2
10→7→1→2
- | - | - | - | - | - | - | - | - | ||
50/4 | - | - | 35/1 | 40/1 | 65/4 | 21/1 | 58/1 | - | - | |
111/3,7 | - | 31/1,7 | 143/3,6 | 75/4,1 | 70/1,4 | 56/4,1 | 83/4,6 | 13/4,6 | 42/1,7 |
4.2- ( 2)
4.5 -
( 3)
3:
1→7→3
2→1→7→3
4→1→7→3
5→1→7→3 4.6 -
6→3 ( 3)
7→3
8→6→3
9→10→7→3
10→7→3
- | - | - | - | - | - | - | - | |||
16/2 | - | - | 47/6 | 83/6 | 60/7 | 62/6 | 30/6 | 60/6 | 31/7 | |
67/6,4 | 31/7,1 | - | 36/7,1 | 41/7,1 | 160/2,4 | 116/2,1 | 46/7,10 | 41/7,10 | 45/6,8 |
4.3- ( 3)
4.7 -
( 4)
4:
1→4
2→4
3→7→1→4
5→1→4 4.8 -
6→4 ( 4)
7→1→4
8→6→4
9→10→7→1→4
10→7→1→4
- | - | - | - | - | - | - | - | - | ||
46/2 | 35/1 | 125/2 | - | 45/1 | - | 26/1 | 53/6 | 83/6 | - | |
91/6,7 | 142/6,3 | 36/1,7 | - | 72/2,1 | 76/1,7 | 51/2,1 | 88/2,1 | 143/6,8 | 47/1,7 |
4.4- ( 4)
4.9 -
|
|
( 5)
5:
1→5
2→1→5
3→7→1→5
4→1→5 4.10 -
6→3→7→1→5 ( 5)
7→1→5
8→5
9→10→7→1→5
10→7→1→5
- | - | - | - | - | - | - | - | - | ||
106/8 | 40/1 | 83/6 | 45/1 | - | 81/8 | 31/1 | 68/1 | 119/6 | 78/8 | |
126/6,4 | 75/1,4 | 41/1,7 | 70/1,2 | - | 80/1,4 | 93/6,3 | 209/6,9 | 88/8,10 | 52/1,7 |
4.5- ( 5)
4.11 -
( 6)
6:
1→7→3→6
2→1→7→3→6
3→6
4→6 4.12 -
5→1→7→3→6 ( 6)
7→3→6
8→6
9→10→8→6
10→8→6
- | - | - | - | - | - | - | - | |||
55/4 | 65/4 | 60/7 | - | 81/8 | - | 22/3 | 134/5 | 108/8 | 33/8 | |
28/3,7 | 70/4,1 | 160/4,2 | 76/7,1 | 80/4,1 | - | 54/8,10 | 73/9,10 | 43/8,9 | 43/3,7 |
4.6- ( 6)
4.13 -
( 7)
7:
1→7
2→1→7
3→7
4→1→7 4.14 -
5→1→7 ( 7)
6→3→7
8→10→7
9→10→7
10→7
- | - | - | - | - | - | - | - | |||
- | 21/1 | 62/6 | 26/1 | 31/1 | 22/3 | - | 36/10 | 31/10 | - | |
79/10,8 | 56/1,4 | 116/1,2 | 51/1,2 | 93/3,6 | 54/10,8 | - | 40/3,6 | 70/3,6 | 64/1,8 |
4.7- ( 7)
4.15-
( 8)
8:
1→7→10→8
2→1→7→10→8
3→6→8
4→6→8 4.16-
5→8 ( 8)
6→8
7→10→8
9→10→8
10→8
- | - | - | - | - | - | - | - | |||
88/5 | 58/1 | 30/6 | 53/6 | 68/1 | 134/5 | 36/10 | - | 25/10 | 100/9 | |
42/10,7 | 83/6,4 | 46/10,7 | 88/1,2 | 209/9,6 | 73/10,9 | 40/6,3 | - | 182/5,6 | 70/1,7 |
4.8- ( 8)
4.17-
( 9)
9:
1→7→10→9
2→1→7→10→9
3→7→10→9
4→1→7→10→9 4.18-
5→1→7→10→9 ( 9)
6→8→10→9
7→10→9
8→10→9
10→9
- | - | - | - | - | - | - | - | - | ||
133/8 | - | 60/6 | 83/6 | 119/6 | 108/8 | 31/10 | 25/10 | - | 105/8 | |
37/10,7 | 113/6,4 | 41/10,7 | 143/8,6 | 88/10,8 | 43/10,8 | 70/6,3 | 182/6,5 | - | 81/6,8 |
4.9- ( 9)
|
|
4.19 -
( 10)
10:
1→7→10
2→1→7→10
3→7→10
4→1→7→10 4.20 -
5→1→7→10 ( 10)
6→8→10
7→10
8→10
9→10
- | - | - | - | - | - | - | - | |||
27/7 | - | 31/7 | - | 78/8 | 33/8 | - | 100/9 | 105/8 | - | |
103/8,5 | 42/7,1 | 45/8,6 | 47/7,1 | 52/7,1 | 43/7,3 | 64/8,1 | 70/7,1 | 81/8,6 | - |
4.10- ( 10)
4.2 :
1. ?
2. ? ? ? ?
3. , .
4. , ?
5. ?
6. , ? ?
7. ?
8. ?
:
1. .
2. (), . () . , . , , .
3. , .
4. , s . , N s t.
5. . , .
6. .
7. .
8. :
0. , s. , s, asj=1. , , s.
1. . :
) , ;
) ;
) ( ), . ( ) .
|
|
2. (+1) . 1.