.


:




:

































 

 

 

 





, , , .

, G, (), . G = (X, U), |X| = n, |U| = m

g(G) = m n + k, (17.1)

k , (k = 1, 2, ). r (G) = n k . g(G) = m r (G).

, - G , . , , ,

g(G) = m n + 1. (17.2)

, G (. 17.38) g(G) = 9 6 + 1 = 4, . (x 1, x 3), (x 1, x 5), (x 4, x 5), (x 4, x 6). T, .

, . g(G) , . () , g(G) = 0. , () , g(G) = 1.

g(G) , . , .

Rc = || rc (i, j)||g(Gm, g(G) m , ,

G (. 17.38) Rc :

    u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9  

Rc =

c 1 1 0 1 0 1 0 0 0 0

.

c 2 1 1 0 1 0 1 0 0 0
c 3 0 0 0 1 1 0 0 1 1
c 4 0 0 0 0 0 0 1 1 1

u 1 = (x 1, x 2), u 2 = (x 1, x 3), u 3 = (x 1, x 5), u 4 = (x 2, x 4), u 5 = (x 2, x 5), u 6 = (x 3, x 4), u 7 = (x 4, x 5), u 8 = (x 4, x 6), u 9 = (x 5, x 6).

X l ():

(17.3)

, X i . X i , , X j , .. . l . , , c(G).

, Kn n , , c(Kn) = n. G = (X, U) (n - 1) £ m £ n(n 1)/2

(17.4)

, , ..

c(G) £ 1+max r (xi), xi Î X, i Î I = {1, 2, , n}. (17.5)

K i G,

c(G) = n / n i,

n i K i. :

, (17.6)

.

. c(G), q.

:

:

j = 1, 2, , n,

l = 1, 2, , m, (17.7)

p = 1, 2, , q.

n , . , .

q ( ) x(j, p), (17.3), , , (17.3) . q, (17.7) , .

G = (X, U). . 1 . , 1 , . , 2 . , .

, G, . 17.1.

. 17.1. G

xi x 3 x 2 x 4 x 5 x 7 x 1 x 6
r (xi) 5 4 3 3 3 2 2

x 3, x 4 1 .

xi x 2 x 5 x 7 x 1 x 6
r (xi) 4 3 3 2 2

x 2, x 6 2 :

xi x 5 x 7 x 1
r (xi) 3 3 2

x 5, x 7, x 1 3. , .

, . , , , , .. O(n) O(n2).

n- () . G(n1, n2) = (X1, X2, U). X1 È X2 = X, X1 Ç X2 = Æ, X1 X2 . . 17.2 G = (X1, X2, U), |X1| = 3 = n1, |X2| = 2 = n2, X1 = { x 1, x 2, x 3}, X2 = { x 4, x 5}.

. 17.2.

K(n1, n2) , xi Î X1 xj Î X2 (i = 1, 2, , n1; j = n1 + 1, n1 + 2, , n1 + n2).

, G(n1, n2) (. 3.2) (x 3, x 4) . , G = (X1, X2, U) X1 , X2 . m K(n1, n2) m = n1 × n2.

.

17.1. G , .

1. G = (X, U), . 17.3.

. 17.3. G

: . 17.3, , ½X½ = 8; ½U½ = 11, .. G 8 11 . (3.1), g(G) = 11 - 8 + 2 = 5. , G , . , .

, , . . , , . (x 1 x 2). , , (x 2 x 3); (x 3 x 4). , . . , , (x 5 x 6); (x 6 x 7). . , , . 17.4.

. 17.4. , G

2. , . 17.5.

. 17.5. G

: .

1. G :

.

2. x 4: P1 = { x 4}.

3. . . x 7: P1 = { x 4, x 7}.

4. . x 2 - x 4 x 7, P1. P1 = { x 4, x 7, x 2}.

5. , , P1, .

.

6. x 8: P2 = { x 8}.

7. x 1: P2 = { x 8, x 1}.

8. x 3: P2 = { x 8, x 1, x 3}.

9. x 6: P2 = { x 8, x 1, x 3, x 6}.

10. , P2. .

11. x 5. .

, , , : c(G) = 3.

3. G = (X1, X2, U), , ½X1½ = 3; ½X2½ = 4.

: . 17.6.

. 17.6.

1. ? ?

2. ?

3. ?

4. ?

5. ?

6. ?

7. ? ?

8. ? ?

9. ?

10. .





:


: 2018-10-18; !; : 2089 |


:

:

, .
==> ...

866 - | 779 -


© 2015-2024 lektsii.org - -

: 0.031 .