( ). :
-
-
-
-
-
-
-
1. | 11. | |||||
2. | 12. | |||||
3. | 13. | |||||
4. | 14. | |||||
5. | 15. | |||||
6. | 16. | |||||
7. | 17. | |||||
8. | 18. | |||||
9. | 19. | |||||
10. | 20. |
: 2,3,5,7,8,9,12,14
3 (1)
:
:
:
:
1.
2. ,
3.
4.
5.
- <V, E>, V - , E - , . , , , : .
, - ( - ) ( ). . .
, 3.1 , 3.2 - .
, - , ( 3.3). , , .
3.1
e v , v e.
3.2 3.3
, , . ( 0).
, ( , ). , , .
- ( ), . , , 3.1, a : adbc abc.
|
|
v u, , u v.
, .
- . . , . 3.4 , : [abhk], [gd], [c] [f].
- , . , adbc abc ( 3.1) - 3 2 .
3.4
, v k - u, u v k . . , , 3.1, a 4 :
0) a;
1) b, d;
2) b, d, c ( adb, abd, abc);
3) c ( adbc).
u v - u v. , a c 3.1 2.
- . , , . , abda 3.1.
- , , ( ). . , 3.5 : dbacfbcd.
3.5
- , ( ), ( 3.5; : abdfca).
() - , . . ( 3.6).
3.6
, : ( ), - ( ). , - , .
, , .
, (, , , ..), - . .
- , : , - .
- ( ), , . , 3.6 , 2 5. , .
( : ) ( ) - (), (, ) . . - : , , .
|
|
: ( ) , 1.
() - () , . - , , . , a d , 3.7, 6.
3.7.
N- v - , ( v) , N.
Sm - N×N (N - ), : e, u v, Sm [ u, v ] = 1, Sm [ u,v ] = 0.
, , : , - .
. :
e, u v, Sm [ u,v ] = ves(e), Sm [ u,v ] = 0.
, 0. : , , - .
, 3.5, 3.6 3.7.
( 3.5) | ( 3.6) | ( 3.7) | ||||||||||||||
a | b | c | d | f | 1 | 2 | 3 | 4 | 5 | a | b | c | d | |||
a | 1 | a | ||||||||||||||
b | 2 | b | ||||||||||||||
c | 3 | c | ||||||||||||||
d | 4 | d | ||||||||||||||
f | 5 |
, . - : , , , (). , : .
- . ():
<__> <__> [<_>](), 3.5, 3.6 3.7.
()
a b c da c c fb c f db d b f | 1 2 3 21 4 3 53 1 4 3 | a b 1 c d 3a c 10b c 2b d 10 |
, , - .
- , ( - , ). , , . , :
|
|
, .
, , 3.5, 3.6 3.7.
a: b cb: c d fc: d fd: f | 1: 2 4 3: 1 2 54: 3 | b: a 1 c 2 d 10c: a 10 d 3 |
, : , - .
- , .
, .
1. - .
2. - , N N-1 .
3. - , .
- , .
() | ||
( - ) | ||
( ) | " - " |
- ( 3.8).
3.8 3
- , : , ( : ) (); :
1. ; ;
2. ; .
( ) : . , , - .
v - , , v. v - , , v. : , .
- , . .
- , . , - .
, , .