G=(V,E), (u,v)ÎE c(u,v) ³ 0, . (u,v)ÏE, c(u,v)=0.
2 : s t. , ...
G=(V,E), .
G , :
1. , : u,v V;
2. : u,v V;
3. : u V - {s,t}.
.
.
, . - .
:
( ) , . - G s t .
v, deg-(v)>0 ( ) deg+(v)=0 ( ) , w, deg+(w)>0 deg(w)=0 .
, ( ).
G=(V, E) V S T=V \ S, sÎS tÎT.
(S,T) , .
f (S,T) f(S,T) .
( ).
-:
.
.
, .
, . .
(cij, cji) .
, , .
j, i, [aj, i], aj .
-
1. (i,j) :
a1=¥ 1 [¥,-].
i=1.
- Si, j, i .
Si¹Æ, 3, 4.
|
|
- Si k, ,
ak=cik k [ak,i].
(k=n), , 5.
i=k 2.
- ( ). i=1, , 6.
i¹1, r, i, i , r.
i=r 2.
- ( ).
, p- .
, :
, , fp fp .
(i,j), , :
a), ij;
b) , j i.
, 4. i=1. 2.
- ().
a) m :
b) (i,j) .
a>0, , (i,j), a.
b>0, b.
, a>0 b>0 .
: , , , , , .
G 1, 2,, n ( ) 1, 2,, m ( ), . , G ( ) (, ).
, , . , .
G , , . , G = (, )
, , , , , , .
:
- .
:
- G, = [aij] :
aij = 1 G (xi, xj)
aij = 0 G (xi, xj)
- G n m . G B=[bij] n´m, :
|
|
bij = 1, xi aj
bij = -1, xi aj
bij = 0, xi aj
, , , , 1, 1, 0.
G , , , , 1, +1.
.
- <{ a,b,c,d },{ u,v,w,x }; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>. , , , . <{ a,b,c,d }; {(a,b), (b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}>. (v 1 ,v 2) (v 2 ,v 1), . , . {{ a,b },{ b,c },{ a,c },{ c,d }} (V,E), V , E .
3.
a | b | c | d | |
A | ||||
B | ||||
C | ||||
d |
4.
u | v | w | x | |
D | ||||
C | ||||
B | ||||
A |
. .
e1,..,em , ei,ei+1 .
.
G .
, .
1 , .
, .
, .
.
.
:
(1,2), (1,2,4,7), (3,4,5,6)
(1,2,4,7,8,4)
(1,2,4,7,8,4,2) ,
(1,2,4,7,8,4,1)
(1,2,4,1)
=3
G .
, .
, .
, .
, , .
, .
, .
, b (a,b)- (b,a) .
.
.
G=<M,R> - , a,b . (a,b)- a b ρ(a,b). ρ(a,a)=0. :
|
|
¾ ρ(a,b)≥0;
¾ ρ(a,b)=0Ûa=b;
¾ ρ(a,b)= ρ(b,a);
¾ ρ(a,b)≤ ρ(a,)+ ρ(,b).
={a1, a2,,an}, P=(pij), pij= ρ(ai, aj), .
a . .
G d(G): . , d(G)=e(a).
G r(G): . , e(a)=r(G). .
(deg v) v G , v.
0 .
1 .
G .
() v , v.
() v , v.
:
:
.