N , :
Ui - i N
i =1, 2, ,N. (6.14)
UN = 0 (6.15) ,
(6.16)
, , . , . (6.16) , , , , , .. . , , , u1, u2, , uN , , , .
u1, u2, , uN U1, U2, , UN (6.16). m , Uj uj, j = 1,2, ,N, . , .
Um = tm,n+ Un ≤ tm,r + Ur, (6.17)
Um = tm,r + ur (6.18)
,
Um um ≤ Ur ur, (6.19)
m , Um um , (6.19), (6.17). , ,
m ≠ r. (6.20)
s,
s ≠ m,
(6.21)
s ≠ r,
Um um = Ur ur = Us us, (6.22)
, , N,
UN uN = 0. (6.23)
. . (6.16), .
(6.24)
. i N, ti,N = ∞, ti,n = 1030 - . .
(6.25)
(6.26)
, (6.25) . (tij) . , . , , . k- (k+1)-
|
|
, (6.27)
. (6.28)
(6.25) (6.28) . i N . i N . i N k . , , ..
. (6.29)
. , , . i N , N-2 . , , (6.16), , N 2 .
- N . ,
- i j, k- .
: , ,
. (6.30)
, , .
. , . , , , .. , , .
.
, , .
. , .
, (6.30). i .
l .
, ( ) , . (6.30), . ( , ) , : , .
|
|
.
(.6.1) .
. 6.1.
i- j- ( ), tij. , k (). k j- , , .
i- N- .
i 1 N j 1 N, , . , , , , , .. .
(.6.11)
6.11
j i | f1(i) | j1 | f2(i) | j2 | f3(i) | j3 | f4(i) | j4 | |||||||||
∞ | ∞ | ∞ | ∞ | ∞ | - |
| 1,3 | 1,3 | |||||||||
∞ | ∞ | ∞ | ∞ | ∞ | - | 5,7 |
| 1,2 | |||||||||
∞ | ∞ | ∞ |
| - | 3,8 | 3,8 | 3,8 | ||||||||||
∞ | ∞ | ∞ | ∞ | ∞ | ∞ | - |
| 3,4 | 3,4 | ||||||||
∞ | ∞ | ∞ | ∞ |
| - | 5,8 | 5,8 | 5,8 | |||||||||
∞ | ∞ | ∞ | ∞ | ∞ | - |
| 3,6 | 3,6 | |||||||||
∞ | ∞ | ∞ | ∞ |
| - | 7,8 | 7,8 | 7,8 | |||||||||
∞ | ∞ | ∞ |
| - | - | - | - |
f1(i) i (i= ) , . j1 , .
f2(i)= - i- (i= ) j2(i).
f3(i)= - i- (i= ) j3(i).
F4(i)= - i- (i= ) j4(i).
fk(i), f4(i) f3(i), .
6.11. , .
, 7 . . , .
10 . j3(2) = 1, .. ( ).
min t18=7
min t28=10
min t48=7
1-3-8 , 3-8 .
|
|
1. ?
2. ?
3. i - ?
4. ?
5. ?
6. , ().
7. ?
8. ?
9. , ?
10. ?