Ͳ Dz
, . 2
050902 ,
( : )
" -
2010 .
2010
, . 2 050902 , ( : ) / . .. . - : "", 2010. - 28 .
.. , . . ., .
³ .. , . . ., .
.. , . . ., .
Ͳ Ͳ ²Ҳ
- ᒺ. ᒺ, , .
' S, ÎS ( S). S, ÏS. . , S={1,2,3} 1,2,3 . 2 , 4 - , 2ÎS, 4ÏS. , .
, . =.
, {1,2,3,1} = {1,2,3} = {3,2,1}.
:
Æ , ;
Z ; Z = {..., -2, - 1,0,1, 2,...};
R ;
N ; N = {0,1,2,...}. ( 1 - .)
( Î Î), , Í. , ; Ì. ( Í , .) - Í.
, Í Í.
- , Í Í Í.
- Æ Í .
: , , . , {: ÎZ /2 - }. Z, /2 - . .
|
|
|
ᒺ , . C = AÈB. yÎAÈB ( º) yÎA yÎB.
, yÎAÈB º yÎA yÎB.
, A ={, }, ={, }, C = AÈB = {, , , }.
.1. ᒺ C = A È B.
, . C = AÇB.
, y Î A Ç B º y Î A y Î B.
:= {x½xÎA xÎB}
. 2. C = AÇB.
, .
г , , . C = A\B.
y Î A\B º y Î A y Ï B.
. 3. г C = A\B.
, , . D.
. 4. C = D
. :={1, 2, 3}; B:={3, 4, 5}.
A\B = {1, 2}; ADB={1, 2, 4, 5}.
G = (V, ) V ( ) V ( ).
G = (V, ) = áV; Eñ, V ≠ Æ, EÌV×V, E = E-1.
p, q:
p:=p(G):=|V|, q:=q(G):= |E|.
v1, v2 , = (v1, v2) , 璺. v1 , v2 . , , ; , , .
, v, v +(v):
+(v):={uÎV½(u, v)ÎE}, (v):= *(v):= +(v)È{v},
uÎ(v)ÛvÎ(u):
: ( ), .
(. 1), .
. 1. ij
v1 v2, v2 v3, v3 v4, v4 v1, v2 v4 , v1 v3 . : 1 2, 2 3, 3 4, 4 1, 1 5, 2 5, 3 5, 4 5. : 1 3, 2 4.
.
, ( ). V , .
. 2() {1,2,3,4,5,6}. , - . , - , .
|
|
|
G = (V, ) : {u, v}, u, vÎV u≠v. (u, v) {u, v}; (u, v) (v, u) . -, ( ).
2() {1,2,3,4,5,6}.
( ). (u,v) , u v.
. 2. .
() (V, E), V={1, 2, 3, 4, 5, 6} ={(1, 2), (2, 2), (2, 4), (2, 5), (4, 1), (4, 5), (5, 4), (6, 3)}. (2, 2) -;
() G=(V, ), V - {1, 2, 3, 4, 5, 6} = {(1, 2), (1, 5), (2, 5), (3, 6)}. 4 ( );
() ϳ (), () {1, 2, 3, 6}.
G¢=(V¢, ¢) G=(V, ) ( G¢ÌG), V¢ÌV / E¢ÌE.
V¢=V G¢ G.
ʳ , v, ( ) v d(v):
"vÎV 0 £ d(v) £ p-1, d(v) = |(v)|.
0 ( d(v) =0), . 1 ( d(v) =1), , . , . 5() 2 2.
, v, , , . d-(v) d+(v). . , 2 . 2() 2, 3 5.
k u v áv0, v1, v2,,vkñ, v0 = u, vk = v (vi-1, vi)Î i = 1, 2,..., k. , k k . v0, v1, v2,,vk (v0,v1), (v1,v2),,(vk-1,vk). v0 , vk - ; , v0 vk. u u' u u', , u' u . ( ) u ~ u'.
, . , . 2() á1,2,5,4ñ 3, á2,5,4,5ñ , .
ϳ =áv0, v1, v2,,vkñ , , , ávi, vi+1,,vjñ i, j, 0 £ i £ j £ k.
, . áv0, v1, v2,,vkñ , ( ), v0, v1, v2,,vk . - 1. , : k k ( - k ). , . 2() á1,2,4,1ñ, á2,4,1,2ñ á4,1,2,4ñ . , á1,2,4,5,4,1ñ . á2,2ñ, - (2,2). , -, .
|
|
|
áv0, v1, v2,,vkñ () , k ³ 3, v0 = vk v1, v2,,vk . , . 2() á1,2,5,1ñ.
, , .
', - .
. ' . , . 2() ' : {1,2,5}, {3,6} {4}. ' , ' .
', - ( ) - . - ' , u v v u. ' , ' . . 2() : {1,2,4,5}. {3} {6}. ³, {3,6} ' , 3 6, .
- G , {u, v} (u, v) (v, u), . , , , - ' (u, v) (v, u) {u, v}. u - , ( ); , v u , v u u v. v - u v u .
.
, (- - ).
(V, ) , V V1 V2 , - .
. , , , , , -.
ó , , , . .
, ' () ( ). , .
. 4. () . () ˳. () , , , .
. 4() ; . 4() . ˳ . 4() , '. . 4() , , .
.
2 ( ).
G = (V, ) - . :
1) G ( );
2) - G ;
|
|
|
3) G ', ', - ;
4) G ' || = |V| - 1;
5) G || = |V| - 1;
6) G , - .
.
( , ) :
1. , 0. ;
2. 1;
3. .
, , , (' ) , . 6() 12 7.
: , , , ,
. , , ,
1, vi vj,
[i,j] =
0, vi vj .
. , , ,
 |
1, vi j,
[i,j] =
0, .
 |
1, vi j ,
[i,j] = 0, vi j .
-1, vi j .
G = (V, ) |V| . uÎV ( ) ( v, (u, v)Î).
.. 1. :
() G 5 7 ;
() ;
() .
. 2. :
() G 6 8 ;
() ;
() .
. 1() . 1() . . 2() . 2().
: (u, v) v Adj[u]. , (u, v) u, v.
, , w: ER. w(u, v) (u, v)Î v , u. , ' .
ز
