6,7
:
. -
G=(V, E) , , .
G=(V, E) , :
1) , ;
2) , , n − G.
, ( ). , − .
G=(V, E) s t f = , , :
1) ;
2) =
, r − .
, . : , .
f = , r .
. , . , . , .
.
f,
-.
.
, .
. , , , , . , . , , .
, :
− ;
− .
:
1) ;
2) , ;
3) .
. j : , , . , +, − -. , , .. .
|
|
-
.
. : .
s: ( , ). , . .
.
i (, , ) j:
j, , , ; j ;
j, , , ; j .
i , .
, , t , . , , , .
, , s X . . , , , , .
.
, , s t. t: t , t i .. : . , +, , , -, . − .
, s, .
.