.


:




:

































 

 

 

 


³, ,




 

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 = GP (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) = vEvV + 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, wE 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, wE. | 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, vjE 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(Gk.

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 .





:


: 2016-11-24; !; : 762 |


:

:

, - , ; , - .
==> ...

744 - | 765 -


© 2015-2024 lektsii.org - -

: 0.169 .