-
-
519.1 (075)
, .. / .. ,
.. . : - . . . -, 2012. 25 .
. , .
1 090900 2 230100 , 230400 .
, .
: .. , - . , ,
.
, 2012
. 4
1. . 4
2. . 7
3. .. 9
4. .. 10
5. . 10
6. . 12
7. , , .. 13
8. . . 14
9. . 17
10. . . 18
11. .. 20
12. .. 21
13. .. 22
14. . .. 24
.. 25
, . .
1936 ë. 1736 , ë . . . 1 ë ( ), , . , , . .
. , ë , . , ë , , , , , .
|
|
, . , . [5], .
S , V(2) .
1.1. ( ) G (S, U), U V(2). G = (S, U).
1.2. G = (S, U) . S G, U ë.
1.3. G = (S, U) -,
U = Æ.
1.4. G = (S, U) .
n, = n.
S (), U x y, (x, y).
U (x, x) .
1.5. ë (x, x) .
1.6. U ( ) ë.
, ë. ë .
1.7. ( ë).
1.8. ë .
, ë.
, , . , ë. . , .
1.1. , ,
. 2, , , .
. , G1, G3, G4, G5 , G1, G4, G5 .
1.9. ( ), U .
(x, y) , (x, y) , x y
(x, y).
1.10. ( ), U .
1.11. ( ).
x (x, y) ë , y ë . , (x, y) x y.
, .
1.1. (x, y) (x, y) (y, x). , (x, y) (y, x) .
|
|
x, y, z ( ), v, u, w ( ).
- . , , .
1.12. , .
1.13. x u , x u, .
1.14. , .
1.15. ë () () G, xi () xi deg (xi) ( . degree ).
1.16. , ë .
1.17. , ë .
1.2. , , x, ë P (x) 2, , x, 1.
1.18. () xi deg + (xi) (deg (xi)) , xi ( xi).
deg (xi) = deg + (xi) + deg (xi).
1.3. , x, 1, deg + (x), deg (x).
1.2. x2, x4 G1 x2, x4 G2, ë . 3.
. G1 :
deg (x2) = 2 deg (x4) = 5.
G2 :
deg + (x2) = 2, deg (x2) = 3
deg + (x4) = 2, deg (x4) = 1.
1.19. , , . n Kn.
. 4 K1, K2, K3 K4.
1.20. , (), .
1.21. , , , , . , p q , Kp,q.
. 5 K1,4 K3,3.
1. () ë ().
2. . .
2.1. G = (S, U) ë:
S = { x1, x2, x3, x4, x5, x6 },
U = {(x1, x2),(x1, x3),(x1, x6),(x2, x3),(x2, x5),(x3, x4),(x3, x5), (x3, x6), (x4, x5)}. , . 6.
3. . . , , .
2.1. G = (S, U) n P (G)= n, , pij , i - j -.
(. 1.1).
2.2. G = (S, U), = m, Q (G)= m, qij , ui uj, .
|
|
qij , ui uj , , .
2.3. G = (S, U), = n = m, R (G)= n ´ m. rij 1, uj i - ; 1, uj i - ; 0, uj i - .
rij , xi uj, , xi uj.
2.4. G = (S, U), = n, B(G) = n,
, B(G) . , , .
2.2. G, ë . 7, , .
. P (G):
Q (G) R (G):
3.1. G1 = (S1, U1) G2 = (S2, U2) (G1 @ G2), S1 S2 , , . .
, . , .
3.1. . , , () , . , . 8 .
, .
3.2. G n , 1 n.
. 9 3.
, ( ) .
3.2. .
3.1. , ( i - j - i - j - ).
3.1 , . .
3.3. G (rank G) P(G).
3.3. .
3.2. , .
() , , - . , , , . , ë .
|
|
4.1. G = (S, U) , (xi, xj)Î U w (xi, xj). , w (xi, xj) (xi, xj).
.
W = (wij), wij (xi, xj). .
5.1. G ¢= (S ¢, U ¢) G = (S, U), S ¢Í S, U ¢ G, S ¢.
5.2. , .
5.3. G ¢= (S ¢, U ¢) G = (S, U), S ¢Í S, U ¢ G, S ¢.
, .
G ¢ S ¢ , G ¢(S ¢). G ¢= (S ¢, U ¢) , ë S ¢ ( -ë ).
5.1. . 10 G, , ë x1, x2, x4, , G, ë.
ë .
G . G ¢(S ¢) G ²(S ²) G. , G ¢(S ¢) G ²(S ²) ( G ¢Í G ²), S ¢Í S ². , G . G . .
5.1. G = (S, U) ( ), S ¢Í S, S ¢ ¹ Æ G ¢(S ¢) G. P (G ¢) G ¢ P (G) G, , S ¢.
5.4. G ¢(S ¢) G.
5.5. x G, x, x .
5.2. . 11 G, G x5 G.
5.1. x , .
, , .
5.6. () x , ë x , x
( x) ë.
, .
1. () . G1 È G2 G1 = (S1, U1) G2 = (S2, U2) (S1 È S2, U1 È U2).
2. () . G1 Ç G2
G1 = (S1, U1) G2 = (S2, U2), S1 Ç S2 ¹ Æ, (S1 Ç S2, U1 Ç U2).
3. . G = (S, U) , , G, ë , G.
4. . G = (S, U) G1 ´ G2 G1 = (S1, U1) G2 = (S2, U2), S = S1 ´ S2, ë U : (x1, x2) (y1, y2) G , x1 y1 , x2 y2 G2, x2 y2 , x1 y1 G1.
5. . ,
G = (S, U) x ë (), x G. G (S \{ x }).
|
|
6. (). , () u ë () U G = (S, U), () u G. () u .
7. . , G = (S, U) G ¢ = (S È{ x }, U), x G.
8. (). , G = (S, U) G ¢= (S È{ x, y }, U È{(x, y)}, ()
(x, y) G.
9. . x y
G = (S, U). x y , G x y z, ë () , M , x y G. G , a Î M
(a, z), (a, x)Î U (a, y)Î U, (z, a), (x, a)Î U (y, a)Î U.
10. (). () . G G1, G1 G ë ().
11. (). () (x, y) G = (S, U) , U () (x, y), S z
U \ {(x, y)} ë (x, z) (z, y).
, ,
7.1. G = (S, U) (). ë ()
x1, u1, x2, u2, , xk, uk, xk+1 (7.1)
( k ³ 1, xi Î S, i = 1, , k +1, uj Î U, j = 1, , k) ,
j = 1, , k () uj (xj, xj+1), , x1 xk+1 (ë x1 xk+1). x1 , xk+1 .
,
x1, x2, , xk+1 u1, u2, , uk.
7.2. () ë () ().
7.3. () , (.. x1 = xk+1).
7.4. (), ë () .
7.5. , .
7.6. () (), ë () .
7.7. () (), .
7.1. . 12. () , , ( ), , ( ), .
. () : x1 - x7 - x3 - x4 - x6 - x9 - x8.
:
x1 - x2 - x6 - x5 - x4 - x 6 - x7 - x1.
( ):
x9 - x6 - x2 - x1 - x7 - x6 - x4.
:
x8 - x7 - x3 - x4 - x5 - x6 - x2.
( ):
x1 - x2 - x6 - x9 - x4 - x6 - x7 - x1.
:
x7 - x3 - x4 - x6 - x9 - x8 - x7.
.
8.1. () ( ), (), x y ( x y).
, y () G x, y = x, x y (, x ).
, G , .
8.2. , G = (S, U),
F (G), G ë .
8.3. G , F (G) .
8.4. () , ( ).
8.1. . 13 ë , . 13 , .., , x2 x1.
8.1. .
8.5. () () , () .
8.1. G = (S, U) k :
G1 = (S1, U1), , Gk = (Sk, Uk).
1) S = S1 È È Sk, U = U1 ÈÈ Uk, .. G = G1 ÈÈ Gk;
2) Si Ç Sj = Æ, Ui Ç Uj = Æ i ¹ j;
3)
8.2. G = (S, U) k : G1 = (S1, U1), , Gk = (Sk, Uk).
1) S = S1 È È Sk, U1 ÈÈ Uk Í U;
2) Si Ç Sj = Æ, Ui Ç Uj = Æ i ¹ j;
3)
, ë () .
P (G) G = (S, U) n. B = (bij) n, : B = E + P + P2 + + Pn.
8.6. C = (cij) n,
G.
, cij , G xi xj.
8.7. L = (lij) n,
G.
, L = CT. L .
8.8. F = (fij) n, F = C * L, * C L (.. fij = cij lij i j), G.
fij F , xi xj . , Gp = (Sp, Up) G = (S, U), xi, xj Î S, fij = 1.
ë () .
8.1. P (G) G = (S, U) n k - P. Pk , k () G xi xj.
8.1. G, . 14, , x 1.
.
G:
G
, B Pk, k = 1, 2, 3, 4:
, B = E + P + P2 + P3 + P4 =
G:
G: F = C * L =
, G G1 = (S1, U1), G2 = (S2, U2) G3 = (S3, U3), S1 = { x1 }, S2 = { x2, x3 },
S3 = { x4 }, . 15.