( , , , ..) . , , .. , , , .
, , , . .
. , : , . X = { x 1, x 2, , x n}, |X| = n . , , (xi, xj) Î X U = { u 1, u 2, , u m}, |U| = m.
, 1 n, . 1, 2, , n G 1, 2, , i, , n x 1, x 2, , xi, , x n, x (1), x (2), , x (i), , x (n). . , . . .
, G = (X,U) , .
, U, U = È È , ─ , . . ui Î xk, yl, . ui = (xk, yl) ui = (yl, xk).
─ , . . ui Î ( ) xk, yl, ui . ui = < xk, yl >. , ui = < xk, yl > uj = < yl, xk > ─ G.
─ , . . ui Î , ui = < xk, xk >, ui = (xk, xk).
|
|
G = (X, U), , , ¹ Æ, . . 15.1 G. |X| = 6, |U| = 13; U = È È ; = { u 3, u 4, u 7, u 9, u 10, u 11}; = { u 1, u 2, u 8, u 12, u 13}; = { u 5, u 6}.
. 15.1. G
G = (X, U), U = , = Æ, , . D = (X, U) G = {X, }.
, , . , . G, U = , , . , , .
, . G, , m ui Î U, , m ─ G (m Î {2, 3, }). , , . . 15.2 (m = 4).
. 15.2. G
uk Î U G = (X, U) xi, xj Î X, .. uk = (xi, xj), , uk xi, xj. , xi, xj uk. xi, xj Î X G , uk Î U, .. uk = (xi, xj). uk, ui Î U , .
G = (X, U) , . , . , , .
. . , G Ì B = X × X. . . G = (X, ), Í X ´ X, = { x 1, x 2, , xn }. ─ . , G = (X, ) (. 15.3). |X| = 6, X = { x 1, x 2, , x 6}, = { x 1, x 2, , x 6}, x 1 = { x 2, x 5, x 6}, x 2 = { x 1, x 3, x 5, x 6}, x 3 = { x 2, x 4}, x 4 = { x 5, x 6}, x 5 = { x 1, x 2, x 4}, x 6 = { x 1, x 2, x 4}.
, G = (X, ), X X .
, x 1, x 2, , xn -1 . xi, xi, xi +1; xi +2 xi, xi +1 .. xn -1 x 1, x 2, , xn -2. G (. 15.3), : x 1 = { x 2, x 5, x 6}, x2 = { x 3, x 5, x 6}, x 3 = { x 4}, x 4 = { x 5, x 6}, x 5 = Æ.
. 15.3. G
.
|
|
. R = || ri , j ||nxn , :
,
, ri , j = rj , i R. ri , i = 0, ri , i ¹ 0. G (. . 15.3)
x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | ||
x 1 | 0 | 1 | 0 | 0 | 1 | 1 | . |
x 2 | 0 | 1 | 0 | 1 | 1 | ||
R = x 3 | 0 | 1 | 0 | 0 | |||
x 4 | 0 | 1 | 1 | ||||
x 5 | 0 | 0 | |||||
x 6 | 0 |
R G. xi xj ri , j, , xi xj. , R , . ri , j, R.
.
, |X|2 , |X| . . xi , xi. |X| + |U|. , |U| << |X|2. G (. . 15.3) :
x 1 | x 2 | x 5 | x 6 | 0 | |
x 2 | x 1 | x 3 | x 5 | x 6 | , |
RL = x 3 | x 2 | x 4 | 0 | 0 | |
x 4 | x 3 | x 5 | x 6 | 0 | |
x 5 | x 1 | x 2 | x 4 | 0 | |
x 6 | x 1 | x 2 | x 4 | 0 |
x 1 | x 2 | x 5 | x 6 | 1 | 2 | 5 | 6 | |
x 2 | x 3 | x 5 | x 6 | 2 | 3 | 5 | 6 | . |
RL= x 3 | x 4 | 0 | 0 | RL=3 | 4 | 0 | 0 | |
x 4 | x 5 | x 6 | 0 | 4 | 5 | 6 | 0 | |
x 5 | 0 | 0 | 0 | 5 | 0 | 0 | 0 | |
x 6 | 0 | 0 | 0 | 6 | 0 | 0 | 0 |
, , . ( ).
I = || ik , l ||n´m , :
G (. . 1.3)
u 1 | u 2 | u 3 | u 4 | u 5 | u 6 | u 7 | u 8 | u9 | ||
x 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | . |
x 2 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | |
I = x 3 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | |
x 4 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
x 5 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | |
x 6 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
I , , ik , l xk ul. I , . I , .
. . , . , , .
, () m × n 2mn. n n2 . k ( )
|
|
.
, :
() n;
(.. ).
:
, ;
, .
, . , , (. 15.4)
. 15.4. G
:
,
G.
. .
ʸ . - , .
. G (. 15.4)
.
, (). , i, j = j, i ( , i, j ¹ j, i).
() GS = (U, V), ( U(G)) G = (X, U). GS G, GS (ui, uj). GS G ui Î U G ui Î U GS (. . 1.5). , GS 12 : U = { u 1, u 2, , u 12}
(ui, uj) vk = (ui, uj), ui, uj G. GS u 1, , u 2, u 4, u 5, u 6, G (x 1 x 2). GS (. 15.6)
. 15.5. GS
. 15.6. GS
, , R I, .
G , ─ . , , , .
G, X ¹ Æ, U = Æ, -, ─ . G0. G = (X, U), |X| = n , xi, xj Î X uk Î U. Kn. , xi Î X G, r (xi) r i. G = (X, U), |X| = n, |U| = m,
. (15.1)
, , . n r (x 1) = r (x 2) = = r (xn),
m = n (n - 1) / 2. (15.2)
. 3 (). (. 15.7).
15.7.
, :
|
|
(. 15.8, ),
(. 15.8, ),
(. 15.9, ),
(. 15.9, ),
( 15.9, ).
ࠠ
. 15.8. (), ()
. 15.9. (), (),
. 15.9. () ()
r (xi) xi
m = n r (xi)/2. (15.3)
, , , .
K1, n . 15.10.
. 15.10.
: (È), (+) (*).
1. G(a) = (X(a), U(a)) G(b) = (X(b), U(b)) G = (X, U), X = (X(a) È X(b)), U = (U(a) È U(b)) (. 15.11).
. 15.11.
2. G(a) = (X(a), U(a)) G(b) = (X(b), U(b)) G = (X, U) G(a) G(b), xi Î X(a), X(a) Ç X(b), X(b) \ X(a) Ç X(b) (. 15.12).
. 15.12.
3. G(a) = (X(a), U(a)) G(b) = (X(b), U(b)) G = (X, U) X = X(a) × X(b), (. 1.13).
. 15.13.
G , G, .. G = (X, U), G = (X, U), X Í X, U Í U U X. G = (X, U) xi G = (X, U), X = X \ xi. . 15.14, , b, c G = (X, U) , G1 = (X1, U1) G2 = (X2, U2), |X| = 7, |U| = 10, X = { x 1, x 2, , x 7}, U = { u 1, u 2, , u 10}; |X1| = 3, |U1| = 3, X1 = { x 1, x 2, x 4}, U1 = { u 1, u 7, u 6}; |X2| = 5, |U2| = 6, X2 = { x 2, x 3, x 5, x 6, x 7}, U2 = { u 2, u 3, u 4, u 8, u 9, u 10}. , G1 , G x 3, x 5, x 6, x 7 , G2, G x 1, x 4 .
a
G1 G2
ᠠ
㠠
.15.14. G () G 1() G 2(); G (); G ()
G = (X, U) G = (X, U) , X = X, U Í U.
G , K, G, = K \ G. . 15.14, ) (. . 15.14, ). . 15.14, ) G (. . 15.14, ) K7.