Martynyuk_A_N_Diskretnaya_matematika

13.4. # .G

^ +. ; + ) / / n1 ,n2 ,K, nk 2 + 3

/ , 1 = n1 + n2 +K+ nk .d / ni ( = 1, 2, ..., k) 3 , 0 3

— 3 +. ( / / +

— +, / ? / / ,

/ .

4 &. 0 4 5 % % % '. (4, 31, 22, 211, 1111) %

( & (4,31, 13, 22, 211, 121, 112, 1111). o 8 % '

'' %: 611, 521, 431, 422, 332.

D A + 8 8 8 9 5 ( ) 8 4 p(x) = p(0) + p(1) + p(2) x2 + K, k : 5

9 (1+ xk + x2k + x3k +K ) , 9

2

(() = (1+(+ x2 K)(1+ x2 + x4 +L)L(1+ xk + x2k +L)L= l(1# xi )#1

i=1

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

5 . D A 8 C + 5 k,

k

pk (x) = l(1# xi )#1.

i=1

2 8, 6 , : (()=(1+()(1+x2)(1+(3)... , 8

+ 5 :+

2

v(x) = l(1# x2i#1 )#1.

i=1

4 &. o % 8 " & 1, 2, 3 5

". 0 ' & p(()=(1+(+(2+...)* *(1+(2+(4+...)(1+(3+(6+...)(1+(5+x10+...).

_P x8 &$ 13, 8 & ` %: 53, 521, 513, )212, 322, 3221, 3213, 315, 24, 2312, 2214, 216,18 ( q , 8 ( & ' % q ). S 8 &, 8 %

% , (()=(1+x)(l+(2)(1+(3)(1+(5), & ( & (8) = 2 (& & % 53 521).

v 8 8': k 9 4 +

( , k) = ( - k, k) + ( - k, k - 1) + ...+ ( - k, 1)

4 6 6 (n, k) = 0, n < k p(k, k) = (n, 1) = 1.

4 &. S 8 n = 7 k = 3, p(7,3) = p(4,3) + (4,2) + (4,1); (4,2) = (2,2) + p (2,1) = 1 + 1 = 2; (4,3) = p(1,3) + (1,2)+ +p(1,1) = 1; (7,3) = 1 +2+ 1 = 4. +,

% 7 - 511, 421, 331, 322.

+H . % ,

1.Y $' '$ $ P$?

2.Y % '` ' – % E'$ ?

3.Y ' P?

4.Y ` $ $ ?

5.S P $ $ ?

6.S &, ( P,

& `, P $ %?

7.Y ' & & > & $ $ ? S 8 P $ $ $ ?

8.Y %$?

9.S ’ % & `?

71

% +

+

1.E -.9. 0 & . – N4%.: 4, 2001. - N.148-157.

2.N " >.4. A " . – _.: .(, 1975. -

N.174-182.

3.Π1.E. 0 . 9 b b: 3 %

%. – A.: % 1 b( ) ", 2001. - N.39-49, 53-66. 0 &

4.E >.d., N 9.>. 4 & & -

(. 0 & ( (. – _.: 3 %-

& " % b ` %, 1992. - N.47-55.

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

20.

6.1 P d., 1 .. N & %. – A.: A, 1976. - N.25-

29.

0 ( '

7.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.23-24.

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

A.: E, 1973. - N.249-281.

72

# : III. A# D

? 14. " : ! ? # " ? A# D "

" %

% P.

, P, P,

' & P, % & ( ( P. )

& P ( P. 3 & & & :

14.1.+

14.2.N % & P

14.1. .-,

q : + + 8 + 5 6 , A 6 8 + 5.

>. A ` „, 8 ' %$ $ % V,

' P ' G = <X,V>.

4 &. d P ( . 14.1) G = <{x1, x2, x3, x4}, {v1, v2, v3, v4, v5}>

. 14.1. d P

- : – 5 9 8 4, '

9 8 5C 5 .

>. d P G – & " & G = < X, d >, & „ – ` P,

d– & & ', 8 &% ` „ %.

4 C C , A 4 +

5 4 9 4 8 9 6 4.

4 &. d P ( . 14.2) ' % & ( )

& ' & G=<{x1, x2}, {(x1, x2), (x2, x1)}>, P

% & % – ( ).

2 4 : 5 , 4 +

4 8 9 6 4 8 9 6 8.

: 8 4 : 5 &$. q : 8

: 5 P. D A C ': 8 5C + 5 + 4,

4 + 5 %.

. 14.2. d P % &

% %

73

2 8 9 4, C, + 5

%, 8 9 4, 9 C, + 5

%, 4 (8), A 6 5 6 5 C, : 5

$, 4 8 9 4 + 5 %.

. 14.3. N % % &, %, % ( &,

q, A 5 5 8, : 5 , 4, A 5

4, 8, : 5 `.

. 14.4. E " P, P ` " P

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

` G(6 ), 6 : 5 .

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

C 6 , : 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)|).

2 : 4 4 8 9 8 + 5 ,

: 4 4 4 8 9 8 + 5 . q 8 5

6 8 : 5 ". q 8 5, 8

: 5 ' P, 4, A 5 8 , : 5 & P.

0. 14.5. * 5 4 4

q, A : 8, C 4 5, : 5 '-

P. . 4, 8 5- C ': 8, : 5 .

74

0. 14.6. . 4

D A C ` 4 4 + 5 8 6

9 `1 `2 (`1 `2 = `1 `2 =`), A + 5 8, ': + 5 C

9, : 5 & % P.

4 &. 1 P ( . 14.7), X = {x1, x2, x3, x4, x5, x6}, X1 = {x1, x2, x3}, X2 = {x4, x5, x6}

0. 14.7. 2 4 (8 4)

q, C 4 “r”, : 5 & &,

r- .

0. 14.8. 4

2 C xi xj X 4 G = <X, V> + 5 , A ': 8 vk V. 2 : 4 4 9 C : <xi, xj> <xj, xi>, 4

<xi, xj>, xi - 4, xj - 5 4. 1 C xi 8 (4) vk &, A 8 (4) 6 5 (6 5) C xi.

75

14.2. % G % * + , F /

. C 8, , - 4 G 4 & " G=<X, q>. < 4 + 5 4 8 9 5 4 4.

3 5C 8 6 4 4 "

G=<X, V, 6>, 6 - C, A : 5 + 4 + 6 X× V× X, , A

K<xi, vj, xk> 6 :, A 4 vj V, ': : C xi xk. ? + G=<X, V, 6> 9

5 4, 4.

= C 8 - 4 G 4 + . (

4 G + 5 C 4, ( )

uij, A : + xi xj , +: 6 8, A '+ 5

C xi C + xj , 4, 4, 6 C xi C

xj.

4 &. + " P, & " $ P

. % 14.1

.14.9. + " & P G =<X, V>, X = {x1, x2, x3, x4, x5}, V = {v1, v2, v3, v4, v5, v6, v7, v8, v9, v10}

, A 8 5-4 4 4 9 :

n n

* 9 4 4 5 .

4 &. E " P, & " $ P

. % 14.2

76

D A C : 8, 4 5, A C 8, 8

C, . 2 4 + 5

& ', 4 6 5 C, & ', 4 6 5 C.

q G 9 $ &, + 5 8 (4) 4, - C 4. 2 : 4 4 i-4

, A : C xi, j-4 , A : 8 vj, 5 ,

xi, 5 ”-1”, A 4 vj 6 5 C xi. 9 5 5

. . + 5 9 5, : 4 8

C, ' . B 8 4 : 5 6 .

4 &. E " P " &

? 8 14.3

. 14.11. E " & P G =<X, V>, X = {x1, x2, x3, x4, x5}, V = {v1, v2, v3, v4, v5, v6}

77

2 8 5-4 : 4 4 8 5 4

:

m

Kj=1xi (G(xi) = k uij), m = nVn.

4 &. + P, & " P $ &

. % 14.4

. 14.12. + " & P G =<X, V>, X = {x1, x2, x3, x4, x5}, V = {v1, v2, v3, v4, v5, v6, v7, v8, v9, v10}

2 8 5-4 : 4 4 8 5 4

:

uji(-1) {+1;0}, uji(-1) {-1;0}.

q, 6 8 4 + 5 C , + 5 P. * : 4 8 5 + .

0. 14.13. = 4

. 9 9 4 4 - 5 : 4 4 i-4 , A

: C xi, j-4 , A : 8- vj, 5 ,

4

i-4 j-4 86, , +1, -1.

2 & P 8 9, A + 5 .

78

+H . % ,

1.S &$ & " ' P,

, 8 & ' % & P?

2.Y P?

3.Y %, &$, $, % %,

% &?

4.Y , ( & ( &?

5.Y P, ' P & P?

6.S P?

7.Y % P % & P, 8 P r-

?

8.Y & $' ' & ', 8 $

$ &$?

9.S P &$ ", &

?

10.S P P?

% +

+

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

P. – A.: E, 1990. - N.9-19.

2.E -.9. 0 & . – N4%.: 4, 2001. - N.189-194.

3._ ., 1 " d. _'$ . – A.: E, 1990, .217-224.

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

94.

0 &

5._` a.A. A b %. – A.: c &, 1987. - N.67-72.

0 ( '

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

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

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

79

? 15. " : ! ? A# D ". :" @ A# D

" %

& & P.

`, $ , " ( ' ( %( &, ’ ,

`, , &, , &,

( P. ) & & '. 3 & & & :

15.1.+ (&)

15.2.) (&) P

15.1. .-, (% * ; ,)

>. A ` (` () & m ' & ' % P,

%' (, (, 8 ` & ( & ( % %$'.

< C 5 : 9 C, : 5. * C

: 5 * = <v1, v2,…,vj,…,vn>...

4 &. E " P ( . 21.1.) ` M1x1 o x4 = <v1, v2, v3, v2, v4, v5>, M2 x1 o x4= <v6>

0. 15.1. -: 4

>. 0$ ` (` () A = <v1, v2,…,vj,…,vn> '

&, 8 " &$'.

2 9 C : 5 l(M).

4 &. 0 . 15.1. ` Mx1 o x1 = <v1, v2, v5, v6>; M1x3 o x3 = <

v4>; M2 x3 o x3= < v3, v2>.

>. A `, % , ' $ , `, &

`, 8 ( & ', ' $ .

4 &. 0 . 15.1. Mx1 o x1 = <v1, v2, v5, v6> Mx1 o x4 = <v1, v2, v4, v5> -

$ , Mx1 o x4 = <v1, v2, v5> - " $ .

< +4 : 5 , +4 : 5

.

4 &. Mx1 o x1 = <v1, v2, v4, v5, v6> Mx3 o x3 = <v3, v2, v4> - , Mx1 o x1 = <v1, v2, v5, v6> Mx1 o x1 = <v3, v2 > - .

>. U P, 8 ' " %, ' " . >. 4 " P, 8 ( & ' " `, '

' .

T 4 5 (86) 9 8 5-4 4 4. 1 4 C, +4, , 4 5

6 : 5 4.

>. o P, 8 ' & &$ &$ %

& `, ' & P.

4 &. d P G = <X, V>, & X = {x1, x2, x3, x4}, V = {v1, v2, v3, v4, v5} & P G' = <X’, V'>, & X’ = { x2, x3, x4}, V' = { v2, v3, v4}, G' G, „' X, V' V.

80