, , , .
, 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(G)×m, 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. .