.


:




:

































 

 

 

 


.




-

-

 


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, xjU 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, xU (a, yU, (z, a), (x, aU (y, aU.

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. 





:


: 2016-09-03; !; : 392 |


:

:

: , .
==> ...

774 - | 737 -


© 2015-2024 lektsii.org - -

: 0.177 .