- , , , , , . , , . , , , .
. G = (X, ), , - . , .
S a(i, j) > 0 (i, j). . 1 , S.
. 1.
:
1: (S, a), (a, b), (b, c), (c, d), (d, b), (b, S)
2: (S, a), (a, b), (d, b), (d, c), (c, b), (b, S)
3: (S, b), (b, c), (c, d), (d, b), (d, a), (a, S)
4: (S, b), (b, d), (d, c), (c, b), (b, a), (a, S).
- . ,
3 + 2 + 1 +3 + 7 + 6 = 22
. ( ), () , .
, . 2.
. 2.
, , (b, ) , .
( ) :
(S, a), (a, b), (b, c), (c, d), (d, e), (e, c), (c, b), (b, S)
3 + 2 + 5 + 1 + 3 + 7 + 5 + 6 = 32
:
1. , ' ( , ) ( ). , '.
2. , . , , . , , d(x). G () , (). , ( d-(x)), a - ( d+(x). d-(x)=d+(x) .
, G, "S". , "t"? - R, "S", "t". R1 R2. , R1 "S" "t". R2 "t" "S". R', R2, R1. R' "t" "t" , R.
|
|
: R' = R - . :
1. , .