70
1
12 : - 11 . 3 , :
) ;
) ?
) 
) 
: 165 ; 55 .
2
2 3 ?
, 
. ,
: 200 .
3
4 , - 6 , - 3 . , 14 : 6 8 ?
14 13 . , 4 6:
:
2 , 2 3 , , , . 2 :
1. 1 2 ( 
)
2. 1 2 ( 
).
1 680 .
: 1 680 .
4
10 : 2 , 3 5 . , 10- ?
2 520.
: 2 520 .
5
Ȼ?
9. = 4, =3, =1, =1. ,
2 520.
: 2 520 .
1. ()
() G , S , G, H, S, . , . ( ) - .
.
G1 M1
, (1,2).
, , . , . , . .
|
|
|
1.
3.2 ( 3.2 ) (R,C).
2.
1 (R,C1)
3.
(1) 1, (,1), . 1 . 1.
3 .
1 - . 2.
2 .
.
1 1 .
, . , , .
.
. 1 (1,2). 1 . (1,5). (2,5) 1. . 5- . 1 6 . (2,6) 1. . . . - - . .
1. (1,5) . 1 . (1,6). 6 , (5,6) 1. . 1 6 = . 1 6. [1,5,6]. ..
: 1 5 6 8; 6 4 8; 1 7 8.
1568.
1 5 6 8
10 1 1 1
51 0 1 1
61 1 0 1
81 1 1 0
2.
, (: breadth first search). , , , , , . , , . , , . , ( ), ( ). . ( , , , , ).
|
|
|
1 procedure WS (v);
(* v;
, *)
2 begin
3 := Æ; <= v; [v]:=
4 while ¹ Æ do
5 begin <= ; ;
6 for u Î [] do
7 if [u] then
8 begin <= u; [u]:=
9 end
10 end
11 end
. 1 , , .
, WS , [v], v = V, . , , ,
 | |||||
| |||||
|
. 1 ( ), , .
3.
--, - , . , G -- .
:
1. .
2. .
3. 1. , , .
4. , , 3, , . .
:
. 1 1
. 2 2
. 3 3
, 3 ==> .
4.
, 1970 ., . 10 .
, . i- (layered network). , ki, ki s t. ki .
i- :
1. .
, Sk k. u ck(u) = c(u) f(u). , k k . , v, q(s, v) ≥ k. , . , . k (k ) ki, i+1 ki+1 = k.
2. .
|
|
|
k . f, k. . .
( ). j- s t. fj. , . . : , ( ), , ( ) . . . , . ck(u) = ck(u) fj(u).
. 1
2 5 . .
fj , ≠ Ø. , f = ∑ fj. - , fj S.
, fi , s .
. :
. 2.
.
. 3.
1 . k1 = 2.
.4.
2 . k2 = 3. , .
.5.
3 . k3 = 5.
5. .
. G=(X,), (), =|| 
||. s 
X t X., , , .. t R(s). R(s)- , s.
, . , G .
:
) s s x 
X;
) .
s t c >0, 
i, j. (s-t) . , s . ( ) , . , , s .
. G, 1, . . x, . , .
|
|
|
1.
.
+, .
1.
l(x 
) = 0 
, l(x 
) = ∞, x 
x , p = x .
2.
(p) = (x ) = { x 
} .
(2),
l(x ) = min { 
; 0+4}= 4,
, 3 .
4.
l(x )=4 ; p= x .
5.
.
.
| i / j | x
| x
| x 
| x 
| x 
| x 
|
x 
| --------- | |||||
| x
| --------- | |||||
| x
| --------- | |||||
| x
| --------- | |||||
| x
| --------- | |||||
| x
| --------- |
1- .
.
2.
(p) = (x ) = { x , x 
, x , x }.
l(x ) = min { ; 4+3}= 7,
l(x ) = min { ; 4+2}= 6,
l(x ) = min { ; 4+3}= 7.
3.
min{l(x ); l(x ); l(x )} = min{7,6,7} = 6.
4.
l(x ) = 6 ; p = x .
5. .
.
2.
(p) = (x 
) = { x , x , x }.
l(x ) = min {7; 7+4} = 7,
l(x ) = min {7; 6+2} = 7.
3.
min{l(x ); l(x 
)} = min{7,7} = 7.
.
4.
l(x ) = 7 ; p = x
5. .
.
2.
(p) = (x ) = { x , x , x , x }.
l(x ) = min { ; 7+5} = 12.
l(x ) = min {7; 6+2} = 7.
3.
min{ l(x ); l(x ) }= min{7,12} = 7.
4.
l(x ) = 7 ; p = x
5. .
.
2.
(p) = (x ) = { x ,x , x , x }.
l(x ) = min { ; 7+3}=10.
3.
min(x ) =10.
4.
l(x ) = 10 ; p= x .
5. . . .3
x () l(x ) + c(x ,x ) = l(x ). , x =x , x , x x x ;
l(x )+ C(x , x )= l(x )= 10.
= x .
, :
l( 
) + C( , ) = l( ) = 7 
= x 
.
l(x ) + C(x , x ) = l(x ) = 6 x = x 
.
l(x ) + C(x , x )= l(x ) = 4 x = x
, x x x , x . 
(x , x ) = (x , x , x , , x ). .
2- .
1. . , . .: 1978.;
2. . ,, . . . 2004;
3. . . . . . .. . - ., , 1965;
4. . . . . - ., , 1986.
