, : .<
, - , .
3.6 G. (2,2,3,2,1).
3.2.2 , ,
u v (u,v)- G , , .. ek , vk1 vk, k = 1,2,, n.
Ñ -, - . vk1 k, a vk .
u , v . . u = v, , .
.
, , , , , . u = = v , u v á u,v ñ.
, , u v, , .
; . G z(G). .
, .
3.7 (1,2,3,4,5,3,2) , ; (1,2,3,4,5,3) , ; (1,2,3,4) ; (1,2,3,4,5,3,1) , ; (1,2,3,1) .
M (, ) , |M|.
u v ( d (u, v)) á u,v ñ, .
Ñ , u v, d (u, v) = +¥.
G ( D(G)) .
G v r(v) = max d(v,v), " v Î V. v G , .
, n v, ( D(v,n)): D(v,n) = { u Î V | d(v,u) = n }.
3.8 , =1.
3.2.3
u v , . , .
, . , , . ; k(G).
|
|
G , : k(G) = 1. k(G) > 1, . , ( k(G)=|V|, r(G)=0), .
3.9 .
, , .
G(V,E) (), E ( , G ).
(), u,v Î V u v (.. ).
, , . , , .
Ñ .
3.2.4
G(V,E) G(V,E): G(V,E) Í G(V,E), V Í V E Í E, E V.
G Í G , , G G (. 3.10, ).
G , G (, ) G (.. ).
Ñ , . , .
G . , (n,m) - G k , (mn+k) .
3.10 (4,6) - G (), (, ), ) ; 2 (, ). : (mn+k) = 6 4 + 1 = 3. Þ 3 (, ).
) ) ) ) )
3.2.5
1. ? ?
2. ?
3. , ?
4. ? ?
5. ? ?
6. ? ?
7. ? ?
8. ?
9. ? ?
10. ? ?
11. ? ?
|
|
12. ?
13. ?
14. ?
3.3
3.3.1
.
, , . , , (.. ).
, k , Ck. , C3 , C4 .
n , . Kn, , n× (n 1)/2.
3.11
Ñ , , 1 : deg(v)=n1 " v ÎV.
.
:
; . , ( 2), .
G(V,E) E V (.. " u,v Î V (u,v)Î E () ).
3.3.2
( , ) G(V,E) , V1 V2: V1ÈV2=V, V1ÇV2=Æ , V1 V2. V1 V2 G.
, V1 V2, . |V1|= m |V2|= n, Km,n.
3.12 K3,3.
3.2 , .
, : {} { }. E .
3.3.3 ()
, , , , , . , , .
, .
, , , ..
(). .
, , . . , , , .
: n m + r = 2, n , m , r ( ).
3.13 K3,3. K5 .
K4 : . . 1,2,3 , 4 .
3.3.4
, , . (.. (u,v) (v,u)).
, ; , . .
|
|
3.14 , 1 , 5 .
3.3.5
, , .. . ( ).
1. G1(V1,E1) G2(V2,E2), , , E1: V2=V1, E=`E1 =V1´V1\E1. G2 , . : `G1(V1,E1). .
3.15 . .
2. v G1(V1,E1) ( v Î V1): v V1, , : V = V1\{ v }, E= E1\{ e = (v1,v2) | v1 = v v2 = v }. : G = G1(V1,E1) v.
3.16 C3 v = K2.
3. v G1(V1,E1) ( v Ï V1): v: V = V1È{ v }, E = E1. : G = G1(V1,E1) + v.
4. e G1(V1,E1) ( e Î E1): e: V = V1, E= E1 \ { e }; . : G = G1(V1,E1) e.
3.17 K2 e = `K2.
5. e G1(V1,E1) ( e Ï E1): e: V = V1, E = E1È{e}. : G = G1(V1,E1)+ e.
6. v1,v2 G1(V1,E1): v, , , , v. , .
3.18 (4,4)- K2.
7. G1(V1,E1) ( A Ì V1): A v, , , , v. V = V1 \ A È { v }, E= E1 \ { e = (u,v) | u Î A v Î A }È{ e = (u,v) | uÎ(A)\A }. : G = G1(V1,E1)/A.
3.19 K4 / C3 = K2.
8. G1(V1,E1): , .
9. v G1(V1,E1) ( v Î V1, v Ï V1): v, , v v . V = V1 È { v }, E = E1 È {(v,v)} È { e = (u,v) | uÎ+(v) }. : G = G1(V1,E1) v.
3.20 K2 v = C3; C3 v = K4
10. G1(V1,E1) G2(V2,E2) ( , , , ) G(V,E), V = V1ÈV2, E = E1ÈE2. : G = G1ÈG2.
3.21 `K3,3. = C3ÈC3. .
11. G1(V1,E1) G2(V2,E2) ( , ) G(V,E), V = V1ÈV2, E= E1ÈE2È{ e =(v1,v2) | v1 Î V1, v2 Î V2}. , , G1(V1,E1) G2(V2,E2). : G = G1+G2.
|
|
3.22 Km,n. = `Km + `Kn.
12. G1(V1,E1) G2(V2,E2) ( , ) G(V,E). V = V1×V2, (u1,u2) (v1,v2) , u1=v1 u2 v2, u2=v2 u1 v1. : G = G1×G2.
3.23
.
3.3.6
. , . , , , , .. , .
. ( ) . , .
:
1. .
2. .
3. .
() . :
1. , .
2. 1.
3. .
4. .
3.24 () () 4 .
) )
3.3.7
1. ? ?
2. C3? K3? C4 K4?
3. , ?
4. ? ? K2,4.?
5. .
6. ?
7. ?
8. ?
9. ?
10. ?
11. ?
12. ?
13. ?
14. 5 ?
3.4
3.4.1
, - , , , ( ), .. ().
. . .
: n, m. M(n,m), , .
Ñ , , .
G D (. .).
3.4.2
1) .
A(G) () n´n, i,j Î{ 1,2,,n } i - j - 1, i - j - ( i), 0 .
M(n,m)=O(n2).
. , , , , . .
, , , .. .
|
|
3.25 G D
Ñ , i- j- , , i j, .
3.26 , , :
2) .
( ) I(G), n m , :
:
3.27 G D
, 0 ( , ), .. ( ). . M(n,m)=O(n × m).
3) .
( ), . : . M(n,m)=O(n+2m), M(n,m)=O(n+m).
3.28 G D:
4) ().
. , , . M=O(2m).
3.29 () : G ( ) D ( ). () .
, .. , , 1. ,
1, , 1.
3.4.3
(). . .
, . .
.
1. .
2. ( ), .
3. , :
u;
;
(u), , , .
(LIFO), (.. , ). (FIFO), . .
3.3 G , .
. 1. . , . ; Þ " 1 .
2. . m ; " Þ stop >, m .
3. . . , , w . , . Þ , , . , , , . G , , á v,w ñ; , v . ! .<
3.30 . 3. : 3T. T={3}Þ 3: {2,5,6,4}T; T={2,5,6,4}Þ 2: {1}T; T={5,6,4,1}Þ 5: {8,9}T; T={6,4,1,8,9}Þ 6: {7}T; T={4,1,8,9,7}. Þ . , : 3,2,5,6,4,1,8,9,7. : 3T. T={3} Þ 3: {2,5,6,4}T; T={2,5,6,4}Þ 4: {7}T; T={2,5,6,7}Þ 7: {9}T; T={2,5,6,9} Þ 9: {8}T; T={2,5,6,8}Þ 8: {1}T; T={2,5,6,1}. . : 3,4,7,9,8,1,6,5,2.
( ).
3.4.4
1. ?
2. ?
3. ?
4. ?
5. ?
6. ()?
7. ?
8. ? ?
9. ?
10. ( )?
11. ?
12. , ?
3.5
3.5.1
() G . . , , . , , -, G.
3.31 , -. , -.
.
3.4 () . () .
3.5.2
( ) A » . .
() G (V,E), () , ( ) . vi () vj, (vi, vj) ¥. , ( ), 0. , . .
. , . - .
v1 vn
: , , .
vk (m,vr), v1 vk, . (¥,0) . . , vn.
:
1. v1 (¥,0), v1 (0,0) .
2. vn , :
a. vk (m,vr) , vj m+d (vk, vj) , vj. , , vk.
b. , . .
3. vn , , . ( ) , vn v1 .
3.32
|
) ) )
(. ), Þ ( 5 6), (5,) (6,). 5 Þ (5,) (. ). , , F, D. 5+3=8 Þ (6) Þ . ¥ Þ . min{12,15,7,6} = 6 Þ (6,) (. ). , 6+7=13>7 Þ . min=7 Þ (7,) . 7+4=11<15 Þ F F(11,E) . , F 11, A,B,E,F.
-
: D, G. vi vj . ..
vi vj { v 1 ,,vm }. :
1) , vi vj (.. D ).
2) .
3) vi vj: .
n , .. D(1), , D(n)=D.
3.33
v 1 v 2 v 3
D(1) . . . D(2) . . .
D(3) . . (i,j) D vi vj.
3.5.3
, , .., ( ) , , () .
.
, . .
: G(V,E) T(V,E).
(Cruskal) . , (V,E), , .
Œ , V , . , .
1) G, Œ, , Œ .
2) Œ.
3.34 .
(v 1, v 3). :
(v 1, v 3 ), (v 2, v 5 ), (v 1, v 2 ) ( (v 1, v 5 )), (v 4, v 5 ).
W=1+2+1+4=8.
3.5.4
, . , , . ( ) (), () . , .
, . .