, , . , , xÎN, N :
, xÎN (!).
:
,
:
.
, n :
, .
, , n- k , . , . . 11 .
. 11.
, , Matematica (3,4) Wolfram Research,Inc. (DiscreteMath) (Combinatorica, CombinatorialFunctions): .
Ì2 [9]
G=<M,T>,
, , , .
, .. . : , , , ..
. 12.
={1,2,3,4,5},
={(1,3),(1,4),(2,4),(2,5),(3,1),(3,5),(4,2),(4,1),(5,3),(5,2}).
- (i,j), i,j , .
, . , , . , - [24].
(. ) (. ).
30- . [19] .
|
|
50- , . . , . .
. , (). . .
. , . . , , , . , . , , (). () , () . , ().
, ={,b,c,d,e}, , b (), , d , [9-10].
(. 13).
. 13. ,
. 13 , , . 11.
, i- (j- ) , . , , . , , . bij ×=2. bij, , Ì2, , , , .
, . 13. i,j , i j.
, . 13:
={,b,,d,},
={(,b),(,),(,d),(b,),(b,),(b,d),(,),(,b),(,d),(,),(d,),(d,b),(d,),(,)}.
-, , :
[<a,{b,c,d}>,<b,{c,d,}>,<c,{a,b,d,e}>,<d,{b,c,e}>,<e,{c}>].
n×m: A=||aij||, n=|M|, m=||,
ai tj; ai tj; ai tj, , . |
, (. 14) :
. 14.
|
|
, : . .
, , , . 15, :
.
. 15.
, () ( , , ..).
[9]. , , mÎ (m,m)Î. (. 16). , .
, (mi,mj)Î (mi,mj)Î, mi¹mj (. 16). .
, (mi,mj)Î, (mi,mk)Î (mi,mk)Î mi, mj,mkÎ, mi¹mj, mi¹mk, mj¹mk (. 16).
, , , , , .
. 16.
) , ) ,
)
G G=<,> , G, , (), .
, [18].
GD G , () G.
, [18].
, , , ( , ). , , .
, [26].
, , .
, .
(, ) , .
.
.
, .
, deg(), , . deg=1, , deg=0, .
G n m , degj j- , :
.
, , , .. 2 . , . .
. .
, . , , .
, (), (. 17).
. 17. -
|
|
, .
, . , , . , n n-1 .
, , m , mm-2. .
.
G , n m .
G n m
n(G)=m-n+1.
: [18]. .
.
, , (. 18).
, , (. 18).
, , (. 18).
, , (. 18).
, , (. 18).
, , (. 18).
, , (. 18).
, , (. 18).
, , (. 18).
.
. 18.
() .
(), , ( ).
, .. ..
.
G -, , , . , -, l(G). l(G)=2, . .
. 19 , , 0,1.
. 19.
. 19 , , (), () ().
.
, . , , , - .. [24]. , , . . , , ; , , .
, , . 20, [24].
. 20. ) ),
51, 15
, .
, , .
, , . n! , n .
|
|
: , , , .
- , . , , , [24].
, . 21 , , , , [24].
. 21. ) )
. 22 , (. . 12).
. 22. ,
(, ) , , .
, .
.
-1.
, .
, , , .
, , , .
.
, . , . , , , , .
, ; , .
, , , , .
[26].
, , Matematica (3,4) Wolfram Research,Inc. (DiscreteMath) , , , .