G - , . a b , Si (a, b), 璺 a b . , . a b : d (a, b). , d (a, a) = 0.
:
1) d (a, b) ³ 0;
2) d (a, b) = 0 , a = b;
3) d (a, b) = d (b, a);
4) d (a, b) + d (b, c) ³ d (a, c).
.
. ij G (V):
.
c Î V
,
.
c 0 G,
.
, .
.6
, , . 6, r 0 = 1; c 0 = v 2 c 0 = v 4.
: G, (). ( s) .
, G (V) s:
d (s, u 0) £ d (s, u 1) £ £ d (s, un) V = { u 0, u 1, , un }.
. :
u 0 = s; d (s, u 0) = 0.
(l + 1) :
{ u 0 = s, u 1, , ul },
. , u 1 s, ( ) .
s: e (ui, v) d (s, ui) + d (ui, v) £ d (s, v), d (s, v) = d (s, ui) + d (ui, v) ( ) , 璺 s v, ui. ϳ , s . ( ui + 1).
.
, :
VID: VID(i) s i - ;
FIX: FIX(i) = 1, i - ;
PRED: PRED(i) s - .
1) .
: VID(s) = 0, FIX(s) = 0, PRED(s) = s.
: VID(v) = ¥, FIX(v) = 0, PRED(v) = v.
: u = s, i = 1.
2) G, FIX(v) = 0
e = (u, v) VID(u) + d (u, v) £ VID(v)
VID(v) = VID(u) + d (u, v), PRED(v) = u.
|
|
3) G, FIX(v) = 0, v 0,
.
4) FIX(v 0) = 1, u = v 0.
5) i = i + 1.
i £ n,
2).
6) ʳ.
VID s ; PRED s .
.
.7
. 5, . Գ , u .
5
i | VID | PRED | ||||||||||
A | B | C | D | E | F | A | B | C | D | E | F | |
0* | ∞ | ∞ | ∞ | ∞ | ∞ | A | B | C | D | E | F | |
∞ | ∞ | 6* | A | A | C | A | E | A | ||||
7* | ∞ | ∞ | A | A | C | A | E | A | ||||
∞ | 8* | ∞ | A | A | C | A | E | A | ||||
∞ | 16* | A | A | C | A | D | A | |||||
∞ | A | A | C | A | D | A |
A, , E , PRED, : E D A.
(, XVIII .). . .8.
. 8.
7 { a, b, c, d, e, f, g }, { A, B, C, D }. , , .
.9.
.9.
(): , . , , .
. G (V) , :
1) G (V) - ;
2) .
:
1) a Î V;
2) P a . , a ( );
3) P (a, a) G (V), G 1 = G ‑ P (a, a), . G (V) , P (a, a) b , G (V) ( G );
4) G 1 P , b b ; P P :
P 1(a, a) = P (a, b) È P (b, b) È P (b, a);
5) P 1(a, a) G (V), , 㳺 3) G 2 = G P 1(a, a) ..
, , G (V) .
( !) P 1, G (V).
|
|
. G (V) - k . , G, k / 2.
Pi.
1) 璺 ( k / 2 ). G 1, ;
2) G 1 S;
3) S 1) k / 2 , k / 2 , G.
. 10.
:
a | b | c | d | e | f | g | h | |
, k = 4. ǒ (c, d) (f, h) ( .10 ).
:
) P 1 = (, , );
) P 2 = (, , VI, IV, III, II);
) P 3 = (, IX, XIII, XII, XI, VI, IV, III, II);
) P 4 = (I, IX, XIV, X, VIII, XIII, XII, XI, VI, IV, III, II);
) P 5 = (I, IX, XIV, X, VIII, XIII, XII, XI, VI, VII, XV, V, IV, III, II).
³ XIV XV, :
1) (, );
2) (, VIII, XIII, XII, XI, VI, VII);
3) (V, IV, III, II).
, . , :
1) (V, IV, III, II, I, IX);
2) (X, VIII, XIII, XII, XI, VI, VII).
. G (V) - . G , v , :
r (v) = r *(v).
,
. , .
. , .
, , : , . ³ . , .
, . ; . , , . .
. (ij). G (V) n v Î V: r (v) ³ n / 2, .
, :
-
- ,
-
- ,
- ( )
- . , , . . . , .
|
|
1. ( ).
2. .
. G v , r (v) = 1, , v, .
3. .
G v 0. e = (a, b) , v 0 ( , v 0 ).
4. vV vE = 1 (vV - , vE - ).
5. ( ).
. G :
g(G) = vE ‑ vV + 1.
. G
g(G) ³ 0
, G , ( ).
g(G) = 0.
: 璺 n 볺 , . 볿 . , G, . , G - .
.
ei . A 1 = { e 1}. Ai ‑ 1 , , , , Ai = Ai ‑ 1 È { ei } . An ‑ 1 = G .
G =(V, E) , { V 1, V 2} V () , (v, w)Î E v Î V 1 i w Î V 2, v Î V 2 i w Î V 1.
G =(V, E) , - v Î V 1 i w Î V 2 (v, w)Î E. | V 1|= m i | V 2|= n, G Km , n.
( ). , .
. G (V 1, V 2) - . 璺 G:{(xi, yj), }, xi Î V 1 yj Î V 2, .
. 璺 () 璺 G, .
: 璺, V 1.
( ). 璺 V 1 , U 1 Í V 1 U 2 Í V 2, , 璺 U 1, U 1.
璺 .
, . 璺 0. V 1, x 0: x 0Î V 1 x 0Ï 0.
W 0 = { x 0};
W 1 = { y | (x 0, y) Î G };
|
|
W 2 = { x | (x, y) Î 0, y Î W 1, x Ï W 0};
W 3 = { y | (x, y) Î G, x Î W 2, y Ï W 1};
W 4 = { x | (x, y) Î 0, y Î W 3, x Ï W 0 È W 2};
W 5 = { y | (x, y) Î G, x Î W 4, y Ï W 1 È W 3};
...
, , , W 1 W 2, W 3 W 4, W 5 W 6 .. . , Wi W 2 k,
U 1 = W 0 È W 2È È W 2 k Í V 1
U 2 = W 1 È W 3È È W 2 k - 1 Í V 2
(U 2 , 璺 U 1) , . y *:
y * Î W 2 k - 1 y * Ï 0.
S, x 0, W 1 y * (2 k ‑ 1) :
S = { e 1, e 2, , e 2 k - 1},
e2 k Î 0.
璺 1 :
1 = 0 \ { e 2 È e 4 ÈÈ e 2 k - 2} È { e 1 È e 2 ÈÈ e 2 k - 1}.
璺 1 V 1 0. 1 V 1, x 0: x 0Î V 1 x 0Î 1 ..
0 = {(x 1, y 1), (x 3, y 2)}.
1) W 0 = (x 2); W 1 = (y 2); W 2 = (x 3); W 3 = (y 1); W 4 = (x 1); W 5 = (y 4).
e 1 = (x 2, y 2); e 2 = (x 3, y 2); e 3 = (x 3, y 1); e 4 = (x 1, y 1); e 5 = (x 1, y 4).
1 = {(x 2, y 2), (x 3, y 1), (x 1, y 4)}.
2) W 0 = (x 4); W 1 = (y 3, y 4).
e 1 = (x 4, y 3).
= 2 = {(x 1, y 4), (x 2, y 2), (x 3, y 1), (x 4, y 3)}.
5.
, (), . , , . , , , , , - , , .
.
, , , , ( ). .
, .
, , ., , , . , - .
, .
) )
.
K 5 i K 3,3, .
K 5 K 3,3
.
K 3,3 .
. K 5 i K 3,3 .
K 5 i K 3,3 , "" . "" K 5 K 3,3. .
G =(V, E) G (vi, vj)Î E vi i vj v, v (vi, vj) G, vi, vj.
, G G ¢, G ¢ G .
. . G i G ¢, G G ¢.
G G ¢
.
.
( ). G , , K 5 K 3,3.
G =(V, E) , Nk ={1,2, ...,k }.
|
|
- f:V Nk, v Î V f (v) Î Nk, G. f (v) v.
f G , - v w f (v) ¹ f (w).
̳ k, G, G c(G).
̳ G k =c(G).
. , 1- G =(V,Æ) . Kn n, - 2. 2- .
.
3.6. G k , c(G)£ k.
3.7. , .
, C 2 k . , c(C 2 k +1)=3.
3.12 (), .
3.8. , .
, k - k, , ( , ) . , c(G), G.
3.16. D(G) G, c(G) £ D(G)+1.
n G. (n =1) .
t (t ³ 2). G t +1 . G v, G ¢, D(G). , , G ¢ D(G)+1 . G G ¢, v , v . , D(G), G D(G)+1 .
3.16.1. .
, . .
, .
ó ( " ") :
, - .
, , .
.
I . . , . ʳ , , , , , 1976 . "" , .
, , 4. K 4. , "", " ".
1. : ϳ / .., .., ..; . ... .: , 2002. 287.
2. : ϳ / .., .., .., .., .. . .: , 2002. 568.
3. .., .., .. . .: ², 1995. 252.
4. .I., .., .. . - .: , 1993. -112 .