Martynyuk_A_N_Diskretnaya_matematika

0. 15.2. q ( ) 4 ( )

>. >( & $ `$ P G = <X, V> ` x(s) X,

" p(x(s)) = 0, ( & $ `$ P G = <X, V> ` x(F) X, "

s(x(F)) = 0.

4 &. 4 ` x1 ` x3, x5

0. 15.3. . C (61 – 6, 63, 65 - 6) 1 4 9 8 5 6 6 (65 - 4 6).

(4 5 6 6 4 9 4 5 (

-8 5 :) C, , A 6 6 + 5,

8 mxi(p(xi) = 0) mxi(s(xi)= = 0), 5 C x(S) X x(F) X, A ': : 5 : + 4 + C + 4 + C.

4 &. 3 & P ( `

0. 15.4. ( (6 xs) (6 xf) C

‹ 6 6 4 4 6, 8 C x(S) 4 C

x(F): 5 x(S) - x(F) - C 6. 1 9 : 5, A 6 8 C 6 4 :. D A 4 C xi xj ' C 6 M[xi, xj], C xj &

C xi A C xi & C xj.

2 C 4 + 5 ' , A : C, A 6 ': :, C

- ' .

>. + P ' ’ , 8 & % &'- "

` xi, xj X " ` ( xi xj , xj xi.

>. d P ' ' , 8 & % &'- " ` xi , xj

X ` ( xi xj ` ( xj xi.

>. + P ' % ’ , 8 & % &'- "

` xi, xj X ` xk, 8 xk & xi, xj, xk & xj,

xi.

>. d P, 8 ’ , ' , % ’

' ' P.

4 &. )'" P ’" P

81

. 15.5. )'" P ( ) '" P ( )

D A : C, +: ' 4 ' ,

: 5 $ , 8 9 : 5 .

>. d P ' & ', 8 '"

, P, 8 ( % & & ' '

% '.

4 &. d P &$ $ P &

. 15.6. .

<' 4 + 5 &. 2 5 5 5 5

8, A 8 : '5 4. - ' 4, 4 : ,

: 5 .

4 &. 0

. 15.7. 0

-6 |X| |V| - 5 C 8. 2 : |X| = |V| + 1; |V| = |X| - 1

>. d P ' ( ), 8 P " "

P, 8 % % " 8 % %.

-6 &$ d(x1, x2) 9 C x1, x2 (4) : 5 9

5 4 C 6 x1 x2. 1 5 C 6 8 5C C

: 5 (() C 6, 8

(6) = max(d(x, y)) = max( d(x, y))

y y X

-C : 5 & r(T)

r(T) = min(e(x)) = min( e(x))

x x X

U '$ `$ ? : 5 C,

+: . U & : 5 9 4 5 6 C. 9

: , A : 5 : C 6 9 6 C.

4 &. r(T) = 3, e(x) = 6 P

82

. 15.8. & & ` &

15.2. : ; (*.- ) F /

D A 8 (4) 4 4 ( ), 4 + 5

(&).

1 4 4 8 9 9, 5, 4

. . 1 4 9 5 8 (4), C. < 9 4

6 5 , 9 . < 9 : 4

+ 5 P - . < 9 4 6 5 , ,

+4. < 9 4, A 5 6 8, 9 8

+ 9. . 5 9 5 +: 4

8 (4).

4 &. A P & P

. % 15.1

	x1	x2	x3
x1			7
x2	5
x3		8

. 15.9. ) " P

+H . % ,

1.Y `, &$ `?

2.Y $ , $ , , ?

3.S " ' ?

4.Y & P, $ $ `?

5.Y ’ , ' , % ’ P?

6.Y & ' P, $ , ?

7.Y &, & ` ' ` % &?

8.S , & ?

9.S P P?

83

% +

+

1.W >.9., A ' +.Œ., N >.Œ., .b` .Œ.

P. – A.: E, 1990. - N.22-26, 133-148, 191-207.

2._ ., 1 " d. _'$ . – A.: E, 1990. - N.224-257.

3.E -.9. 0 & . – N4%.: 4, 2001. - N.195-197.

0 &

4.d % >.9. + b & " . – A.: >b `.`., 1986. - N.94-

102.

0 ( '

5.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. –N. 43-44.

6.d d.4., N 9.9. N% & & " . –

A.: E, 1973. - N.111-137.

84

? 16. #-@ # ) A# D

" %

-( " & P.

%’&, , &, , & & %

P, & ' ' ( " % ( ". )

& & P " & , &

P & " ( (. 3 & & & :

16.1.+ & P

16.2.> " & P

16.1. % C * F /$

-6 4 G =<X, q>, H = <Y, P>.

>. +%'& Q = G H ' P Q = <A, S> ", 8

A = X Y, S = d .

4 & : d P G, & X = {x1, x2, x3}, d = {<x1, x2>, <x1, x3>, <x2, x2>, <x3, x2>}; P H, & Y ={x1, x2}, P = {<x1, x1>, <x2, x1>, <x2, x2>}. 3 ' P Q, & A = {x1, x2, x3}, S =

{<x1, x1>, <x1, x2>, <x1, x3>, <x2, x1>, <x2, x2>, <x3, x2>}. G H – & P P Q, G Q H Q

. 16.1. +%'& P

1 8':

Kxi X Y(S(xi) =A(xi) P(xi))

Kxi X Y(S-1(xi) =A-1(xi) P-1(xi))

>. 4 Q = G H ' P Q = <A, S> ", 8

A = X Y, . S = d .

4 &. A = {x1, x2}, S = {<x2, x2>}, Q – & P P G E & '

&, Q G Q H

. 16.2. 4 P

85

1

Kxi X Y(S(xi) =A(xi) P(xi))

Kxi X Y(S-1(xi) =A-1(xi) P-1(xi))

q G = <X, q> : 5 ( ), A q = X2.

>. 0 P G = <X, d> & ' P

G = <X, d>, & d = X2 \ d.

4 &. G = <X, d>, X = {x1, x2, x3}, d ={<x1, x2>, <x1, x3>, <x2, x2>, <x2, x3>, <x3, x1>}, X2 ={<x1, x1>, <x1, x2>, <x1, x3>, <x2, x1>, <x2, x2>, <x2, x3>, <x3, x1>, <x3, x2>, <x3, x3>},

G = <X, d >, d = X2 \ d = {<x1, x1>, <x2, x1>, <x3, x2>, <x3, x3>}.

. 16.3. 0 P G = <X, d >

1

Kxi X( q(xi) = X \ q(xi))

Kxi X( q-1(xi) = X \ q-1(xi))

>. $ P Q = G \ H ' P Q= = <A, S> ", 8

A = X Y, S = d \ P = d P, % Q = G \ H = G H

4 &. 0 & ( ( & ( P G = <X, d>, H = <Y, P> & P Q = G \ H

	`		&	$'
A = X Y = { x1, x2}, P = {<x1, x2>}, S = {<x1, x2>}.

. 16.4. P Q = G \ H = G H

1 :

Kxi X Y(S(xi) = A(xi) \ P(xi))

Kxi X Y(S-1(xi) = A-1(xi) \ P-1(xi))

-6 4 G = <X, q>, H = <Y, P>.

86

	16.2. "+ G . ( % C E * F /$
1.	G H = H G;	G H			=	H G;
$H
2.	G (H F) = (G H) F;	G (H F)		=	(G H) F;
C H
3.	G (H F) = (G H) (G F);	G (H F)	=		(G H) (G F);
* G H
4.	G G = G;	G G		=		G ;
G GU = GU;	G GU		=			G;
+ $;
5.	G G = G;	G G			=	G;
*$% H
6.	G G = GU;	G G		=		G ;
* % ,
7.	G (G H) = G;	G (G H)			=	G;
% F+ ,
8.	(G H) (G H) = G H ;	(G H) (G H)			=	G HU;
+ ' ,
9.	G ( G F) = G (GU F);	G ( G F)		=	G (G F);
B+ E-CH F
10.	(G H) = G H	(G H)		=		G H
*-F
>. 0 & % Q		= G× H P		Q	= <X,	d>

E = <Y, P> ' " P Q = <A, S>, & A =X× Y & % &' <x, y> A

' S(<x, y>) =d(x)× P(y)).

4 & : 0 P G =<X, d>, H = <Y, P>, ( X = {x1, x2}, d ={<x1, x1>, <x2, x1>, <x2, x2>} Y = {y1, y2}, P = {<y1, y1>, <y1, y2>, <y2, y1>},

d(x1)= = {x1}, d(x2) = {x1, x2}, P(y1) = {y2, y1}, P(y2) = {y1}, ` P Q = = <A, S> ( & :

A = X× Y = {a1, a2, a3, a4} = {<x1, y1>, <x1, y2>, <x2, y1>, <x2, y2>}, S(<x1, y1>) = d(x1)× P(y1) = {<x1, y1>, <x1, y2>}, S(<x1, y2>) = d(x1)× P(y2) = {<x1, y1>}, S(<x2, y1>) = F(x2)× P(y1) = ={<x1, y1>, <x1, y2>, <x2, y1>, <x2, y2>}, S(<x2, y2>) = =d(x2)× P(y2) = {<x1, y1>, <x2, y1>}

. 16.5. 0 & % P Q = G× H

>. _ $ Q = G ° H P G = <„, d> H =<Y, P> '

P Q = <A, S>, & A = X× Y	& <x, y> A ' S(<x, y>)) ={d(x)× Y} {X× P(y)}).
4 &. 0 P	G = <X, d>,	H = <Y, P>, ( X = {x1, x2},
d = {<x1, x1>, <x2, x1>, <x2, x2>} Y = {y1, y2},		P = {<y1, y1>, <y1, y2>, <y2, y1>},

87

d(x1)={x1}, d(x2)={x1, x2}, P(y1)={y2, y1}, P(y2)={y1},

` P Q = <A, S> ( &

A = X× Y = {a1, a2, a3, a4} = {<x1, y1>, <x1, y2>, <x2, y1>, <x2, y2>}, S(<x1, y1>) = {{x1}× {y1, y2}} {{x1, x2}× {y1, y2}} = {a1, a2, a3, a4}, S(<x1, y2>) = {{x1}× {y1, y2}} {{x1, x2}× {y1}} = {a1, a2, a3}, S(<x2, y1>) = {{x1, x2}× {y1, y2}}({{x1, x2}× {y1, y2}} = {a1, a2, a3, a4}, S(<x2, y2>) = {{x1, x2}× {y1, y2}} {{x1, x2}× {y1}} = {a1, a2, a3, a4}.

. 16.6. _ P Q = G ° H

+H . % ,

1.Y %'& P, "

%’&?

2.S %'&?

3.Y P, "

?

4.S ?

5.Y & P, "

&?

6.S &?

7.Y $ P, "$ $

$?

8.S ?

9.S & ' " $' % & P?

10.S " " &

& P?

11.Y & & % P?

12.Y $ P?

% +

+

1.A ( 9.E. + b Pb b b. – A.: E, 1971. – N.40-59, 64-70.

2.E -.9. 0 & . – N4%.: 4, 2001. - N.199-201.

3.W >.9., A ' +.Œ., N >.Œ., .b` .Œ.

P. – A.: E, 1990. - N.19-22. 0 &

4.1 P d., 1 .. N & %. – A.: A, 1976. - N.68-

72.

5.d % >.9. + b & " . – A.: >b `.`., 1986. - N.89-

94.

88

0 ( '

6.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.45-47.

7.d d.4., N 9.9. N% & & " . –

A.: E, 1973. - N.101-111.

? 17. # # A# D ". # " ? "

" %

' ( P %

& P ’ W+A. `,

( , ` ' ` '

". ) & P ( % & P ’ W+A. 3 & & & :

17.1.o ' ( P

17.2.4 & P ' W+A

17.1. ! +H ( F /

0’ 8 4 5 6 4 5 6

C 6 ' ( ( 4.

17.1.1. % H K

2 : 4 4 8, A ' C + 6 , : 5

` G(6 ), 6 : 5 .

2 : 4 4 G = <X, q> 4, A 6 5 C : 5

( & (6 )

K xi (p(xi) 4 |q-1 (xi)|);

4, A 6 5 C xi - ( & s(xi)

K xi (s(xi) 4|q (xi)|).

4 &. 0 P ' ` (1, (2, (3, (4 &$ & & 1, 4, 3, 4 (& ' &).

. 17.1. E " P " ` s(x1)=1, s(x2)=4, s(x3)=3, s(x4)=4

89

17.1.2. +$ - -+

-6 G = <X, V>- : 4, |X| = n, |V| = m r –

’ (8 '6 4 4 G).

>. U P ' p, 8 &$ p(G) = m –n + r

B : - +: 8 5C

9 6 4. . 6 6 +4

9 9 6 .

4 &. 0 & . 23.2. & ( P V(G) = 5-4+2 = 3

. 17.2. 0 " P '$ , 8 &$ '

17.1.3. $ - -+

-6 – 5 .

>. d P ' -(, 8 " `

P % “ ” ' , 8 % & ` %

P % &.

>. E " ` , P -(, '

( P ' q(G).

D A q(G) = 2, 4 : 5 % (. -86 + 5 +

+ 8 6 4 : 5 5 9. 1 6 4 4, 8 6 4 4, : + +.

4 &. 0 P % P ( . 17.3) %( & ', &

P % – & ', % " P – % ( ".

. 17.3. E % ( " % ( " P

17.1.4. ; K H E

>. A S X P G =<X, d> ' ` ' "$, 8

& ` S , % & % &'- xi S d(xi) S = :

K xi S (d(xi) S = )

* 9 C 5 , A 5 8 5C , : "% '`$ ` ' "$ $, : 9 : 5

` ' " P.

4 &. 0 P ` ' "

. 17.4. d P ` ' " & ( ) ( )

90