.


:




:

































 

 

 

 





( , , , ..) . , , .. , , , .

, , , . .

. , : , . 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.





:


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


:

:

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

759 - | 770 -


© 2015-2024 lektsii.org - -

: 0.088 .