GRAPH2007.dvi

Transcription

1 / URL:

2

3 ? k

4 ,, Menger Hall ,, Hall Hall : Menger

5 004 ( / 4 ) ( / 4 ) ( / 4 ) ( / 4 ) ( / 4 ) ( / 4 ) ( / 4 ) ( / 4 ) ( 4 ) ( 4 ) ( 4 ) 67 5

6

7 7.,..,,,,,, /,,. /,. *.* ( ) 5 ( ) (, II(B)) / ( / ).,,.,.,,,,...?,.,,.,,,,.,,,,,,. (vertex) (. P,Q,R,S,T),, (edge) (. PQ, QR ). (degree). :. P.. Q 4.

8 P Q R T S.:. n =5, m =8, deg(p) = deg(t) =, deg(q) = deg(s) = 4, deg(r) =.., P,Q. { deg(p) = (.) deg(q) = 4.,. P,Q,R,R,T.,,, P deg(p) = P..,,,,..,. ( ),.,., P Q Q R = P T R T S S.:.,. ( )., A, B, A B. ( ),, 5 n =5,,, G G (, G ).,,,.,,,.,. 8

9 .,,.....,.,.,, (multiple edges) P,Q, Q P T R S..:, TS, QS, P. (loop) P P (simple graph) (directed graph : digraph ) Q P T R S.4:., (, P Q ). (walk). 9

10 (path). (cycle). Q S T Q.... P Q T U S R V.5:.. (connected graph). (disconnected graph) (.5 ). (component)..5,.. :,. P () Q P () Q () () (6) (5) R (5) (7) R () () T (4) S T (4) S.6: ( ), ( ). (Eulerian graph). (Hamiltonian graph).,,, 0

11 .,, ( ), Euler ( ), Ore ( ).,,...7:. (tree) (.7 ).,. ( ).,,.

12 . (004 ). C 5 H ( )., (CH 4 ),. H H C H H. John Joan, Jean Jane, Joe Jean Joan, Jean Joan. John, Joan, Jean, Jane Joe.. a,b,c,d,e,f 6. a b c d e f 4 4.,,.,. ( ) :., C n H n+, n 4, n +.,,..8( ). A A H H H H H c c c c c C H c c c c c H H H H H H C H H H H B c c c c c c c c c B H H H H c H H c c c H H c H H H H c c c c H H H c H H H H c H.8: n =5 ( )., A, B --, C -., C 5 H.,,.8( ).

13 : (, ),.9,, C 5 H 0, C 5 H. 4 H H H H c c H H c c H H c H H.9: C 5 H 0.. ( ) ( ).0( ). b a f b a f c e c e d d John b a f b a f c e c e Jane Jean Joan d d b a f c e Joe d.0: John, Joan, Jean, Jane Joe ( ). 5 ( )...0( ) 5.. (005 ) () V = {v,v,v,v 4,v 5,v 6 },, E = {v v, v v, v v 4, v 4 v, v 4 v, v 5 v 6 }. (),..,,,.. ( ). (),. ( ). () s( ), f( ), sn( ), sp( ), b( ), i( ), ( ) ( ),. ( ). 4 Cayley ( ).

14 v v v s v4 f i sn v5 sp v6 b.:, ( ). ( ).. (006 ). (),. (,,, ) () ( ) n., n =7,. (,., n =7.) ( ) (),. () n =7.., : 5 4 A group B group : 7. group A group B,.. 4 6,.,, ( group A ),,, A B B A,, ( ),. 4

15 .4 (007 ) (),. () V E, V = {v,v,v,v 4,v 5 } E = {v v, v v, v v 4, v 4 v 5, v 5 v, v v, v v 5, v 5 v, v v 4, v 4 v }.,,. ( ) (),, ( ),, ( ),,.,,.,,, ( )..,.,.,, 4 9, 4 ( ),,.,,., (, ), ( ),,. ().. ( 5 ) V v5 V v4 V,..:.. 5

16 . 0. ( n n C = n(n )/.),.,

17 7..,,... :,. V (G) : G (vertex set) E(G) : G (edge set) ψ G : G (incidence function) ( )G V (G) E(G). G V (G) V (G) ( ) E(G)..4. G G G, ψ G (e ) = uv, ψ G (e )=vw ψ G (e ) = wu, ψ G (e 4 )=wz. u e e e4 z V(G)={u,v,w,z} v e w E(G)={uv,vw,vw,wz}.4: G V (G) E(G).,.5 (general graph) ( ). uv( ), vv(, ), vw( ), uw( ), wz( ).

18 u z v w.5: G... G G, G G, G G (isomorphic)..6 G u v w l (u) p (x) r (z) m (v) x y z G n (w) g (y) G.6: G G. G, G. ( ), G, G, : θ : V (G ) V (G ) φ : E(G ) E(G ) : ψ G (e) =uv ψ G (φ(e)) = θ(u)θ(v). (φ, θ) G, G,, G, G, G = G..6 G, G θ(u) =l, θ(v) =m, θ(w) =n θ(x) =p, θ(y) =q,θ(z) =r φ(ux) = lp = θ(u)θ(x) 8

19 φ(uz) = lr = θ(u)θ(z) ψ G (ux) =ux ψ G (φ(ux)) = ψ G (lp) =lp = θ(u)θ(x),,.6 G, G (, φ, θ ).....,, :...4,,,., G u, v, G u, v, u v., G u, v, u v u v V i G G V,V,,V i,,v n, G(V ), G(V ),, G(V n ) G (component), (connected graph)..8 (G ), (G )., (disconnected graph)...5 G v,. v (degree) v.,. deg(v). 9

20 G G.8: G G.G. (isolated vertex) (end-vertex) G (degree sequence)...8 G, (,,,,, 4, 5).,. (handshaking lemma) :., d,d,,d n, n G, i deg(v i ) = d i (.), d,d,,d n., (4,,,, ), v v5 v4 v v.9:..9. d(v )=4, d(v )=, d(v )=, d(v 4 )=, d(v 5 ) = (.)...6 G (subgraph) : V (G), E(G). 0

21 ,, G, (, ), G...7,.,,. G,,,n,,,,m (adjacency matrix) : i j ij n n (incidence matrix) : i j, ij, 0 n m 5. (00 # ) (). () A M. ( ) () (,,, ). () A A = (.4) M M = (.5) 5 v e, ve,,., 0.

22 .. (004 ).. G G φ, θ. a b e 4 5 c d G G, G e u, v ψ G (e) =uv ψ G (φ(e)) = θ(u)θ(v), {e, u, v}...6 G.. A, M A = 0 0, M = ( ). θ, φ G, G θ(a) =,θ(b) =,θ(c) =,θ(d) =4,θ(e) =5 φ(ab) =,φ(bc) =,φ(cd) =4,φ(bd) =4 φ(de) =45,φ(ce) =5,φ(ea) =5, ψ G (ab) =ab ψ G (φ(ab)) = ψ G () =θ(a)θ(b) ψ G (bc) =bc ψ G (φ(bc)) = ψ G () =θ(b)θ(c) ψ G (cd) =cd ψ G (φ(cd)) = ψ G (4) =θ(c)θ(d) ψ G (de) =de ψ G (φ(de)) = ψ G (45) =θ(d)θ(e) ψ G (ea) =ea ψ G (φ(ea)) = ψ G (5) =θ(e)θ(a) ψ G (ce) =ce ψ G (φ(ce)) = ψ G (5) =θ(c)θ(e) ψ G (bd) =bd ψ G (φ(bd)) = ψ G (4) =θ(b)θ(d).

23 r p l p n m.0: G...0 G.., A., n =5,., A,...,, b a d e c.: A., A,,, a,b,.. M,.,,. i, j l, i, j l... e b 8 c 6 a d.: M., M,, a,b,.

24 . (005 ). () 5 8. (i) (ii), (iii), () A, M () 6, (,, 5, 5, 5, 5).? ( ). (i)(ii)(iii).. (i) (ii) (iii) : 5 8 (i)(ii)(iii).., A, M A = , M = (.6)

25 () () 6(5) (5) 5(5) 4(5).4: 6 (,, 5, 5, 5, 5)..4 (006 ). () #. (),.,,. () (,,,,, )?. ()...5 G, G θ, φ, G e u, v ψ G (e) =uv ψ G (φ(e)) = θ(u)θ(v) {e, u, v}. ( ) a b G G 4 c d.5: G, G. () A A = (.7) 5

26 .,.6, M M = (.8). 4 A group B group :. ().7 K, (,,,,, ), (,,,,, ). K,...7: (,,,,, ). () θ, φ θ(a) =,θ(b) =,θ(c) =,θ(d) =4 (.9) φ(ab) =,φ(ac) =,φ(ad) =4,φ(bd) =4,φ(cd) =4,φ(bc) = (.0), ψ G,ψ G ψ G (ab) =ab ψ G (φ(ab)) = ψ G () = = θ(a)θ(b) (.) ψ G (ac) =ac ψ G (φ(ac)) = ψ G () = = θ(a)θ(c) (.) ψ G (ad) =ad ψ G (φ(ad)) = ψ G (4) =4 = θ(a)θ(d) (.) ψ G (bd) =bd ψ G (φ(bd)) = ψ G (4) =4 = θ(b)θ(d) (.4) 6

27 ψ G (cd) =cd ψ G (φ(cd)) = ψ G (4) =4 = θ(c)θ(d) (.5) ψ G (bc) =bc ψ G (φ(bc)) = ψ G () = = θ(b)θ(c) (.6)., G,G.,.,, (, ),,,,,..5-a.5-f.5-g..5-a (004 II(B) #) G u, v d(u, v)., u, v ( u) G, d(u, v) u, e(u)., G u e(u) G, R(G)., u e(u) G, D(G)., G, G..8( ) G e() =, e() =, e() =, e(4) =, e(5) =, R(G) =,D(G) =, {,,, 4, 5}, {,,, 4, 5}..8( ),,,,,. G G : G( ) e() =, e() =, e() =, e(4) =, e(5) =, R(G) =,D(G) =, {,,, 4, 5}, {,,, 4, 5}. G( ). ( ), u, v d(u, v) u v.,.8( ) d(, ) =, d(, ) =, d(, 4) =, d(.5) =, d(, 6) = (.7) 7

28 , e() e() = max d(,y) = (.8) y.,, 6 (.7)(.8), d(, ) =, d(, ) =, d(, 4) =, d(, 5) =, d(, 6) =, e() = max y d(,y)= d(, ) =, d(, ) =, d(, 4) =, d(, 5) =, d(, 6) =, e() = max y d(,y)= d(4, ) =, d(4, ) =, d(4, ) =, d(4, 5) =, d(4, 6) =, e(4) = max y 4 d(4,y)= d(5, ) =, d(5, ) =, d(5, ) =, d(5, 4) =, d(5, 6) =, e(5) = max y 5 d(5,y)= d(6, ) =, d(6, ) =, d(6, ) =, d(6, 4) =, d(6, 5) =, e(6) = max y 6 d(6,y)=,,.8 ( ) G R(G),, D(G)., {,, 4, 5}, {, 4}. R(G) min e(x) = x (.9) D(G) max e(x) = x (.0).5-b (004 II(B) #) A G, : r S(r) = A + A + A + + A r = A k (.) [S(r)] ij i j r.8( ) G., (.) r, S(r) r,.5-a D(G).8( ) G. ( ), G A A = (.) k= 8

29 .,, A, A A =, A = (.) (A, A, A )., S(), S(), S() S() = A = (.4) S() = A + A = (.5) S() = A + A + A = (.6) , r =, S(r)., r =.5-a D(G). 9

30 .5-c (004 II(B) #).5-b S(r), η η W (r) = A η + ( A η ) + ( ) A + + η ( ) r A = η,,. ( ), W (). η =6 r k= ( ) k A (.7) η.,.8( ) G, ( ),., W (r) C r (i, r) = [W (r)] i +[W (r)] i + +[W (r)] ni = n [W (r)] ji (.8) i r..8( ) G., η =6.,.8( ) j= W () = η A + η A = = (.9)., C (i, ). C (, ) = 9 ( )= 6 6 C (, ) = 6 ( )= 6 6 C (, ) = 8 ( )= 6 6 C (4, ) = 9 ( )= 6 6 C (5, ) = 6 ( )= 6 6 C (6, ) = 8 ( )= 6 6, η =, C (i, ), G i,, η =6,,,, i ( ).,, 5,, 4. G.,, 0

31 ,., D(G) =, W (),, C (i, ) W () = η A + η A + η A = W () + η A = = (.0) C (, ) = C (, ) = C (, ) = C (4, ) = C (5, ) = C (6, ) =, r =..5-d (004 II(B) #) ( ) = ( ) = ( ) = 6 6 ( ) = 6 6 ( ) = 55 6 ( ) = ( ).9.,,., A [A] ij i, j,.,.9 G A. ( ),.9 G

32 G :.8( ) G. A A = (.)..5-e (004 II(B) #).5-d, X A/η (η = 6).,. G. X = lim r Xr = 0 ( ) (.) ( ) A r ij [A r ] ij = A il A ll A ll A lr l r A lr j (.) l = l = l r =., A [A r ] ij = =6 r (.4) l = l = l r = (η =6 ), X = A/η r ij [X r ] ij = 6r 6 r = 6 (.5)

33 ,.,,, R [A r ] ij. [A r ] ij = ( ) r A il A ll A ll A lr l r A lr j 6 r (.6) R l = l = l r =, X r ij [X r ] ij 6 ( ) r 0 (r ) (.7) R. X = lim r Xr = 0 (.8)..5-f (004 II(B) #) X = 0 ( ) X X + X + = X k = (I X) I (.9) k=0., I.,,.5-d W ( ). ( ). I = (I + X + X + ) (X + X + ) = (I X)+(I X)X +(I X)X + = (I X)(I + X + X + ) (.40) I + X + X + = (I X) (.4) X + X + = X k = (I X) I (.4) k=., W ( )., W ( ) = X k =(I (A/η)) I k=

34 = (.4), C (, ) = C (, ) = 0.4 C (, ) = 0.79 C (4, ) = C (5, ) = C (6, ) = g (004 II(B) #).5-f.9 G,?,,,. ( ) 5, 5,,.,, 5 (, ),. 4

35 .6 (00 II(B) #) () (5). () A : A = (.44). () G : G = (.45). (). (4). (5). ( ) (), :. (),,,,,,,.., 4 ++=, 4..,. (),. (4). (5).,,. 5

36 4 4.:,,,., 4,..7 (00 II(B) #) () (). (), 8., 4,. () n N (n)., : N (n) = n(n ) (.46) (a + b) n = n nc k a k b n k (.47) k=0. () n m. ( ) (). () n, n nc = n(n ) (.48)., n N (n), n(n )/,, 6

37 ,, n(n )/ N (n) = n(n ), : a = b = C 0 + n(n ) C + n(n ) (a + b) n = n = C + + n(n ) C n(n ) = n(n ) k=0 n(n ) C k (.49) n nc k a k b k n (.50) k=0 n nc k (.5), (.49) n n(n )/ n(n ), n. () n(n )/, m }!. k=0 n(n ) C m = k=0 n(n ) C k = n(n ) (.5) m! { n(n ) { n(n ) m }! (.5).7 (007 ) ()(). () (,,,,,,,,, )?.,,. () K,,K 4,4,... ( ) () (,,,,,,,,, )..,,,,,.. () K,,, K 4,4.., G, G θ, φ θ() =a,θ() =c,θ() =e,θ(4) =g,θ(5) =h,θ(6) =b,θ(7) =d,θ(8) =f (.54) φ(5) =ah,φ(6) =ab,φ(7) =ad,φ(8) =af (.55) φ(5) =ch,φ(6) =cb,φ(7) =cd,φ(8) =cf (.56) φ(5) =eh,φ(6) =eb,φ(7) =ed,φ(8) =ef (.57) φ(45) =gh,φ(46) =gb,φ(47) =gd,φ(48) =gf (.58) 7

38 .:. 4 a h b g c G f d e G.: K 4,4.,, G, G ψ G,ψ G ψ G (5) =5 ψ G (φ(5)) = ψ G (ah) =ah = θ()θ(5) (.59), G, G. 8

39 9. G, ( ),.,,,,.,,... (null graph) : ( ),, n N n..4 N 4. N 4.4: N 4... (complete graph) : ( ). ( v,v V (G),v v, v, v.) n K n. n K n,,,,n,, n C = n(n )/., n =4 6, n =5 0,.5 (.4 () )... r- (regular graph) : v V (G), dev(v) =r., r. ( :, N n 0-, C n -, K n (n )-.)

40 K 5 K 4.5: K 4 K 5. -regular graph -regular graph.6: ( ),, )...4 (cycle graph) :. C n. C 6.7: C (path graph) : C n. P n...6 (wheel) :C n v, v ( ). W n. 40

41 P 6 C 6.8: C 6 6 P 6. C 5 W6.9: C 5 6 W (Petersen graph),.7(), 6..40:...8 (bipartite graph) : G A, B, G A B., G...9 (complete bipartite graph) :A B., r, s K r,s., K r,s (r + s) rs. 6 Petersen graph,,, (, ) 4

42 A G B.4: G.. K, K, K, K 4,.4: K,, K,, K,, K 4,...0 k- k- (k-cube) : a i = 0 or ( ) (a,a,,a k ), a i. Q k. Q k k, k k 7... (complement) : G G, V (G), G G,,.. (, )...,. 7 (0, 0, 0,, 0, 0,, 0), (0, 0, 0, 0,, 0,, 0), k k, k k k k. 4

43 Q z (0,0,) (0,,) (,0,) (,,) y (0,0,0) (0,,0) (,0,0) (,,0) x 00 0 Q : -. G G. u u y y v v x w x w.44:, A, B, C, D, E, F, G, H 8.,.,,., 8! = 460,. ( ) : A H ( ). #, # ( ). ( ) :., #, # A, B.. A, H B G #8, #7..., #=C,#4 = E, #5 = D, #6 = F. 4

44 K, K,.45: K,. # #4 #7 # # #8 #5 #6.46: ( ) : cube, cube, cube, cube4 cube B R G Y R R cube Y B R Y G G cube G cube4 B B R B B Y R R G Y Y,,, 4 4. () (),. () 4, R, B, G, Y,. cube, cube, cube, cube4. () () G. () G H, H, : cube, cube, cube, cube4,,,

45 ( ) (), cube, cube, cube, cube4.47. R B G Y R B G Y R B G Y R B G Y cube cube cube cube4 R B G Y : cube, cube, cube, cube4 ( ),, G( ). () (),.47( ) G. () cube,, G H, H,.48. H (FB), H (LR), cube, R B G Y R B G Y 4 4 H H B R Y G G Y B R Y B G R R G Y B F L B R : G H, H ( ),, ( ). cube, cube, cube4.48( ).. 45

46 . (004 ) G. 4 4 () G. ()? ()? (4) ɛ(g) G deg(v) =ɛ(g). v V (G) ( ) (), M 0 0 M = (),,,.,.,,,,. (),. (4) ()(), v V (G) deg(v),.,,,, ɛ(g),. v V (G) deg(v) = ɛ(g) 46

47 . (004 ).4 K 5. ().4 K 5 5,,, 5., A. (), A (, )-. (), A (, )-. (4), A G i, j K, A K (i, j)-. ( ) () K 5 A A = ,. (), K 5, [] [] 5 [] 4., A = , A (, )-.,. () (),,, [] [] [] 4 [4] 5 [5] 5 [6] 4 47

48 [7] [8] 4 [9] 5 [0] 4 [] 4 5 [] 5 [] 5 4,., A A =, (, )-,. (4) n K,, A K (i, j)- [A K ] ij = n n n a ik a kk a kk a kk k K a kkj k = k = k K =, a ik i k, [A K ] ij i, j.. (004 ) K r,s,t r, s, t,.,. () K,, K,,. () K r,s,t. ( ) () K,,.49 (K,,,.). () K r,s,t rs + rt + st. 48

49 A B K,, C.49: K,,. K,,,..4 (005 ). (i) (v) ( ). (i) 5. (ii). (iii). (iv). (v) 4 K 5,K 4,4,Q 4.. (self-complementrary). () 4, 5. () 8. ( ).(i) 5.50 K 5,5..50: 5. (ii),.5. (iii).5. (iv),.5 n =4, 6, 8, 0,. (a,a,,a n )=(,,, ), n =,,., 49

50 .5:..5:., n, m m = n (.60).,,., n., n =. (v) 4 K 5,K 4,4,Q (),, ( )., n m m = n(n )/,,, n(n )/4.,, n k, n =4k n =4k,,, n n =4k n =4k +. k =, n =4 n =5,,., n =4,,,. L, M, L, M. L +M = 6 (.6) L + M = 4 (.6) (L, M) =(, ), (,,, )..55 ( ). 50

51 n=4, m=6 n=6, m=9 n=8, m= n=0, m=5 n=, m=8.5: n =4, 6, 8, 0,., n =0. m =5..54: 4 8., n =5,,, L, M N, : L +M +N = 0 (.6) L + M + N = 5 (.64). (M, L, N) =(,, ), (,, ), (,,,, ) (,,,, ),,.55 ( ). n=4 n=5.55: 4, 5.. : 5

52 n =5,,, L, M, N L +M +N = 0 (.65) L + M + N = 5 (.66), L, M, N, L, M, N,, M =5,L= N =0. (,,,, ), : n =5.. () k = n =8, 8., (I)-(IV). (I).57 8,,, : ( ) )., 8 K 8. (II) 8 (,, 5, 7) ( ). (III), (,, 4). 0, 8., 4 0 = 4. (IV),, ( 5, 8 8+=, 8=, 8 ). (I)-(IV) 4,, (.57 ) 5

53 (.57 ) ( ), (.57, )..5 (006 ) G cube cube B Y G R B G R R Y R G Y cube cube 4 B R Y G B Y B G R Y B.58: 4. ( ),,.59 ( ).,.59 R cube G R cube G B Y B Y R G R cube G R cube4 G 4 4 B Y B Y B 4 Y.59: ( ) 4 ( ). ( ). RB, GY cube4,., 4. 5

54 .6 (005 II(B) #) G L(G) (line graph) G, G L(G).. () K K,,. (). () G k, L(G) k. (4) G, L(G). (5) L(K 5 ). ( ) ().60, K K,..60: K ( ) K,. ().6...6: (K 4 ) ( ). () k v i (i =,,m)(m ). (k ), v i v j (j i) (k ), v i (i =,,m), k k. (4) m (), (k ) n =m, m = n(k ) (.67). 54

55 (5) ()(4), L(K 5 ) n, m, d( ) n(l(k 5 )) = m(k 5 )=0, m(l(k 5 )) = n(k ) = 5 =5, d(l(k 5 )) = k = 6 (.68)., 0 K 0 n(k 0 )=0, m(k 0 )=45, d(k 0 ) = 9 (.69).,, L(K 5 ),, L(K 5 )+ = K 0,, m(k 0 ) m(l(k 5 )) = 45 5 = 0 = m( ), d(k 0 ) m(l(k 5 )) = 9 6= =d( ), ( 0, 0, )., L(K 5 )..7 (00 II(B) #) G k,. G m(k) k, m(k) k (.70) k., k. ( ). K k,k k, k, K k,k m(k) k (.7), K k,k (v, w), k + v, w K k,k (k +) ( )., K k,k v( ) k, K k,k w( ) w v.6: K,. K, v, w. k,, v w,, K k,k k K k+,k+ (.6 ), k +k +=(k +) 55

56 . m((k + )) (k +) (.7),, G m(k) k..8 (007 )., k,, A k (i, j), i, j k., x, : I + xa + x A + + x k A k + (.7) (I )., (.7) (i, j) x, x k i, j k., a : ( a) = +a + a + + a k + (.74), A (I xa) = I + xa + x A + + x k A k + (.75)., (I xa)., (.75), (I xa) (i, j) x, x k, i, j k.,.6, (I xa),. 4.6:. ( ) (),.,. ( ) 0 A =. (.76) 0 I xa = ( 0 0 ) ( x 0 0 ) ( = x x ) (.77) 56

57 ,, ( ) (I xa) x = x = x., x ( x x x x x x ) (.78) [(I xa) ], = +x + x x n + =[(I xa) ], (.79) [(I xa) ], = x + x + x x n+ + =[(I xa) ], (.80)., (, ),, k, k., (.79) x,. (, ), k, k., (.80) x,.,,. () (), 4 4 : 0 0 A = (.8) 0 0. I xa = x 0 x x x x 0 x 0 x x 0 (.8).,.. 4, : x x x 0 x 0 det(i xa) = x 0 x x 0 x + x x x x 0 x x 0 0 x { } { } x = x x x 0 x x x x x x 0 x x 0 x { } x + x + x x 0 x = x( x x + x ) x(x + x )+ x = 4x x + x 4 (.8)., ã ij I xa (i, j) [(I xa) ] ij = {det(i xa)} ( ) i+j ã ij (.84), ã ij x x x ã, = x 0 = x x 0 x 0 + x x = x 57

58 ã, = ã, = ã,4 = ã, = ã, = ã,4 = ã, = ã,4 = ã 4,4 = x x x = x x 0 0 x x x 0 = x x =ã, x x x 0 0 x 0 x x x x x x x 0 = x + x =ã, x x x 0 x = x x x 0 x 0 x x x = x x x =ã 4, 0 x = x 0 0 x 0 x = x 0 x x x 0 x 0 = x x x 0 x x 0 x 0 = x x =ã, x 0 x 0 x = x x 0 x 0 x x 0 x = x + x =ã 4, x x x x x = x x x + x x x x x x x x = x x x 0 x x x = x x 0 x 0 + x x x x 0 = x x =ã 4, x 0 x x x = 0 x x + x x 0 = x x,, (.84) ã i,j ( ) i+j ((, ), ( ) + =,(, ), ( ) + = ) x x +x x +x x+x x 4x x +x 4 4x x +x 4 4x x +x 4 4x x +x 4 (I xa) x +x x x x x +x = 4x x +x 4 4x x +x 4 4x x +x 4 4x x +x 4 x +x (.85) 4x x +x 4 4x x +x 4 4x x +x 4 4x x +x 4 x x x x x +x x x x 4x x +x 4 x +x 4x x +x 4 x +x 4x x +x 4 x 4x x +x 4.,, (, ) (, 4), (, ) (4, 4)., x,., (, ) x [(I xa) ], ( x ){+(4x +x x 4 )+(4x +x x 4 ) + } = +(4x x )+x +( 8x 4 x 4 +6x 4 )+O(x 5 ) = x 0 +x +x +7x 4 + O(x 5 ) (.86) 58

59 ., O(x α ) x α.,,, , : ( ) ( )., 4 4, 4 4 4, 4, 4 7 ( ).,., (, ). x [(I xa) ], (x + x){+(4x +x x 4 )+(4x +x x 4 ) + } = x + x +4x +(4x 4 +x 4 )+O(x 5 ) = x + x +4x +6x 4 + O(x 5 ) (.87).. 4,..65 4,., :. 4, 4 4, 4, 4 4, 4, (, ) x 4.,. 59

60 (, ). x [(I xa) ], (x + x ){+(4x +x x 4 )+(4x +x x 4 ) + } = x + x +4x 4 + O(x 5 ) (.88).,. 4., 4, 4, 4, 4.,,. (, 4) x [(I xa) ],4 (x + x x ){+(4x +x x 4 )+(4x +x x 4 ) + } = x + x +( x +4x )+(4x 4 +x 4 )+O(x 5 ) = x + x +x +6x 4 + O(x 5 ) (.89) , 4 4, , 4, 4 4 4, 4, 4 4 6,. (, ). x 4 [(I xa) ], ( x ){+(4x +x x 4 )+(4x +x x 4 ) + } = +(4x x )+x +( 4x 4 x 4 +6x 4 )+O(x 5 ) = x 0 +x +x +x 4 + O(x 5 ) (.90).,, 4,, 4, 4. 4, 4 4, 4, 4 4, 4, 4, 4 4,.,,., x 4. = (I xa) x 4 +x +x +7x 4 x + x +4x +6x 4 x + x +4x 4 x + x +x +6x 4 x + x +4x +6x 4 +x +x +x 4 x +x +x 4 x + x +4x +6x 4 x + x +4x 4 x +x +x 4 +x +x 4 x + x +4x 4 x + x +x +6x 4 x + x +4x +6x 4 x + x +4x 4 +x +x +7x 4 (.9) 60

61 ,,,. :, (4),.,,. x,,. 6

62

63 6 4 4.,,,,. 4.. :. : v i (i =,,m) G, v 0 v,v v,,v m v m (walk). : v 0 v v v m (v 0 :, v m : ) : v 0 v,,v m v m : v 0,v,,v m ( v 0 = v m ) : x v z w y 4. (00 # ) 4.66:, x v w x G {v,v,,v n }, m t. () (). () G A, A ij v i v j. () A m. () A 6t. ( )

64 ().8. G n n A = A n k= A a ka k =, A ij b ij a a n (4.9) a n a nn n k= a ka kn n k= a n nka k k= a nka kn b b n b n b nn B (4.9) b ij = n a ik a kj (4.94) k=., a ik v i v k, a kj v k v j, a ik a kj v i v k v j ( 4.67 ). v k (k =,,n) (i = k, j = k v k v i. v j 4.67: v k v i v j. ), a ik a kj n a ik a kj = b ij (4.95) k= v i v j., A ij b ij v i v j. () (), B = A b ii = n a ik a ki (4.96) k= v i v k v i, v i v k ( 4.68 )., A n b ii = i= n n a ik a ki (4.97) i= k= G, m. 64

65 v k v i 4.68: v k, v i. () A A = n n k= l= a ka kl a l n k=, A ij n n k= l= a ka kl a ln n l= a n nka kl a l l= a nka kl a ln n k= c c n c n c nn = C (4.98) c ij = n n a ik a kl a lj (4.99) k= l=., a ik v i v k, a kl v k v l, a lj v l v j, a ik a kl a lj v i v k v l v j., {v k,v l } n n a ik a kl a lj = c ij (4.00) k= k=, A ij v i v j ( 4.69 )., v k v l v i v j 4.69: v i {v k,v l } v j. c ii = n n a ik a kl a li (4.0) k= l= v i v k v l v i. v i,v k v l., {v k,v l } n c ii = i= n n n a ik a kl a li (4.0) i= k= l= G 6 (i, k, l!=6 ) ( 4.70 ). 65

66 v k v i v l 4.70: v i, {v k,v l } v i.. n c ii = 6t (4.0) i= 5. G n. G k, G m. n k m (n k)(n k + ) (4.04) ( ), (4.04) : m n k. m =0, n = k, 0 0 0=0.,., m 0, m 0., G,,, : k k + : n n : m 0 m 0, (k +,n,m 0 ) m 0 n (k )., m 0, m 0, m 0 n k,, m : m n k., (4.04) : m (n k)(n k +)/., G k,, G., C i, C j, C i n i, C j n j (n i n j )., C i +C j N ij ( 4.7 ). N ij = n i(n i ) + n j(n j ) (4.05) 66

67 n j n i C j C i n j - n i + C j C i 4.7: C i, C j,..,. ( ) C i n i + C j n j, C i +C j, N ij., ( ), ΔN ij = N ij N ij. N ij = n i(n i +)+ (n j )(n j ) (4.06) = n i(n i +)+ (n j )(n j ) { n i(n i ) + } n j(n j +) = n i n j +> (4.07) 0,, k G n (k ) = n k + k ( ), m : ( ). m (n k)(n k + ) (4.08) 67

68 4. (00 II(B) #), v w d(v,w) v w., ()(). () d(v,w) d(v,z)+d(z,w) = d(v,w) (4.09) z. (), v w d(v,w) = d(v,w) =. ( ) () 4.7. v w C. C d(v,w). C z C C * w v C * 4.7: v z w C = C + C v w, d(v, w). C z, z C, v z C, z w C. z, C v z., v z C, C C C + C v w,., C v z, C d(v,z)., z w, C., C, C C C + C v w,., C z w, d(z,w).,, C z, z d(v,z)+d(z,w) = d(v,w) (4.0). () 4.7,.,, 6 ( d ). d(, ) = ( ), d(, ) = ( ), d(, 4) = ( 5 4) d(, 5) = ( 5), d(, 6) = ( 6), d(, 7) = ( 7), d(, 8) = ( 6 8), d(, 9) = ( 6 9), d(, 0) = ( 5 0) 68

69 : d(6, ) = (6 ), d(6, ) = (6 ), d(6, ) = (6 8 ) d(6, 4) = (6 9 4), d(6, 5) = (6 5), d(6, 7) = (6 9 7) d(6, 8) = (6 8), d(6, 9) = (6 9), d(6, 0) = (6 8 0), v, w d(v,w) = d(v,w) =. 4..,??. (disconnecting set), (separating set).. :. :, {e,e 6,e 7,e 8 }. (edge-connectivity) λ(g) : G. λ(g) =. λ(g) k, G k-. : ( ). :. 8,,. 69

70 w e y e6 e4 e e5 e7 v e x e8 z w y {e,e6,e7,e8} e e5 e4 v e x z 4.74: {e, e 6, e 7, e 8 }. κ(g) 9 : G. κ(g) k, G k-. ( ) κ(g) ( ).,, ( ) G κ(g), κ(g) ( ), ( ). κ(g), κ(g),., λ(g), λ(g), ( ), λ(g). w y y v x z {w,x} v z 4.75: {w, x}. 9,. 70

71 4. (00 II(B) #) G () (5). A e B G e7 e0 e e4 e e6 E e8 e9 F e e e e5 C D H () G. () G. () G. (4) G. (5) G. ( ) () G, {e 7, e 8 }, {e 0, e }, {e 0, e, e, e }. () G, {e 7, e 8 }, {e 0, e }, {e 0, e, e, e }. ( ) ( ). () G e 9. (4) G {B, D, E}. (5) G E, F. 7

72 4.4 (004 4 ),,,,.,,,,. G (tie-set matrix) B, G L i, j j E(G), b ij { (L i j ) b ij = (4.) 0 ( )., G (cut-set matrix) C, i G C i, j j E(G), c ij = { (Ci j ) 0 ( ) (4.)., 4.76 G,, ( ) B =, C = (4.) () 4.77 G ( L,L, ). () G ( C,C, ). () G B. (4) G C. () B C. BC T 0 (mod ) (4.4), C T C, 0. ( ) () () () L,L,L,,,, 5 7

73 a C a C b L c 6 L 4 5 d C b c d e C5 C6 e C4 4.76: G ( ) ( ). a b d 4 5 c 4.77: G. B B = (4.5) 0. (4) C,C,,C 6,,,, 6, C C = (4.6) (5) BC T BC T =

74 a C C5 b L L d C 4 5 L C4 C c C6 4.78:, L,L,L,, C,C,,C 6. = = (mod ),. 4.5 (005 4 ). K,, K. q,,., ( ) R q,... () e, e. () e, e. ( )., ( ), ( ), ( ) 4.79.,,,.,,,, ( q),q( q), R., q R R(q) = ( q) +q( q) (4.7) ()() 4.8,, , e L,L, e, L,L e L. 4.8 e,e, {e, e }, G G,, G +G, {e, e } G +G,, G 74

75 a b c a a a b c b c b c a a a b c b c b c a b c 4.79:.,,,,.,,,. R q 4.80: R q., e {e,e }, G G +G,, G. 75

76 L e L L 4.8: e, L,L, e, L,L e L. C G e e C G e G C 4.8: e,, e,e, {e, e }, {e, e }, {e,e }. 4.6 (004 II(B)#) G G. p.,. k, ( ) p k.,., : R(G) = k p k, p. ( ) k =0,,, 4.8 (k =, 4 )., p k p 0 = ( p) 4 (4.8) 76

77 k=0 4 k= 4 4 k= 4 4.8:. p = p( p) (4.9) p = 4p ( p) (4.0) p = 0, p 4 = 0 (4.), R(G) R(G) = 4 p k =( p) 4 +p( p) +4p ( p) (4.) k=0. p R(G) 0.8 (-p) 4 + p(-p) + 4p (-p) p 4.84: : R(G) =( p) 4 +p( p) +4p ( p) 77

78 4.7 (006 4 ) G G : G = G + G : V (G) =V (G ) V (G ),, : E(G) = E(G ) E(G ) {uv u V (G ) v V (G )}.. () K K. () n V i (i =,,n), G n, n,,, n, K p,p,,p n (p i = V i )., K p,p,,p n = K p + K p + + K pn (4.)., G G. (, K,,.) ( ) () K, K,,. K + K, K, K,, K K, K K 4.85: K K. (), K,, K,, = K + K + K (4.4),,., 4.86( ) A,B,C. K,,.,,, A,B,C, u A (, u A V (A) ), (4.4) : E(K + K + K ) = {u A u B u A V (A) u B V (B) } {u B u C u B V (B) u C V (C) } {u C u A u C V (C) u A V (A) } (4.5) 78

79 A group B group K A K B C group K,, K C 4.86: K,, ( ) K + K + K ( )., 4.86( ), K,,. n. K pi K pi p i, V (i), : K p + K pn n V (i),v(j), n K p,,p n.,. 4.8 (004 II(B) #) u v. u v,.,,. ( ) 4.87 A H. x l(x), A 4 D G 4 4 u C F v B E H 4.87:.. 79

80 l(u) = 0 l(a) = l(u)+= l(b) = l(u)+= l(c) = min{l(u)+, l(a)+, l(b)+ } = min{,, 5} = l(d) = min{l(a)+ 4,l(C)+ } = min{5, } = l(e) = min{l(c)+ 4,l(B)+ } = min{6, 5} = 5 l(f) = min{l(d)+ 4,l(F)+ 5} = min{7, 0} = 7 l(g) = min{l(d)+,l(f)+ 4} = min{6, } = 6 l(h) = min{l(f)+,l(e)+ } = min{9, 6} = 6 l(v) = min{l(g)+,l(h)+ 5,l(F)+ } = min{9,, 0} = 9., u A C D G v, (005 II(B) #) G n =k.. () k = G m m + ( m), m + G. () G k (m m + = k ). :. ( ) () k =, n = =6., G 4.88( ), m + =9= = k, 4.88, : k =,n =k =6 ( ). K, ( ). (). k =, n = =,k ==m + ( G )., k., n =k, m m + = k m + (k). 80

81 , (),, K s,t s + t, s t, s = t = k n =k, k, ( 4.88( ) ). K k,k (A,B ), A ( m ), B ( m ). A,B ( ) k +=(k +), m + (k +) = k +k +=(k +) (4.6),,, k +., G k. 4.0 (006 II(B) #) n, m.. () : m> n C. () n> m = n C. ( ) () n, k., n,, k =., n K n, n C. K n, m. m n C + (4.7). m. m > n C (4.8), m> n C. () n =4, K ( ). C =. 8

82 4. (007 4 ) () G, : deg(u) =ɛ(g) u V (G). () G, G. ( ) () G V (G), : V odd = {u deg(u) }, V even = {u deg(u) }., ɛ(g) = deg(u)+ deg(u) (4.9) u V odd u V even,, ɛ(g) u V even deg(u)., u V odd deg(u), deg(u),,,., G,. () G n., G, G n.,, n, 0,,,,n, 0 n G., G, G. 8

83 (Eulerian graph) :. (semi-eulerian graph) : ( ). Eulerian graph Semi-Eulerian graph 5.89: ( ) ( ). 6. G G. ( ) ( ) G P,,,,. ( ),,, p. 4 6., G C., G.,.,, C G,.,,., 5.90 G C (, ) H. G, H C.,, C, C., H, H (C

84 H H C 5.90: G C H. C,., H.,,, H ),, C, C,,, ( ) () n K n? () K s,t? () n W n? ( ) () K n n, n =, K n.,, K 5, K 4. () 5.9, s,, t, a b a b 4 a 5 b, a, b ( t,,. t =6 )., s, K s,t. K,5 4 5 a b 5.9: K,5.,. () n, C n ( ), 84

85 ., 6.,,.,,. 7 a,b,c,d,e,f,g,.. a b c d e f g ,?, ( ).,,.?, Fleury ( ). p. 45,,,, ( 6.). Fleury,. (),. (),. 5.. (Hamiltonian graph) :. (Hamiltonian cycle) : G. (semi-hamiltonian graph) : ( ). Ore ( ). 85

86 7. (Ore ( ) ) G n( ). v, w deg(v) + deg(w) n (5.0) G. ( ). G (5.0),. G ( ), G : v v v v n.,, v v n, G, v v n., v,v n (5.0) ( ), deg(v ) + deg(v n ) n., v,v n (n =, deg(v )=, deg(v n )=,,, ), v i v, v i v n v i,v i ( 5.9 )., v vn v v i- vi v n- 5.9: Ore. G v v v i v n v i v,. ( ) 0. Ore. 5. (00 #4 ) G n, (n )(n )/+., Ore, G. ( ) n K n (n )(n )/,, G K n v n, v K n w, x 5.9., 0., (5.0)

87 x K n- w v 5.9: K n v w, x G. n, (n )(n )/+. (n )(n )/+,., K n,, K n u ( w, x) v, deg(u ) + deg(v) = n +=n (5.), Ore., K n, v K n, deg(v) =, z deg(z) =n, deg(v) + deg(z) =n, Ore., Ore,, n (n )(n )/+ G. 5. (004 5 ). (). () (), Fleury,.., v,, v. () 5.94( ). (),. () ( ) Groetzsch. ( )., Fleury,. () a g 5.95( ). () Fleury,. 5.95( )..() 5.96, v =4, v,v,v 5,v 7,v 8,v 9 6,., (, 87

88 5 7 v : ( ). Groetzsch. a a b g b 0 g c c d e f 4 d 9 e 8 f 5.95: ( ) ( ) ) , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

89 5 7 v : : , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

90 , 44 ( ),,. () , 6., v 5.98:.,,, v v v., 5.98, 8, 9, 0,., 8,., 5.98.,,,,,,? , v 6 v :. 4., 4, 5.99 ( ) 4,,.,, 4. (),,,,.,, Ore ( deg(7) + deg(0) = + 4 = 7 < ),

91 :. 5.4 (005 5 ). G, G... ( ). n =4 5.0( ),. n =6 n=6 n=4 5.0: n =4 ( ). n =6 ( ) ( ).. 5.0( ),.,., n 5.0 n =7,,,,., 9

92 n=7 5.0: n =7...,, ( 5.0 )..,, ( 5.0 ) :, ( ). ( ).., ( ) 5.0( ),4,6, 5.0( ).,,4,6,5,,,4,5,, 6,, 5., 4, 9, 9 8, {0,, },, 9 8 {6, 7, 8}.,.,,,, {,, 4, 5, 6, },. Ore, Ore,,,, Ore,.,,.. 9

93 ,,,,, ( ). ( ).., 5.04, 5, C. C a 5 b 0 e c 7 8 d :., a, b, c, d,, e 5,, 4,,, C ( ) + ( ) + (4 ) + ( ) + ( ) = 5 ( ),, C 5 5 = 0 ( ).,, 0, 5.04,. 5.5 (006 5 ) G, S G k., G S (G S ) k. ( ), C, K s,s (s =,, )., G 5.05., G k S G, k, G S ( 5.06 )., G S. S S k, G S., C k ( l = k/), C G S. 5.07( ),, 4,..., l l, l 9

94 G C 5.05:. C. k= S 5.06: S. G, G S. S k, G S k,. G C,, 5.07( ), G S,.,. 5.6 (005 II(B) #) K,K 5,K 7, K 9 Ore,,.,, K k+ (k ) ( ). ( ),, K n. K n n, n +n =n n (n ), Ore, Ore : deg(v) + deg(u) n u, v,,., Ore. v f(n), deg(v) f(n)., f(n) n., u, deg(u) f(n). deg(v) + deg(u) f(n), 94

95 : S, S =4. G S 4.,,, ( ). Ore, f(n) =n,, f(n) =n/., Ore. deg(v) n (5.),. Dirac ( ). n, n.,.., n ( )., K n ( 5.08 )., v, v, v. v, v. v v, 4 v. v (n )/ ( v.,, ), n =k + (k + )/ =k,, K k+ k K,K 5,, K 7.,, k +,, ( 5.09 )., k k + k., M(K k+ ) { k (k + ) M(K k+ ) = k k (k +, k ) (5.). 95

96 K K5 K7 5.08: K,K 5,K 6. NG! K9 5.09: K 9. 9,. 5.7 (005 II(B) #). ( ) 5.0., u,u,,u 5 5 (g )., ( g ) (v ), g, v, g g ( A ), v, g, g, g v, g g 4 ( B ).,,. ( A) g g v u e., v u,e. () e = u 4 v 4, v u u u 5 u u 4 v 4., v,v,v 5. () e = u v, v u u 4 u u 5 u v., v,v 4,v 5. 96

97 v u v5 u5 u v u4 u v4 v 5.0:.. ()() v., ( A). ( B) g g 4 {v u, v u, v u, v 4 u 4 }., v 5 u 5., C.,,, C v v 5, v 5 v 4., u 4, u 4 u C., u 4 u, u ( v ),., v 4 u, u v, u u 5 C., u 5 u 5 u, C., ( B).,,,. 5.8 (006 II(B) #) n, m.. ( ) (= ) ( ) 4( ) 5. (, ), +4 ( ) =6, +4=7,,. 4,.,,.,,. 97

98 5.: (007 5 ). : D =(d,d,,d n ), d d d n, D. D, : n i= d i, k =,,,n k d i k(k ) + i= n i=k+,,., : min(a, b) a, b. : D =(,,, ) D =(4,,,, ) D =(7, 6, 6, 6, 5, 5,, ) min(k,d i ) (5.4). (.,. (5/8).). K m K n m, K m K m C m,n. (n>m, K m K m.) C m,n ε(c m,n ) m, n. ε(c m,n ) m n, n. ( )..7 G,.,,., G. D =(,,, ). d =,d = 98

99 ,d =,d 4 =, 4 i= d i =8., k = i =,, 4 min{,d i } = d = ( )+++= i=,. k =,, 4 d i =5 ( )++=5 i= d i =7 ( ) + = 7 i= 4 d i =8 4 (4 ) = i=, k., D =(,,, ). 5.. V V V 5.: D =(,,, )., V = k, V = n k., V =,,.,. 5. V = k, V = n k., k i= d i V, V., 5., V k i= d i V, V V. ε, ε. V ε,ε, ε k d i = ε + ε (5.5) i=. V V, ε k C = k(k )/., (5.5) k d i k(k ) + ε (5.6) i=. ε, V V V ( i ) V k, V i d i,, i min{k, d i }., ε i min{k, d i } 99

100 i = k + n n i=k+ min{k, d i}. (5.6) k d i k(k ) + i= n i=k+ min{k, d i } (5.7), G : n i= d i =ε(g) =. Erdös-Gallai. D,D. D = (4,,,, ), d =4,d =,d =,d 4 =,d 5 =, 5 i= d i =6. k = d i =4 +++=4 i= d i =7 ( )+++=7 i= d i =0 ( )++= i= 4 d i = 4 (4 ) + = 5 i= 5 d i =6 5 (5 ) = 0 i=, k. D : D =(4,,,, ). D =(7, 6, 6, 6, 5, 5,, ). d =7,d =6,d =6,d 4 =6,d 5 =5,d 6 =5,d 7 =,d 8 =, 8 i= d i =8., k = d i = =7 i= d i = ( )++++++= i=.. 00

101 d i =9 ( )+++++=8 i= 4 d i =5 4 (4 )+4+4++= i= 5 d i =0 5 (5 )+5++=8 i= 6 d i =5 6 (6 )++= i= 7 d i =7 7 (7 ) + = 4 i= 8 d i =8 8 (8 7) = 56 i=, k =, 4, 5, 6. D... C m,n ε(c m,n ) = m m(m ) (n m)(n m ) + + m(n m)+ = { m + ( )} n ( ) 6 n n(n ) + (5.8), ε(c m,n ) m m = n 6 (5.9), n(n )/ /4., m, n, n m (5.9). G, D ( )., ( ε,ε ),, D. 0

102

103 0 6 6.,, /,,, (Cayley ( ) (forest) :. (tree) :., 6.4,. 6.4:... p.6,.. 9. n T,. (i) T. (ii) T, n. (iii) T, n. (iv) T,. (v) T. (vi) T,,,., (ii)(iii), G.

104 9. G n k., G n k. ( ), n., n, n 4, n 4 k k, n k. ( )., 9. (ii). 9.,. ( ) T:V (T) = {v,v,,v p }, p, E(T) = {e,e,,e q }, 9.(ii) q = p, ( ) : p deg(v i ) = q p deg(v i ) = (p ) i= i=., 0,,,. ( ). 6.. (spanning tree) : G, ( 6.5 ). (spanning forest) : n m, k, G,. 04

105 v e6 w v w e e e e8 e4 e e e e4 e5 e7 x y z x y z 6.5:. (cycle rank) γ(g) :. γ(g) = (G ) (n, k G ) = m (n k)( 9. ) =m n + k (cutset rank) ξ(g) : ξ(g) = n k, γ(g) ξ(g) γ(g) + ξ(g) = m. 6.. T :T G T,. ( 6.6( ) ). v w e e e e4 v w v w e e e e4 e e8 e e4 x y z x y z y z v w V v e e v e e v e6 e w e4 V e {e,e5} x e5 y y e7 z z x e5 y z 6.6: ( ) ). T : T ( 05

106 6.6( ) ). 6. (004 6 ) G, G (centre) v : v G.,. T (), T. (). (),. (4) 7,,. ( ) () T,, {,, 4, 5, 8, 9,,, 5, 6}, {, 6, 0, 4, 7}., {7, 8}., T. ()., 9. (iv),,, 6.7., v. 6.7:. (I),. 06

107 (II) (I), v, v. (II),, v, (v, )., (I)(II),,,,. (),,, 9. (iv),,, v ( 6.8 ).,, v, v 6.8:..,,. (4) 7, : 7 ( ). 6. (005 6 ) (). a b e d c () G C. C, C. ( ) () 6.0, I:{,, }, II : {4, 5, 6} 07

108 ,,., a b d 6 e 4 5 c 6.0:. =9. A:(,4), B : (,5), C : (,6), D : (,4), E : (,5), F : (,6), G : (,4), H : (,5), I : (,6), 6.. A B C D E F G H I 6.:. () 6.( )., e ( a e e c b e e 6.: G( ) ( ). ),,.,,, 6.( ), e.,. 08

109 6. (006 6 ) T,T G.,. () e T, T e f (T {e}) {f}, T f. () (), T T., T T,. ( ) () 6. G T,T., G T 4 5 T : G T,T. T e, T f 5 ( e =,f =5 ), T e, T f : ( ) G. T {e} {f} G ( 6.4 t )., T,T g ( G,, 5 C = 5., g ), T f = C = 5 f, 5(= g), T g =5 f T g =5 e G., T,,, 5, e. G, G. () 6. T,T e =,f = t = T {e} {f}, t e =,f =5 t = t {e} {f} T, T. 6.4., : T T t G. 09

110 t t : T e =,f =5 t t e =,f =4 t. t T., t,t G. 6.4 (005 II(B) #) γ(g), ξ(g). () K 5 () K, () W 5 (4) N 5 (5) ( ). () γ(k 5 )=6,ξ(K 5 ) = 4 () γ(k, )=5,ξ(K, ) = 4 () γ(w 5 )=5,ξ(W 5 ) = 5, (4) γ(n 5 )=0,ξ(N 5 ) = 0 (5) γ( ) =6,ξ( ) = (007 6 ) (). () G ε G., G, ε G + () G,, G. ( ) () + G = 0, ε =5. :, 68, 70, 49, 80, : ( ). 0

111 () (), 45, , , , , , (),.,., (), 6, ε G +=5 0 + = 6. G, ɛ, G G,, G, ε ( G ) = ε G +,,, ε G +.

112

113 7 6..4,,,. Cayley ( ), n n n,. ( ),,,,. 0. (Cayley ) n n n. ( ) deg(v) =k v A deg(v) =k v B. A B (linkage) B A ( ),. :A B,, :B A., n v k T (n, k). : A B 6.6 A v ( 6.6 (a) (b)), v z ( 6.6 (b) (c)), deg(v) =k B., A (a) (b) v z v z cut (c) v z 6.6: :A B.

114 T (n, k ), A, ( v ) = ( A ) ( v ) = (n ) (k ) = n k ( ), :A B ( :A B ) = T (n, k )(n k). :B A. : B A 6.7, B v,,, B (T, T,, T k ) ( 6.7 (a)). n i, n (v ) = k i= n i., B v,, ( (a) w,t (b) w,t cut v v w,t w,t w,t w,t (c) w,t v w,t w,t 6.7: :B A. T i )( 6.7 (a) (b)), T i T j u T i w i ( 6.7 (b) (c)) deg(v) =k A. B T (n, k), w i T i T j ( v ) ( T i ) = (n ) n i ( ), :B A k T (n, k) (n n i ) = T (n, k){(n n )+(n n )+ +(n n k )} i= = T (n, k){(n )k (n + n + + n k )} = T (n, k)(n )(k ) 4

115 . :A B, B A, : (n k)t (n, k ) = (n )(k )T (n, k)., T (n, n ) =, k = n,n,n, k = n T (n, n ) = (n )(n )T (n, n ) = (n )(n ) k = n T (n, n ) = (n )(n )T (n, n ) = (n ) (n )(n ) T (n, n ) = (n ) (n )(n ) k = n T (n, n 4) = (n )(n 4)T (n, n ) = (n ) (n )(n )(n 4) T (n, n 4) = (n ) (n )(n )(n 4)., k = k + T (n, k) = (n )n k+ (n ) (k )(k ) = n C k (n ) n k., T (n) T (n, k), k = k = n T (n) = = = n T (n, k) k= n n C k (n ) n k k= n n C k k (n ) (n ) (k ) = {(n ) + } n = n n k=, Cayley. ( ).. 5

116 7. (00 #5 ) n T (n).. () k n k. (n )T (n) = n nc k k(n k)t (k)t (n k) k= (). ( ) n nc k k k (n k) n k =(n )n n k= () n, A, B (n ) T (n) = (n )T (n) (6.40)., T (n) n, (n ),, A, B., k A (n k) B, k kt(k) n k (n k)t (n k), n k (k =,,,n ) A, B n nc k kt(k)(n k)t (n k) = k= n nc k k(n k)t (k)t (n k) (6.4) k=. (6.40)(6.4) (n )T (n) = n nc k k(n k)t (k)t (n k) (6.4) k=. () (6.4), Cayley : T (n) =n n (n )n n = n n nc k k(n k)k k (n k) n k = nc k k k (n k) n k (6.4) k= k=. Cayley. 0. K n n n. 6

117 ( ) K n,, n ( ),, n, n, K n (, 6.8 K 5 )., n K n,, K n n n. ( ). K 5 6.8: K (matrix-tree theorem), G., G (vertex matrix) D 4. G D, D ij { v i D ij = ( v i v j ) (i = j ) (i j )., G τ(g) D., D i, j D(i, j) τ(g) = ( ) i+j D(i, j)., X X., D N N, i = j = N, τ(g) = D(N,N)..,. 4, 5.,. 7

118 7. A A = G τ(g).,. ( ) A G 6.9( ). G D, 6.9: G( ) ( ). D =, i = j =, G τ(g) τ(g) = =4 = ( ). 6.9( ). 8

119 7. (004 7 ). Cayley,. () n, v? () n v P (n)., n P (n) lim n P (n) = e., e.. A A = G. () G D. (), G τ(g). () (). ( ).() Cayley : T (n, k) = n C k (n ) n k (6.44)., n, v k, v k =., T (n, ) = n C 0 (n ) n =(n ) n (6.45). () P (n) n n n T (n, ) P (n) = n ( T (n, ) n n = n) (6.46). () e lim P (n) n = ( lim n ( = lim n n) ) n = n n e (6.47),. 9

120 ( ) P (n) : ( lim ) n = n n e (6.48), P (n) : ( lim log n ( = lim n n) n log ) n n (6.49) (6.48). (6.49) ( lim n =, lim log ) = 0 (6.50) n n n, 0, log( /n) (/n) ( log ) = n n ( ) n + O n (6.5), ( n log ) n = ( ) n + O n (6.5), (6.49) ( lim log n = (6.5) n n)., n log /e, (6.48)..() A G 6.0., D G 4 6.0: A G. D = (6.54). 0

121 () i = j =4, G τ(g) τ(g) = ( ) =( ) = + =7( ) (6.55). () G : A G., 4, 4, 4 4, 7. ( ) A D, δ. δ δ ij { deg(v i ) (i = j ) δ ij = 0 (i j ) (6.56),, A, D D = δ A (6.57). G,. ( ),,,,.,., R ij R 5. { c i (i = j) R ij = (6.58) ± ( c i c j ) (i j) c i c j,,., R G τ(g) τ(g) = R (6.59), R., 7. ( 6.0 G),. 5 6.

122 , G c,c,, c = 4,c = 4., G R ( ) 4 R = (6.60)., G τ(g) τ(g) = 4 = 7 (6.6),,, 7..()., G,,? G,.,,. 6. G,,, c = 45,c = 45,c =., R G c c 5 c 4 6.: G. R = 0 0 (6.6) 0 0., G 0 τ(g) = 0 = 0 0 = 8 = 4 (6.6).,, 5, D 5 5, D = 0 (6.64) 0 0

123 , D 5 5 G 0 τ(g) = ( ) (6.65) 0.,,., τ(g) = { } { } = ( ) + 0 { } 0 + ( ) ={ 8 } + { 8 } + { 5} =4 (6.66),.,. 7.4 (005 7 ) Cayley. ( ), K n, m m. a a + a (a +) a b m a = 0 a =(a +)b m +(a +)c m a 0 a (6.67),, c m. 0 a (a +) a c m a = 0 a =(+a) c m (6.68) a 0 a, b m b m,c m. { b m = (a +)b m +(a +)c m c m = (a +)c m (6.69)

124 c m, c m =(a +) m c, b m, b m b m = (a +) m b +(m )(a +) m c (6.70). (6.70). K 5, K D K5 = 4 5, D K6 = (6.7) , K n, (6.70) m = n,a= n,b = a, c = (6.7), τ(k n )=b n = n n (6.7). K n n,,. 7.5 (006 7 ) K n e K n e τ(k n e) τ(k n e) = (n )n n. [ ]. 7.4 b m,c m. ( ), 6. K 5., 6. D K5 e = (6.74) (,, )., 4

125 5 4 6.: K 5 e. e. D Kn e = a 0 0 a a a (6.75).,,. 7.4 τ(k n e) = ( ) N+N D Kn e(n,n ) a 0 0 a a = a a a a = (a ) a 0 a a + (a ) a m m = a 0 (a ) a a a (m ) (m ) (m ) (m ) m m 5

126 = (a ) + (a ) a (a +) a 0 a a (a +) a 0 a a (m ) (m ) (m ) (m ) = (a ){ab m +(a +)c m } +(a ){b m +(a +)c m } = (a )(a + )(b m +c m ) (6.76)., b m,c m 7.4, { bm = (a +)b m +(a +)c m c m = (a +)c m (6.77). { c m = (a +) m c b m = (a +) m b +(m )(a +) m c (6.78) :, b m,c m (6.76) m = n,a= n,b = a, c = (6.79) τ(k n e) = n(n ){(a +) m b +(m )(a +) m c +(a +) m c } = n(n )(a +) m {b + c (m )} = n(n )n n 4 =(n )n n (6.80).. 6

127 7.6 (006 II(B) #) () H k. H, G. G, n, m, G, H τ(g),τ(h) τ(h) =k n τ(g). () F G k. τ(f )=k m n+ τ(g). () () K,n τ(k,n )=n n. ( ) () H G k, k, G n, k n. G, H τ(h) = k n τ(g) (6.8). () G G F k,,, G, F G., G F., F k, G k, G m (n ), τ(f ) = k m n+ τ(g) (6.8). () n G.. F. : G F n, K,n ( 6.4 )., () τ(g) =n τ(k,n ) = τ(f )= n + τ(g) = n n (6.8). 7

128 6.4: F ( ) K,n ( ). 7.7 (006 II(B) #) n w n w n 4w n +4w n w n =0, w n. ( ) n D n D = n n (6.84)., w n = D(, ) w n = a n +b n (6.85)., a n, a n = =a n a n (6.86) b n, b n = = a n + b n + a n (6.87) n n n n 8

129 , b n + a n b + a, 0 b n + a n = b + a = + 0 = (6.88)., (6.85)(6.86)(6.88) w n,., α =(+ 5)/,β =( 5)/ w n = α n + β n =(α n + β n ) (α n + β n ) + = w n w n + (6.89), n n + w n 4w n +4w n w n = 0 (6.90) (004 II(B) #) 6.5 G,. () G T., T. () () m. () T ()., m. (4) () C,C,,C m,, τ(g) : G. ( ) () 5 () m =4 () 4 C,C,C,C

130 5 C C C4 4 C 4 6.6:.,. (4) G R () R = (6.9), τ(g) τ(g) = G = ( ) { } = 4 ( ) = 64 ( ) (6.9). 0

131 7.9 (004 II(B) #) 6.7 k, k k n T k (n). 6.7 T ().,. () T (n) S (n)., T (n) Q (n), P (n) =Q (n)/s (n), :. p = lim n P (n) () (), K P K (n), n :, K : p K = lim n P K(n) p = lim K p K, T K (n) p. ( ) : n,. T () 6.7: T (). ( ) (), S (n), n S (n) = n = n+ (6.9)., T (n) Q (n) T (n) Q (n) = n, P (n) =Q (n)/s (n) P (n) = n n+ (6.94)

132 , p = lim n P (n) = (6.95). () k = K, P K (n) n S K (n) = Kn+ K (6.96) Q K (n) = K n (6.97) P K (n) = (K )Kn K n+ (6.98) p K = lim n P K(n) = K K (6.99) (K = () )., K p K =,,.,., (Caley s tree). 7.0 (005 II(B) #) K m,n. τ(k m,n ) = m n n m ( ) K m,n D (m + n) (m + n). D = n n n m m n (6.00)

133 ,, (, ) : D(, ) = n n n m m n (6.0)., : n 0 0 m n , 0 m n 0 m, (m ) (m ), n n. (6.0),., m (m + n ) (n ) (m + n ),, (m + n ) /m (m ). n m m n m D(, ) = m n... (6.0) n m n m m.., /(m ) (m ) D(, ) = m n n m m 0 n m. 0 n m m n m... n m m (6.04),, i /(m i) (i +) i = i = m D(, ). D(, ) = m n n m m 0 n m m n m n = m n n m m = mn n m (6.05), m n n m.,,.

134 7. (007 7 ) ( ) n ( ) p n. p 0 =0,p = p =.. () p =.. () p 4,. () n n ( ) n + n p n p n. n =,n =4,. (4) x. x n n p n : P (x) = p 0 + p x + p x + + p n x n +., () p n p n,, {P (x)} x n+n ( n + n n n ). P (x) = x + {P (x)} (6.06). (5) (4) (6.06) p n n. ( ) n p n ( n, ).,. () p =, :. (4) 4., , p 4 =5. () ()(),,4 p =,p 4 =5, p p 4 =0., +4= (4) () 7, (), 7, 4, 7,, 4., 4

135 : : 7. 4,. (, 6), (6, ), (, 5), (5, ), (0, 7), (7, 0)., P (x) x n n, {P (x)} x 7 p p 6,p 6 p,p p 5,p 5 p,p 0 p 7,p 7 p 0,p p 4,p 4 p.,,,,.., {P (x)} P (x) ( ), {P (x)} x P (x) ( )., : P (x) = x + {P (x)} (6.07). 5

136 (5) (4) P (x) x p 0 + p x + p x + + p n x n + = x + {p 0 + p x + p x + + p n x n + } (6.08), x. x 0,x,x,x,x 4 p 0 = p 0 (6.09) p = +p p 0 (6.0) p = p 0 p + p (6.) p = p 0 p +p p (6.) p 4 = p 0 p 4 +p p + p (6.), p 0 =0(,., ),,, p = p =,p =,p 4 =5.., (6.08) x, (6.08) P (x) P (x) = ± 4x (6.4), P (x) x, x 4x 4x = x i= i k= (k ) i! i (4x) i (6.5), (, ), (6.4) P (x) =( 4x)/. P (x) = x + i= i= i i k= (k ) P (x) = x + x i = i! i k= (k ) i! i (4x) i (6.6) i= i (i )!! x i (6.7) i!., (i )!! = (i )(i 5) 5, ( )!! =. n, i = n. p n = n (n )!! n! (6.8),, p = ( )!!/! =,p = ()!!/! =,p =!!/! =,p 4 = 4 5!!/4! = 5,. n =7? (6.8) n =7 p 7 = 7!! 7! = = = (6.9) 6

137 . n = n =4 p p 4 =0, 7, 7,, 0/., (6.8). n n (n )!! n!., (n )!! = (n )(n 5), ( )!! =..8,,,.. 7

138

139 9 8 8.,,.,,,. 8.. (planar graph) :, ( 8.4 ). 8.4:.,. (face) : 8.4, f 4 (infinite face). f f f5 f4 f f8 f7 f6 8.4: 8., f 4. G n, m, f,, G,? ( ).

140 . ( ) G,. n m + f = (8.0) ( ) m. m =0, n =,,, f =. n m + f = 0+=,., m 0. m G (8.0)., m (8.0). G, m, m = n, f =( ), (8.0) n m + f = n (n ) + =, m., G. G,,, f f f5 f4 f8 f f7 f6 cut 8.4:,,., : n =9,m= 5,f =8, =, : n =9,m =4,f =7, =., (, 8.4 ) n n m m f f, m (8.0),, (8.0) n (m ) + f = 40

141 , n m + f =, m,. ( ).,. 8.,. () K 4 () K 5 () K, ( ),. f, f G,.,.,,.,,.,, G. κ : G. d(f ): G F., G F,. κ d(f ) (8.), K (, ), κ κ =., K : K 4. κf d(f )=m (8.) F F (G)., F (G) G,. f κ( n + m) m (8.) 4

142 , G, m (,, ) m κ(n ) κ (8.4).,. () K 4 :, n =4,m = 4 C =6,κ =, (8.) 6 (4 ) = 6 (8.5)., K 4. () K 5 :, n =5,m = 5 C = 0, κ =, (8.) 0 (5 ) = 9 (8.6),., K 5. () K, :, n =6,m = =9,κ =4, (8.) 9 4 (6 ) 4 = 8 (8.7),., K,. G., G, k,.. G, n, m, f, k n m + f = k + (8.8). ( ) G k, k, f (k ), n m + {f (k )} = (8.9) 4

143 ,,. ( ). n m + f = k + (8.0).4 () G, n( ) m m n 6 (8.). (), G m n 4 (8.). ( ) () G,,, d(f ) (8.)., f F F (G) d(f )=m (8.4), : f = n + m, f :. m n 6 (8.5) (), G 4, 4 d(f ) (8.6)., 4f F F (G) d(f )=m (8.7), f, m n 4 (8.8). ( )

144 ( ) G v δ deg(v) (8.9),.4() δn deg(v) =m (n 6) = 6n (8.40) v V (G) δ 6 n (8.4),, δ δ 5 (8.4). ( ) ,,,,.,. (crossing number) cr(g) : G,. (thickness) t(g) : G. 8. (00 II(B) #) r s. ( ) cr(k r,s ) rs(r )(s ) ( ),,. 8.45( ).,, 8.45( ). Y v,v,,v s/, X w,w,,w r/., v s/ w,w,,w r/, v s/ w,w,,w r/ q q = ( r ) ( r ) ( r ( r )) (8.4)

145 Y v s/ v s/- v s/- s/- w w w r/ r/- r/- X r/- 8.45: ( ). r = s =4.. v s/ w,w,,w r/ v s/ w,w,,w r/ v s/ w,w,,w r/ q. q ( r ) ( r ) ( r ( r )) q = (8.44) q =, v q s/ q s/ = ( r ) ( r ) ( r ( r )) (8.45) ( s )( r ) ( s )( r ) ( s )( r ( r )) ( s ) (8.46)., Q Q = q + q + + q s/ ( r ) ( r ) ( r ( r )) = ( r ) ( r ) ( r ( r )) ( r ) ( r ) ( r ( r )) ( s )( r ) ( s )( r ) ( s )( r ( r )) ( s ) p + p + + p s/ (8.47). p ( r ) ( r ) ( s )( r ) = ( r ) s/ k= k = ( r ) s ( s ) = s ( r )( s ) 4 (8.48) 45

146 p ( r ) ( r ) ( s )( r ) = ( r ) s/ k= k = s ( r )( s ) 4 (8.49) p s/ = s/ k= k = s 4 ( s ) (8.50). Q Q = p + p + + p s/ = s ( s )( r ) 4 + s ( s )( r ) s ( s ){ r ( r )} 4 + s ( s ) 4 = s ( s ) r/ 4 ( r ) k k= = s ( s ) r/ r 4 s ( s ) r/ 4 k k= k= = s ( s ) r ( r ) 4 s ( s ) r ( r ) 4 = sr ( s )( r ) { 8 = } sr ( s )( r ) 6 = sr (s )(r ) (8.5) 6 4,, 4 Q total. K r,s Q total = 4 Q = sr (s )(r ) (8.5) 6 cr(k r,s ) rs(r )(s ) (8.5) 6., K r,s rs(r )(s )/6. 8. G n( ),, m, G t(g) : m t(g) (8.54) n 6 m +n 7 t(g) (8.55) n 6 a. a x x. x x. ( ),.4 () m t(g) = n 6. (8.56) 46

147 , a, b : a (a + b ) = b b (8.57), a = m, b =n 6 (8.55). : a/b = (a + b )/b a, b : a (a + b ) = (8.58) b b. (a/b). (i) (a/b) a/b = M ( ) = a b = M (8.59)., (a + b ) ( ) = = b, (i). a b + a = b b += M +=M (8.60) b b (ii) (a/b) a/b C, D a ( ) = = C + (8.6) b. (a + b ) ( ) = = b, D a/b a b + a = b b += C + D + (8.6) b b D = a bc b, a, b, C, a bc, a>bc (8.6) a bc (8.64). D > b (8.65), D (/b) =ε (0 ε<) ( ) = C + ε +=C + (8.66) 47

148 , (ii). a b = (a + b ) b (8.67). ( ) 8.4 (00 #6 ) () K n t(k n ). t(k n ) (n +7) 6 (8.68) () K r,s t(k r,s ). rs t(k r,s ) (8.69) (r + s) 4 ( ) () K n n(n )/, : m +n 7 t(g) n 6 (8.70) t(k n ) n(n ) +n 7 n 6 = n +5n 4 = (n 6) n +7 6 (8.7),. () K r,s, A r, B s, A B, m n m = rs (8.7) n = r + s (8.7)., K r,s, K r,s m n 4 m 0 (8.74)., K r,s t(k r,s ) m m rs t(k r,s ) = = n 4 (r + s) 4 m 0 (8.75),. 48

149 8.5 (004 8 ). K 4 τ(k 4 ) () G,,,, G m. () (), G K, G m. () () K m,. ( ). 8.46( ) c =, c = 4, c = 4., R c c c : K 4 c, c, c ( ). K 4. R = (8.76).,, 4 4,,,,. 8.46( ) K 4,. 8.46( ), c., 4 c, 4 c,.., 4, ( ).,, (8.76), K 4 τ(k 4 ) τ(k 4 ) = R = = = 6 (8.77) 49

150 , 6.., n, m, κ n =0,m=5,κ=5, : m κ(n ) κ (8.78), 5 5 (0 ) 5 = 40 =... (8.79).,.. (),, d(f )., 6f 6 d(f ) (8.80) F F (G) d(f )=m (8.8), : f = n + m, f, m :. m (n ) (8.8) () K, d(f ) K + d(f ) (8.8)., (K +)f F F (G) d(f )=m (8.84), f = n + m f, m : ( ) K + m (n ) (8.85) K. () (), K., K n, K = n n, K.. ( ) { n + m (n ) = n + + } = n (n ) (8.86) n n 50

151 , K( ), G n ( n, )., n (8.85) K m n, n ( ), n n ( ),, n., K = n n. : K = n n, n K., K n, m n f f 0. f =,. m n f f. f =(K( ) ), f = ) ( 8.47 ). f f f 8.47: f, K( ) (f) (f) f = ( ), (f) f = ( ). 8.6 (005 8 ) ( ) 5 ( ) ( ) (*). () n, m n m. () (*) : ( ) 6 ( ) (**), f f m. () ()(), (**), (*). ( ) 5

152 () 8.48, v., G n v 8.48:., m n,,,, m n/, n m (8.87). (), F 6 ( 8.49 ), G f f f F f6 f4 f5 8.49: F 6. f, m 6f.,,, m 6f/=f, f m (8.88). () ()() = n m + f m m + m = 0 (8.89), 0,.,, (006 8 ) 4 G 8. 5

153 ( ), 4 4n = v V (G) deg(v) =m (8.90).. (8.90) : n =+m f n m +8 = 4f (8.9).,, k ϕ k, ϕ k (8.9)., (8.9) m, f ϕ k, f = ϕ k (8.9) k= m = k= kϕ k (8.9) ((8.9) m,. m, m!)., (8.9)(8.9) (8.9), ϕ +4ϕ 4 +5ϕ 5 +6ϕ 6 +7ϕ = 4ϕ +4ϕ 4 +4ϕ 5 +4ϕ 6 +4ϕ 6 +4ϕ 7 + (8.94), ϕ (ϕ 5 +ϕ 6 +ϕ 7 + ) = 8 (8.95) ϕ (ϕ 5 +ϕ 6 +ϕ 7 + ) 8 = 0 ϕ 8 (8.96) ϕ ϕ 8,

154 8.8 (004 II(B) #) G ( : n 4). G k n k () G m m =n 6. () : n +n 4 + n 5 n 7 n 8 =. () G 5 4. G, ϕ k k. (4) G m, f m +6=f. (5) : ϕ +ϕ 4 + ϕ 5 ϕ 7 ϕ 8 =. (6) G 5 4. ( ) (),, f, m f = m (8.97). : n m + f = f m = n 6 (8.98). () (8.98) n = n k (8.99) k= m = k= kn k (8.00) 54

155 k= kn k = 6 k= n k (8.0), n +4n 4 +5n 5 +6n 6 +7n 7 +8n 8 + = 6(n + n 4 + n 5 + n 6 + n 7 + n 8 + ) (8.0) n +n 4 + n 5 n 7 n 8 = (8.0). () () n +n 4 + n 5 n 7 n 8 = 0 n +n 4 + n 5 (8.04) n +n 4 + n 5 (8.05)., (n +n 4 +n 5 ) n +n 4 + n 5, n + n 4 + n 5 (n +n 4 + n 5 ) = 4 (8.06), G 5 4. (4) n =m, n. 6+m = f (8.07) (5) (8.07) f = k= ϕ k (8.08) m = k= kϕ k (8.09),. ϕ +ϕ 4 + ϕ 5 ϕ 7 ϕ 8 = (8.0) (6) () ϕ + ϕ 4 + ϕ 5 (ϕ +ϕ 4 + ϕ 5 ) = 4 (8.), G

156 8.9 (007 8 ) k n k., n +n 4 + n 5 + n 7 +n 8 +n 9 +. ( ) k n k, n n k = n (8.) k=.,, k =., n k k= kn k, kn k = m (8.) k=.,,,, m f m f/, f m (8.4). f : f = n + m n m 6 (8.5), n m (8.)(8.) 4 n k kn k (8.6) k= k=., :. n +n 4 + n 5 + n 7 +n 8 +n 9 + (8.7) 56

157 ,.,,.,.,,,.,,. G. () G f v. G. () G e, e e, e f v. G. a f f4 b f f5 d e c f 8.50: G ( ) K 4,, K 4. ( ),, 8.5,

158 K 4. G G, G G* 8.5: K 4 ( )., n,m,, f G?. 5. G n, m, f., G n, m, f n = f, m = m, f = n. ( ), G n = f, G e e m = m., f = n = +m f (8.8), G n m + f = (8.9), n m + f = n m ++m f =, f = n (8.0). ( ). 5. G, G G G G., G, G, G, G. 58

159 ( ) G C, C,, G v. v C,,, G {c c, c c, c c 4, c 4 c 5, c 5 c 6, c 6 c } G {v a, v b, v c, v d, v e, v f}, G ( 8.5 ). G f c a c6 e v* c b c5 C c4 c d c 8.5: G C, G ( ).,, G v.,. ( ). 5.4 G G, G G., 8.5 G,. G G a 6 f 7 g 8 b e d c 4 8.5: G( ) ( ). {7, 8, 9, 40, 5, 6} G, G {fa, ab, bc, cd, de, ef}, G.. 59

160 ( ) 5. G G,G G, 5., G, G = G, G G, G G, G G.. ( ). 9. (00 #7 ) (). () G, G G. () G, G G. ( ) () W n, n C n v, v n. 5. n = f,,, G C n n,, n n ( G n ), C n, v ( G n), C n n ( G ) Wn,, W : W 7 ( ) (, ). (), 8.55( ) G. G G, 8.55( ). G, G 8.55( ), G (G ). (), G G 8.56., G G G 60

161 G G * G ** G 8.55: G( ) G ( ). G ( ) G ( ). 8.56: G( ) G ( ). G 8.57, 8.57, G.,. 8.57: G ( ) ( ). (abstract dual) :G G,, G G, G G,,, G G. ( ) :G G, G G

162 g* c a b d e f g h a* b* c* e* d* f* h* 8.58: G ( ). g* b* e* f* a* d* c* h* b* e* 8.59: a, c, d ( ) f, g, h ( ). 8.. k- (k-colourable) : k G,. k- (k-chromatic) : G k, (k ). G (chromatic number) k. χ(g) = k., G 4., G β α γ α β χ (G) = : G χ(g) = 4. 6

163 χ(k n ) = n χ(n n ) = χ(k r,s ) =.,,. 7. G Δ, G (Δ + )-. ( ) 8.6, v, v n, Δ., n (Δ + )-. G v 8.6: v., v Δ v, G (Δ + )-. ( ) ( ) G n(> 6)., n : 5, G 5 v. 8.6, v v, 8.6:. n, 6-. v 5 6

164 v, G 6-. ( ) ( ) n>5. n , G 5 v. deg(v) < 5., deg(v) =5. v,,v 5 v ( 8.6 ). v,,v 5 v (v) v v5 v5 v v v v4 v4 v v v5 v v v4 v 8.6:. K 5,. vv,vv,, n, 5-., v v,v. v v G 5. ( ).,. 64

165 9. (00 #8 ).,. ( ). a b c d e f g a b c d e f g ()(). () a, b, c, d, e, f, g 7,. () () α, β, γ,, 7. ( ) (), d(γ) b(δ) e(α) g(γ) a(β) c (α) f (β) 8.64:.. ( ). () 8.64, α, β, γ, δ 4, b,, b 4 b (a, c, d), b δ, δ 4. c, e α 65

166 a, f β d, g γ b δ. 9. (004 9 ). G. G a b c d e () G G. () () G G, G G. ( ) :, #... G. () G., G. () G. () () G K. ( ).() G G () () G G 8.65,,,, 4, 5., {θ, φ} θ : V (G) V (G ) φ : E(G) E(G ), θ(a) =,θ(b) =,θ(c) =,θ(d) =4,θ(e) =5,, φ(ab) =,φ(be) = 5,φ(ed) =54,φ(da) =4,φ(ac) =,φ(ce) =5,φ(bc) =,φ(cd) =4.,, ; Ψ G (ab) =ab Ψ G (φ(ab)) = Ψ G () = = θ(a)θ(b) Ψ G (be) =be Ψ G (φ(be)) = Ψ G (5) = 5 = θ(b)θ(e) Ψ G (ed) =ed Ψ G (φ(ed)) = Ψ G (54) = 54 = θ(e)θ(d) Ψ G (da) =da Ψ G (φ(da)) = Ψ G (4) = 4 = θ(d)θ(a) Ψ G (ac) =ac Ψ G (φ(ac)) = Ψ G () = = θ(a)θ(c) 66

167 G a b G * c d e G ** : G G., G G. Ψ G (ce) =ce Ψ G (φ(ce)) = Ψ G (5) = 5 = θ(c)θ(e) Ψ G (bc) =bc Ψ G (φ(bc)) = Ψ G () = = θ(b)θ(c) Ψ G (cd) =cd Ψ G (φ(cd)) = Ψ G (4) = 4 = θ(c)θ(d)., Ψ G, Ψ G, G G.. () G v δ deg(v), nδ deg(v) =m (8.) v V (G)., G, G κ =4 4 deg(f), 4f =m (8.) f F (G), : f = n + m, f m n 4 (8.). (8.)(8.) nδ m (n 4) (8.4) δ 4 8 n (8.5)., δ, n 8 δ,., G v, deg(v), n deg(v) =m (8.6) v V (G) 67

168 m n (8.7), (8.), n n/ n 4, n 8., δ, G. () (), G,, 8.66 v ( G n)., v deg(v) <, deg(v) =., 8.66 v v,v,v. G v v v v 8.66: G. v v,v,, v., vv (n ) 8.67, (n )., v α, v α, v β α v v β α v (v) 8.67: G vv., v ( n). v α, β v v α v α β γ v 8.68: 8.67 vv. γ G. ( ). () K, (K +)f F F (G) deg(f )=m 68

169 , f ( ) K + m (n ) (8.8) K. nδ m δ ( ) K + 4 K n ( ) K + K (8.9)., G K, n : ( ) K + n 4 K (8.0), G (K +/K )., (8.0), (K +/K ), v, (K +/K ) deg(v), m n {( ) } K + (8.) K, (8.8) {( ) } n K + K ( K + K ) (n ) (8.), n 4 ( ) K + K (8.), (K +/K )., (K +/K ). 9.4 (005 9 ). () () K r,s,t () k- ( ) () p , χ( ) = 4 (8.4) χ( ) = (8.5) χ( ) = (8.6)., 0,, 8.70, 69

170 (a) β (c) β α α α β α δ γ β (b) α α β γ β α β γ 8.69: (A), (B), (C). α (d) (E) α β β γ δ α γ γ β α γ α β β α γ α δ β γ δ β α δ β α γ γ β α β 8.70: (D) 0,, (E). χ( 0 ) = 4, χ( ) = 4 (8.7). () K r,s,t. χ(k r,s,t ) = (8.8) () k- Q k,. χ(q k ) = (8.9) 70

171 9.5 (006 9 ) m G χ(g) : χ(g) + 8m +. ( ) G,,,χ(G),. G m. ( ) G. χ(g), χ(g),.,,,,., G,, m., m χ(g) C.. χ(g) m χ(g)(χ(g) ) (8.40) χ(g) ( + 8m + ) (8.4),. 9.6 (005 II(B) #) χ(g) = k,, G k-.. () -, -. () 4-. () G k-, (a)(b). (a) G k. (b) G. ( ) () -,, K., - K. () 4- K 4. () (a)(b). (a) k-, c,,c k k., k-, c,,c k., c k., (k )- 7

172 ., (k ), (k ). (b) k- G n. n, G A, B., A, B, A n B n, k-. ( k, A, B n k.) A n k-, B k-. B n k., k (007 9 ) Δ(G) G., G χ(g) +Δ(G) (8.4). ( ) G, χ(g) =, Δ(G) =0,. n, n G v, G G v n χ(g v) +Δ(G n) (8.4)., G v +Δ(G n)-. G v +Δ(G n)-, G v Δ(G), G v Δ(G).,, Δ(G v) =Δ(G) (v G ), G v v (χ(g) =χ(g v) +Δ(G v) =+Δ(G))., Δ(G v) < Δ(G) (v G ), G v v, n G χ(g) +Δ(G) (8.44). 7

173 ,,,?,. k- : k β α γ α δ 8.7: G, G. ( ) : G v,v., 6., G, G. : F,. F x, F ( 8.7 ). F ( ) F ( ), x y x (G )

174 F x y F 8.7: - G, x y x G.. ( ). 9. G, G G., G k-, G k G G * 8.7: - G( ), G. G G., G -,. ( ) : 8.74, G F, F G.,,. : G, G, G ( ), G -. G, 9.,, G,. α, β, γ. α, β, γ.,. ( ). 74

175 F 8.74: F G. β B α B γ γ B β α 8.75: G (B) , ( ),. k- : G, G k. :G k-, k -, χ (G) χ (G) = k G : 4-. G χ (G) = 4. 75

176 0. G, Δ, Δ χ (G) Δ+.,,. ( ) : χ (C n ) = { (n : ) (n : ) χ (W n ) = n (n 4) 0. n( ), χ (K n )=n,, χ (K n )=n. ( ) n, n. n : K n n,, ( 8.77 ) : K 5. 5,, 5-., (n )/., n K n (n )χ (K n ) = (n ) n C, K n n C = n(n )/., χ (K n )=n,, (n )χ (K n ) = n(n ) = nc,., n χ (K n )=n. n : K n K n. K n n, n 76

177 ., (n )-, K n n, n,,.,, K n ( 8.7 )., n : K 5 v, K 5 v, n ( n =6) n-., χ (K n )=n. ( ). 0. (00 #9 ) () (). () 8.79 (a)(b). () 5- -, 4. () G. (),. (a) (b) 8.79: (a)(b). ( ) () 8.80, (a)(b) χ ((a)) = 5 (8.45) χ ((b)) = (8.46). 77

178 (a) (b) :. () 8.8, :.. (),,, G χ (G) =, (), P G (k) : G, k P G (k)., P G (k). ( ) : P G (k) = k(k ) ( 8.8( ) G) P G (k) = k(k )(k ) ( 8.8( ) G) P G (k) = k(k ) n ( 8.8( ) n G) P G (k) = k(k )(k ) (k n +) ( K n ) k<χ(g) P G (k) =0 k χ(g) P G (k) > 0. 78

179 k k- k k- k- k k- k- k- k- k- k- 8.8: P G (k) =k(k ),k(k )(k ),k(k ) n. G.. G e G e, a G/e. P G (k) = P G e (k) P G/e (k) (8.47). a, u, v e, u, v.,. ( ) : 8.8, (8.47) k k k k- v w k- = k- v k- w - k- vw k- k- k- G G-e G\e 8.8: (8.47). k(k )(k )(k ) = [k(k )(k ) ] [k(k )(k )]. ( ) : e = vw. G e e, P G e (k) v w G e k- v w G e k-., 79

180 .,,, v w G e k- v w e ( 8.8 G,, G-e )., P G (k).,, v w G e k- v w ( 8.8 G-e G/e )., P G/e (k). P G e (k) = P G (k)+p G/e (k). ( )., G (8.47),, n P G (k) =k(k ) n,,,.. 0. (00 #9 ) 4,, k 4 mk + ak bk., m, a, b. ( ), 4, 8.84 A F 6. A B C D E F 8.84: 4 A F., n =4 A,B 8.85 P A (k) =P B (k) = k(k ) = k 4 k +k k (8.48)., C : P G (k) = P G e (k) P G\e (k) (8.49) 80

181 A k k- k- k- B k k- k- k- 8.85: A,B n =4, k(k ). C, 8.86 C k- k- k k- = - e k k- k- 8.86: C e. P C (k) = k(k ) k(k ) = k 4 4k +5k k (8.50). D e 8.87 D k- k- k k- = - e k k- k- 8.87: D e. P D (k) = k(k ) k(k )(k ) = k 4 4k +6k k (8.5). E, 8.88 D n =, D P D (k) (8.5), P E (k) = P D (k) k(k ) = k 4 4k +6k k (k k + k) =k 4 5k +8k 4k (8.5). F, 8.89 E, E (8.5) 8

182 E D e = - k k- k- 8.88: E e. F E k k- e = - k- 8.89: F e. P F (k) = P E k(k )(k ) = k 4 5k +8k 4k (k k +k) =k 4 6k +k 6k (8.5). P A (k) = k 4 k +k k (8.54) P B (k) = k 4 k +k k (8.55) P C (k) = k 4 4k +5k k (8.56) P D (k) = k 4 4k +6k k (8.57) P E (k) = k 4 5k +8k 4k (8.58) P F (k) = k 4 6k +k 6k (8.59), P G (k) = k 4 mk + ak bk (8.60), m, a, b. 0. (004 0 ),,. () K, P K, (k). () K,s (s : ) P K,s (k). () C 4,, C 5 P C4 (k),p C5 (k). (4), C n P Cn (k) P Cn (k) = (k ) n +( ) n (k ). ( ) 8

183 () K, 8.90( )., a b a k k- k- k- b k- 8.90: K, ( ) ( ).. (i) a b, k(k ). (ii) a b, k(k )(k ) ( 8.90( ) ).,. P K, (k) = k(k ) + k(k )(k ) () K,s s a b 8.9: K,s. s..,, a b /. (i) a b : k(k ) s. (ii) a b : k(k )(k ) s.,. P K,s (k) = k(k ) s + k(k )(k ) s 8

184 () : P G (k) = P G e (k) P G/e (k) (8.6), C 4.4, P C4 (k) = k(k ) k(k )(k ) = k(k )(k k +)., C 5, 8.9, P C5 (k) P C4 (k) C 4 k- k- k- k- = - e k k- k 8.9: C 4 (C ). P C5 (k) = k(k ) 4 P C4 (k) = k(k ) 4 k(k )(k k +)=k(k )(k 4k +6k 4). C 5 = - C 4 8.9: C 5 C 4. (4), n. n =, 8.94, P C (k) =k(k ), n =., n, : k- k 8.94: C.. P Cn (k) = (k ) n +( ) n (k ) (8.6) 84

185 , 8.95 e, (8.6) P Cn (k) = k(k ) n P Cn (k) = k(k ) n {(k ) n +( ) n (k )} = k(k ) n (k ) n +( ) n (k ) = (k ) n +( ) n (k ).,, n T n C n C n- = - e 8.95: C n e, n T n C n.. ( ). P Cn (k) = (k ) n +( ) n (k ) 0.4 (005 0 ) G, P G (k). ( ), G, G.,, P G () = P G () = 6. R,B,G 8.96., G,G G,, G G., G, P G () P G () = 6.,,. 0.5 (006 0 ) n : G, : T n, : K n. P Kn (k) P G (k) P Tn (k) 85

186 R B G R B R B R G B B R G R G G R B B G G R G G B B R G R B 8.96: G, G. 6. ( ), 4 K 4,,. 8.97,, k k- k k- k- k- k- k- k- k k k- k- k- k- k- 8.97:. k(k )(k )(k ) k(k )(k ) k(k ) (k ) k(k ), 4 T 4.,,,, k,.,, n. P Kn (k) P G (k) P Tn (k) (8.6) k(k )(k ) (k n +) P G (k) k(k ) n (8.64). 86

187 ,. 0.6 (007 0 ). ( ), : P G (k) = P G e (k) P G/e (k) (8.65),.., G 8.98 e, e = - G A B 8.98: G. (8.65), G 8.98 A, B., A, B, (8.65),. A, 8.99 e, A 8.99 G,G., G,G 8.00, 8.00 = - e A G G 8.99: A. A G,G.., G K G, G G G 4. {k(k )(k )}., G,G 4,. 87

188 e = - G K x K G e = - G G G4 8.00: G,G. 8.0 e G,G , e = - G G5 G6 e = - G4 G7 T 8.0: G,G 4., G 5,G 6,G 7,, 8.99 A., 8.0 T k(k ). G 5,G 6,G 7 e 8.0,., 8.99 A P A (k) = P G (k) P G (k) = P {K} (k) P G (k) {P G (k) P G4 (k)} = P (k) {K} P G (k)+p G4 (k) = P {K} (k) {P G 5 (k) P G6 (k)} + {P G7 (k) P T (k)} = P (k) {K} {P T 5 (k) P T4 (k)} + {P T4 (k) P T (k)} + P T4 (k) P K (k) P T (k) = P {K} (k) P T 5 (k)+5p T4 (k) P T (k) P K (k) (8.66) 88

189 e = - G5 T5 T4 e = - G6 T4 T e = - G7 T4 K 8.0: G 5,G 6,G 7... n, P Kn (k) = k(k )(k ) (k n + ) (8.67) P Tn (k) = k(k ) n (8.68), A P A (k) = {k(k )(k )} k(k ) 4 +5k(k ) k(k ) k(k )(k ) = k 6 8k 5 +9k 4 9k +k 0k (8.69). B. B 8.0 e, 8.0 G 8 K G 8 = - e B G8 K4 8.0: B. G 8 K , G G 9., G G 6 89

190 e = - G8 G G9 = - e G9 G6 K 8.04: G 8. G G 9., G 9 G 6 K. K, P B (k) = P G8 (k) P K4 (k) = {P G (k) P G9 (k)} P K4 (k) = P G (k) {P G6 (k) P K (k)} P K4 (k) = P G5 (k) P G6 (k)+p K (k) P K4 (k) = P T5 (k) P T4 (k) {P T4 (k) P T (k)} + P K (k) P K4 (k) = P T5 (k) P T4 (k)+p T (k)+p K (k) P K4 (k) (8.70),., P Kn (k),p Tn (k) P B (k) = k(k ) 4 k(k ) +k(k ) + k(k )(k ) k(k )(k )(k ) = k 5 8k 4 +4k k +4k (8.7)., (8.69)(8.7), P G (k) = P A (k) P B (k) = {k 6 8k 5 +9k 4 9k +k 0k} {k 5 8k 4 +4k k +4k} = k 6 9k 5 +7k 4 6k +6k 4k (8.7).,, e (8.65) (8.7) (, G ).,, G n, m n =6,m=9, k n, k n m,. G 90

191 . 0.7 (007 ) G n, m., : P G (k) (i) k n. (ii) k n m. (iii). m. ( ).,,., 4 K 4.,. P K4 (k) = k(k )(k )(k ) = k 4 6k +k 6k (8.7), (i) k 4, k n. (ii) k n 6, m m = n(n )/, n =4, m =4 / =6, k n m.,, (iii).,, K 4.,., : P G (k) = P G e (k) P G/e (k) (8.74)., m, m, n G P (m,n) G (k)., G e m, n, G/e m, n, P (m,n). (8.75). G (k) = P (m,n) G e (k) P (m,n ) G/e (k) (8.75) (i) m =, G, n, P (,n) G (k) = k(k ) k n = k n k n (8.76).,. m., P (m,n) G (k) = kn + n α i k n i (8.77) m, n G. k n., G e G e, G e i= 9

192 m, n, G P (m,n) G e (k) = k n + n α i k n i (8.78)., G e G/e, n i= P (m,n ) G/e (k) = k n + n β i k n i (8.79)., (8.75), m, n G i= P (m,n) G (k) = k n ( α )k n +(k n ) (8.80)., m., m. (ii) m =, P (,n) G (k) = k n k n (8.8) (k n ). m., m, n G P (m,n) G (k) = k n (m )k n + n α i k n i (8.8)., k n m (m ). (i) P (m,n) G e (k) = k n (m )k n + P (m,n ) G/e (k) = k n + i= n α i k n i (8.8) i= n β i k n i (8.84)., (8.75) m, n G i= P (m,n) G (k) = k n (m )k n k n +(k n ) = k n mk n +(k n ) (8.85), m (k n m m )., m. (iii) m = P (,n) G (k) = k n k n (8.86). (.,,.), m., P (m,n) G (k) = kn + n ( ) i α i k n i (8.87) i= 9

193 m, n G., : ( ) i, i α i > 0., ( ) i, m., (i)(ii) P (m,n) G e (k) = k n + n ( ) i α i k n i (8.88) i= P (m,n ) G/e (k) = k n n ( ) i β i k n i (8.89). α i, i β i > 0., (8.75) m, n G i= P (m,n) G (k) = k n k n +( )α k n + = k n mk n + n ( ) i (α i + β i )k n i i= n ( ) i (α i + β i )k n i (8.90) i=. (ii) : α = m. α i + β i > 0, m ( ), m. 9

194

195 95 9.,,,.,,. 9.. (arc family) A(D) : V (D). (digraph) D:V (D) A(D) ( 9.05 ). D u z v w 9.05: D. V (D) = {u, v, w, z}, A(D) = {uv, vv, vw, vw, wv, wu, zw}. D (underlying graph) : D ( 9.05 ). u z v w 9.06: (simple digraph) :D,. ( ) : ( 9.07 ). :,., 9.08 A B. wz. D A =(a ij ): a ij v i v j, n n n.

196 u u z z v w v w 9.07:.7. A u z B u z v w v w 9.08: A B. wz. ( ) :, A D A A = : D. (strongly connected) :, v, w v w. (orientable) : G ( 9.0 ).. G, G. ( )., G.,. 96

197 9.0:., C, C e ( 9. ). G e C C 9.: C C., e C. C C C..,,.,. ( ).,.. (00 #0 ) A G. B 40 E A 9 D G 50 0 ( ) C 0 F A V l(v) A : 0 B : l(a) + 0 = 0 C : l(a) + 50 = 50 D : max{l(b)+ 6,l(C)+ } = max{6, 6} = 6 F : max{l(d)+,l(c)+ 0} = max{85, 60} = 85 E : max{l(b)+ 40, l(b)+ 5, l(f)+ } = max{70, 97, 96} = 97 G : max{l(e)+ 8,l(F)+ 0} = max{05, 05} = 05, 05,

198 A B E D 50 B E 8 D G A G C F C F 9.: (00 #0 ) D D D.. (). () D D,. ( ) () D, D 9.. D D - A B A B 9.: D, D. () 9.4 G D, D, A G, A D, A D D D G : G, D, D. A G = , A D = , A D = (9.9) 98

199 . A D + A D A D + A D = (9.9), ([A D + A D] ).., : A G = A D + A D (9.9).,. 9.4,., vw vw., (9.9) [A G ] vw =[A D + A D] vw. [A D ] vv =[A D] vv (9.9) [A G ] vv =[A D + A D] vv., (9.9), v, w [A G ] vw = [A D + A D] vw (9.94) [A G ] vv = [A D + A D] vv (9.95). 9.. D, D. 9.5,,. u v w 9.5:,. (out-degree) outdeg(v) :vw D. (in-degree) indeg(v) :wv D. 99

200 D.. D, D outdeg(v) = indeg(v). (Hamiltonian digraph) :. (semi-hamiltonian digraph) :.. D, n. v, outdeg(v) n/,, indeg(v) n/, D. (tournament) : ( 9.6 ). v z w y x 9.6:.. (i). (ii). ( ) (i) n. T n, ( 9.7 ). () vv T, v v v v n. () vv T, v v T, 9.8 v i. () vv i T, v v v n v. ( ). ( ). 00

201 T T v i- v vi v vn v v 9.7: T. v v4 v i- v i v v i+ v v n v 9.8: vv T, v v T, v i.. (00 #0 ), uv vw uw.. (). ().,. (). ( ) () 9.9. w v u 9.9:. ().47, k = u, v, w : outdeg(k) : indeg(k) (u) : outdeg(u) =, indeg(u) =0 (v) : outdeg(v) =, indeg(v) = (w) : outdeg(w) =0, indeg(w) = 0

202 ., outdeg ( indeg )., outdeg indeg,. (), outdeg(k) =0 k,..4 (005 ). (). () K n (n ),, K r,s (r, s ),. (). ( ) (), ( ), v, w.,. () K n (n ) v deg(v) =n, Dirac, v deg(v) n/., (),., ( 9.0( ) ). K4 K, A B 9.0: K 4 ( ) K, ( ). K r,s (r, s ), ABAB 4 (A, B ),,,, : ABAB ( 9.0( ) ). () 9.. 0

203 9.:..5 (006 ) v,v,,v N D. a ij v i, v j D N N- A D, A k (i, j) D k (v i,v j ). ( ), A a a a n a A = a a a n a = a n a nn a n a nn n l= a n la l l= a la l l= a la ln n l= a la l n l= a n nla l l= a nla ln (9.96)., (i, j) [A ] ij = n a il a lj (9.97) l=,, a il v i v l v i v l., a lj v l v j v l v j., a il a lj v i, v l, v j v i v l v j., [A ] ij,, (v i,v j ). A k. n n n [A k ] ij = a il a ll a lk l k a lk j (9.98) l = l = l k =, a il i l, a ll l l,..., a lk j j l k, a il a ll a lk l k a lk j {v l,v l,,v lk } k 0

204 ., (9.98) k (v i,v j )..6 (007 ) ( ),,, A D S 5 B 4 7 E 7 5 T 6 4 C 6 F ( S, T) ( ). ( ). /***************************************************************************/ /* Graph Theory 007 exam.# Sample program to find the shortest path */ /* J. Inoue */ /**************************************************************************/ #include<stdio.h> #define N 8 /* # of points */ /* Main Program */ main() { int flag[n]; /* (, 0) */ int distance[n]; /* */ int root_point[n]; /* */ int i,j; /* */ for(i=0; i <= N-; i++){ flag[i]=0; distance[i]=-; root_point[i]=0; } /* 8 x 8 */ /* i,j <ij> */ /* - */ int adjacent[n][n]={ {-,,,6,-,-,-,-}, 04

205 {,-,5,-,,4,-,-}, {,5,-,,-,7,,-}, {6,-,,-,-,-,6,-}, {-,,-,-,-,,-,7}, {-,4,7,-,,-,4,5}, {-,-,,6,-,4,-,}, {-,-,-,-,7,5,,-} }; /* */ printf("// Define as S==0,A==,B==,C==,D==4,E==5,F==6,T==7 //\n"); printf("\n"); /* */ distance[0]=0; /* S */ flag[0]=; /*, S */ int count=0; int min, min_number; /* */ while(count<n){ min=-; for(i=0; i<=n-; i++){ /* */ if(flag[i]==){ for(j=0; j<=n-; j++){ /* */ if((flag[j]==0) && (adjacent[i][j]!=-)){ /* */ if((distance[i]+adjacent[i][j]<min) (min==-)){ min=distance[i]+adjacent[i][j]; /* */ min_number=j; } /* */ if((distance[i]+adjacent[i][j]<distance[j]) (distance[j]==-)){ distance[j]=distance[i]+adjacent[i][j]; root_point[j]=i; } } } } /* */ flag[min_number]=; } count++; } 05

206 /* */ for(i=0; i<=n-; i++){ printf("// The shortest distance to point %d is distance[%d]=%d //\n",i,i,distance[i]); } printf("\n"); printf("// The previous point for each point on the shortest path //\n"); printf("\n"); for(i=0; i <=N-; i++){ printf("root_point[%d]=%d\n",i,root_point[i]); } printf("\n"); printf("// The shortest path //\n"); printf("\n"); i=7; printf("%d",i); while(i!=0){ printf(" <== %d",root_point[i]); i=root_point[i]; } printf("\n"); }. // Define as S==0,A==,B==,C==,D==4,E==5,F==6,T==7 // // The shortest distance to point 0 is distance[0]=0 // // The shortest distance to point is distance[]= // // The shortest distance to point is distance[]= // // The shortest distance to point is distance[]=5 // // The shortest distance to point 4 is distance[4]= // // The shortest distance to point 5 is distance[5]=4 // // The shortest distance to point 6 is distance[6]=6 // // The shortest distance to point 7 is distance[7]=8 // // The previous point for each point on the shortest path // root_point[0]=0 root_point[]=0 root_point[]=0 root_point[]= root_point[4]= root_point[5]=4 root_point[6]= root_point[7]=6 06

207 // The shortest path // 7 <== 6 <== <== 0 07

208

209 09 9..,,,,. : /, /, /6., E,E 6 ( 9. ). E,,E 6 / / E E E E4 E5 E6 /6. 9.:. E 4,, x =(0, 0, 0,, 0, 0)., x i, E i.,, x = (0, 0,, 6, ) (, 0, x = 0, 4, 6, 6, 9, ) 9., (transition matrix) : P =(P ij ). ij P ij (transition probability),, E i E j., P =

210 , x 0 =(p 0,p 0,p 0,p 4 0,p 5 0,p 6 0), x =(p,p,p,p4,p5,p6 ) x = x 0 P (9.99) (p,p,p,p 4,p 5,p 6 )=(p 0,p 0,p 0,p 4 0,p 5 0,p ) ( ) = p 0 + p 0, p p 0, p 0 + p p4 0, p 0 + p p5 0, p4 0 + p p6 0, p p6 0 (9.400)., p = p 0 + p 0 (9.40) t =0 E, E, E, / E.. (00 #0 4 ) P Q, PQ., P Q PQ. ( ), 9. P / / /4 v /6 / / v /4 /6 v / 9.: P. P = (9.40)., 9.4 Q 0

211 v / / v v 9.4: Q. Q = (9.40) 0 0., t =0 v,v,v p v (0),p v (0),p v (0), p(0) = (p v (0),p v (0),p v (0)), t = p() (p v (),p v (),p v ()) = (p v (0),p v (0),p v (0)) = ( p v (0) + 4 p v (0) + 6 p v (0), p v (0) + p v (0) + 6 p v (0), p v (0) + 4 p v (0) + p v (0), t =0 v p v (0) =,p v (0) = p v (0) = 0,, ( ) ( (p v (),p v (),p v ()) = (, 0, 0) 4 4 =,, ) (9.404) ( 9. ).,,. ( )., PQ 0 6 PQ = = 8 8 (9.405) , PQ, PQ. PQ 9.5 t =0 t = 6 (p v (),p v (),p v ()) = (p v (0),p v (0),p v (0)) )

212 / /8 v /6 / v /6 /8 / / v /4 9.5: PQ. = ( pv (0) + p v (0) + p v (0), p v (0) + p v (0) + p v (0) 6 6 8, p v (0) + p v (0) + p ) v (0) 8 4 (9.406).. (004 ). D : {,,, }, j = k, ij kl., D,... () P P = (a,b,c )., a,b,c. () t =0, a,, x =(, 0, 0), t =,, a,b,c (p a (),p b (),p c ()),, (p a (),p b (),p c ()). () t = n, a,b,c p a (n),p b (n),p c (n). ( ). {,,, }, j = k, ij kl,. {, {,

213 , , 9.6: {,,, }, j = k, ij kl. ( D ), D, D,, D v, outdeg(v) = indeg(v) (. ), outdeg() = = indeg() outdeg() = = indeg() outdeg() = = indeg() outdeg() = = indeg(),.,,,... () P 9.7.,. / a /6 /6 /6 /6 b /6 c / /6 / 9.7: P a, b, c. ()() t = n, n + : x n (p a (n),p b (n),p c (n)), x n+ (p a (n +),p b (n + ),p c (n + )) P x n+ = x n P (9.407)

214 ,, (p a (n +),p b (n +),p c (n + )) = (p a (n),p b (n),p c (n)) (9.408) p a (n +) = p a(n)+ 6 p b(n)+ 6 p c(n) (9.409) p b (n +) = 6 p a(n)+ p b(n)+ 6 p c(n) (9.40) p c (n +) = 6 p a(n)+ 6 p b(n)+ p c(n) (9.4).,., n : p a (n)+p b (n)+p c (n) =( a, b, c ), p c (n) = p a (n) p b (n), p a (n +) = p a(n)+ 6 p b (n +) = p b(n)+ 6 (9.4) (9.4) ( p a (n) p b (n) ) = ( 0 0 ) n ( p a (0) p b (0) ) ( n 0 + k=0 0 ) k ( 6 6 ) (9.44)., p a (n) p a (n) = n p a(0) + n 6 k = n p a(0) + n 6 k=0 = n p a(0) + ( ) n (9.45).,, p b (n) p b (n) = n p b(0) + ( ) n (9.46), p c (n) p c (n) = n (p a(n)+p b (n)) ( ) n (9.47)., t =0 b : p a (0) = 0,p b (0) =,p c (0) = 0. p a (n) = ( ) n p b (n) = ( + ) n p c (n) = ( ) n (9.48) (9.49) (9.40) 4

215 . (005 ) 5 (A, B, C, D, C, ).,,,, 4, 5, 6,. (),. (),. () A, 5 A. ( ) () P P = (9.4), 9.8. / A /6 / / /6 E / D / / / / / C / B /6 /6 /6 9.8: P. () P P = (9.4),,, n(n ), P n., lim n P n, 5

216 ., (i j,j i ) (p ii 0),. () P P = (9.4) , x(t) =(p A (t),p B (t),p C (t),p D (t),p E (t)), A, x(0) = (, 0, 0, 0, 0) ( 476 x(5) = x(0)p 5 = 7776, , , , 75 ) (9.44) 7776, t =5 A 476/ (006 ) E,E,,E 6., E /, /. /6., E.,., 6 p,p,,p 6. ( ) E, E E, E 6, 9.9., n /6 /6 /6 /6 / / / / / E E / E / E4 / E5 E6 9.9: E, E 6. x (n) =(p (n),p (n),p (n),p 4 (n),p 5 (n),p 6 (n)), n A : A = (9.45)

217 x n = x 0 A n (9.46), n =6, x 0 =(0,, 0, 0, 0, 0).,. /************************************************************/ /* Calculation of time evolution of probability for */ /* -dimensional random walk */ /* J. Inoue */ /***********************************************************/ #include<stdio.h> #define tmax 0 main(){ FILE *pt; double a[6][6],b[6][6]; int i,j,k,t; for(i=0; i<=5; i++){ for(j=0; j<=5; j++){ b[i][j]=0; }} /* Definition of transition matrix A (definition of digraph) */ a[0][0] = 0; a[0][] =.0; a[0][] = 0; a[0][] = 0; a[0][4] = 0; a[0][5] = 0; a[][0] =.0/; a[][] =.0/6; a[][] =.0/; a[][] = 0; a[][4] = 0; a[][5] = 0; a[][0] = 0; a[][] =.0/; a[][] =.0/6; a[][] =.0/; a[][4] = 0; a[][5] = 0; a[][0] = 0; a[][] = 0; a[][] =.0/; 7

218 a[][] =.0/6; a[][4] =.0/; a[][5] = 0; a[4][0] = 0; a[4][] = 0; a[4][] = 0; a[4][] =.0/; a[4][4] =.0/6; a[4][5] =.0/; a[5][0] = 0; a[5][] = 0; a[5][] = 0; a[5][] = 0; a[5][4] = 0; a[5][5] =.0; /* Calculation of A^{t} */ if((pt=fopen("matprod.txt","wt"))!=null){ for(i=0; i<=5; i++){ for(j=0; j<=5;j++){ if((i==0) && (j==0)){fprintf(pt,"time Step=%d\n\n",);} if(j!=5){ fprintf(pt,"a(%d)(%d,%d)=%lf ",t,i+,j+,a[i][j]); }else{ fprintf(pt,"a(%d)(%d,%d)=%lf\n",t,i+,j+,a[i][j]);} }} for(i=0; i<=5; i++){ fprintf(pt,"\n t=%d p(%i)=%lf",,i+,a[][i]); //fprintf(pt,"%d %lf ",, a[][i]); } fprintf(pt,"\n %c", \n ); for(t=;t<=tmax;t++){ for(i=0; i<=5; i++){ for(j=0; j<=5;j++){ for(k=0; k<=5; k++){ b[i][j] = b[i][j] + a[i][k]*a[k][j]; } } } for(i=0; i<=5; i++){ for(j=0; j<=5;j++){ if((i==0) && (j==0)){fprintf(pt,"time Step=%d\n\n",t+);} 8

219 if(j!=5){ fprintf(pt,"a(%d)(%d,%d)=%lf ",t+,i+,j+,b[i][j]); }else{ fprintf(pt,"a(%d)(%d,%d)=%lf\n",t+,i+,j+,b[i][j]);} }} for(i=0; i<=5; i++){ fprintf(pt,"\n t=%d p(%i)=%lf ",t+,i+,b[][i]); //fprintf(pt,"%d %lf ",t+,b[][i]); } fprintf(pt,"\n %c", \n ); for(i=0; i<=5; i++){ for(j=0; j<=5; j++){ a[i][j]=b[i][j]; } } for(i=0; i<=5; i++){ for(j=0; j<=5; j++){ b[i][j]=0; }} } } fclose(pt); }. 9.0, p p p p4 p5 p6 P t 9.0:.,, 6, 9

220 6. : P (), / E E, E., E E,., P (X t+ = E X t = E )=0, (, ). 0

221 0.,, Menger,,,. 0.. Hall (mariage problem).,.?,. {g, g, g, g 4 }, {b, b, b, b 4, b 5 }. g b, b 4, b 5 g b g b, b, b 4 g 4 b, b 4 0.., G(V,V ), V V g b g b g b g4 b4 b5 0.:. V V,,,.

222 G = G(V,V ), G V V?. Hall, k k. ( ) [ ] : k k. [ ] :. m., m =, k =,.,. m. (i) k<m, k, k +,, m (m <m) m.,. (ii) k(< m) k, k. m k. (m k) h (h m k) h ((h + k) (h + k) )., m k.. 0..,. E:. F=(S,S,,S m ):E. F : S i E m. ( ) E={,,, 4, 5, 6}, S = S = {, },S = S 4 = {, },S 5 = {, 4, 5, 6}., F= (S,S,,S 5 )., F =(S,S,S,S 5 ) {,,, 4} ( ). 0..,, Hall E={b, b, b, b 4, b 5, b 6 } = {,,, 4, 5, 6}., F=(g, g, g, g 4, g 5 )=(S,S,S,S 4,S 5 ), S = {, } S = {, }

223 S = {, } S 4 = {, } S 5 = {, 4, 5, 6} ( 0. ), F Hall. g b g b g b g4 b4 g5 b5 b6 0.: Hall, Hall : m n (m n) : m n M (i) m ij n. (ii),,. ( ) M = (0.47) 5 4. m = n,. 7. M m<n m n., M n m. ( ) E = {,,, 4, 5} M. F=(S,S,S,S 4,S 5 ), M i E S i. (0.47) S,S,, S = {4, 5}

224 S = {, } S = {4, 5} S 4 = {, } S 5 = {, }, F (4,, 5,, ), (5,, 4,, ), M = 5 4 (0.48) ( ) Menger (edge-disjoint path) : v w. (vertex-disjoint path) : v w. vw- : G E, v w E. ( ) : 0. E = {ps, qs, ty, tz}, E = {uw, xw, yw, zw}. vw- : G V, v w V V. ( ) : 0. V = {s, t}, V = {p, q, y, z}. G p u s x v q y w t r z 0.: G. ( v p u w,, v r t y w) v w? Menger I Menger I G v w, vw-. v w? Menger II 4

225 Menger II G v w, vw-. ( ) 0.4 G, vw- E = {vp, vq}, E = {pr, qr, qs}, E = {rw, sw},., vw- V = {p, q}, V = {r, q}, V = {r, s},. p r v w q s 0.4: Menger G v, w., ( ) ( )., x 4 v 4 y 4 w z 0.5:. v w..?. N :. Ψ(a) : a. outdeg(x) :xz. 5

226 indeg(x) :zx 7.,. (flow) a φ(a) φ,. (i) a φ(a) Ψ(a). (ii) v w,. ( ), 0.6 ( v ) = ( w ) = =6 ( 0.6 ) x 0 v y 0 4 w z 0.6: 0.5,, v, w. (cut) : D vw-. :. 0.5, ( ) {xw, xz, yz, vz}, {xw, zw}, 6.,.. 0.5, 0.6,, ( ) =( ) =6,. 7, indeg, outdeg,,,. 6

227 0... v w p, : v,v,v,,v k,v k, w ( 0.7 ).,, e i =(v i,v i ), e i vk=w ek e v e v k- e v v v=v0 0.7: p., e, e. v i,v i. p e i., e i =(v i,v i ) e i v i,v i,. 0.7, e, e., e i, (residual) ( ) Ψ(e i ),, φ(e i ). { Ψ(e i ) φ(e i ) (e i ) g(e i ) = (0.49) φ(e i ) (e i ) g(e i ) p g(p). : g(p) = min i k g(e i) (0.40) φ(e i ) φ(e i )+g(p) (e i ) (0.4) φ(e i ) φ(e i ) g(p) (e i ) (0.4), φ g(p)., e i, e p g(p),, e i, g(p),,... e φ(e) =0.. v w p g(p) > 0,.... (0.4)(0.4) φ,. 7

228 8 0.., U V U V. 0.8: U V., v U, U V, V w,.,,.. (004 ). a d 0 v 4 5 w 0 b 7 c () v w. (), (),. ( ) () p v a d w., φ(v, a) = φ(a, d) = φ(d, w) = 0 (0.4)., p g(v, a) = Ψ(v, a) φ(v, a) =0 0=0 g(a, d) = Ψ(a, d) φ(a, d) = 0= g(d, w) = Ψ(d, w) φ(d, w) = 0= 8

229 , p g(p ) = min g(k) = (0.44) k=(v,a),(a,d),(d,w)., (0.4)(0.44). φ(v, a) = 0+g(p )= φ(a, d) = 0+g(p )= φ(d, w) = 0+g(p )= p v b c w. p., p φ(v, b) = φ(b, c) = φ(c, w) = 0 (0.45) g(v, b) = Ψ(v, b) φ(v, b) =0 0=0 g(b, c) = Ψ(b, c) φ(b, c) =7 0=7 g(c, w) = Ψ(c, w) φ(c, w) = 0= g(p ) = min g(k) = (0.46) k=(v,b),(b,c),(c,w)., (0.45)(0.46). φ(v, b) = 0+g(p )= φ(b, c) = 0+g(p )= φ(c, w) = 0+g(p )=, (a, d),, (c, w).,,,.,, v w v a c d w,, v b c d w. p, p 4. p, φ(v, a) = φ(a, c) = 0 φ(c, d) = 0 φ(d, w) =. (a, c), (c, d) g(v, a) = Ψ(v, a) φ(v, a) =0 = 9 g(a, c) = φ(a, c) =0 g(c, d) = φ(c, d) =0 g(d, w) = Ψ(d, w) φ(d, w) = = 9

230 , p g(p ) = min g(k) =0 k=(v,a),(a,c),(c,d),(d,w),. φ(v, a) = φ(a, c) = 0 φ(c, d) = 0 φ(d, w) = p 4., (c, d). p 4, φ(v, b) = φ(b, c) = φ(c, d) = 0 φ(d, w) = g(v, b) = Ψ(v, b) φ(v, b) =0 =7 g(b, c) = Ψ(b, c) φ(b, c) =7 =4 g(c, d) = φ(c, d) =0 g(d, w) = Ψ(d, w) φ(d, w) = = g(p 4 ) = min g(k) =0 k=(v,b),(b,c),(c,d),(d,w) φ(v, b) = φ(b, c) = φ(c, d) = 0 φ(d, w) =., + = 4, 0.9. () 0.9, v w, 4+7 = 4, ().,. 0

231 (0) a () d () v (0) 0 (4) 0 (5) () w b (7) c 0.9:,.., 4+7=4, + = 4.. (005, 006 ). a v 5 b 4 w c (),. (),. ( ) (), {aw,bw,cw} 8 ( ) {cv,bc,cw} 8 ( ) {av,bv,cv} 0 {av,ab,aw} 7 {av,bv,bc,cw} 8 ( ) {aw,bw,bc,cv} {ab,bv,bc,bw} 7 {aw,ab,bv,cv} 9 {av,ab,bw,cw} {av,bv,bc,bw,aw} {aw,ab,bv,bc,cw} 7 {cv,bv,ab,bw,cw}

232 {av,ab,bw,bc,cv} 5. (). p v a w, φ(v, a) = φ(a, w) = 0 (0.47)., p, Φ(u, v), p g(p )., g(v, a) = Φ(v, a) φ(v, a) =4 0 = 4 (0.48) g(a, w) = Φ(a, w) φ(a, w) = 0 = (0.49) g(p ) = min g(k) = (0.440) k=(v,a),(a,w) φ(sfv, a) = 0+g(p ) = (0.44) φ(a, w) = 0+g(p ) = (0.44)., p,p v b w, v c w, p,p, g(p )=,g(p )=, φ(v, b) = 0+g(p ) = (0.44) φ(b, w) = 0+g(p ) = (0.444) φ(v, c) = 0+g(p ) = (0.445) φ(c, w) = 0+g(p ) = (0.446). vb, aw, cw,., aw, ba,., ba,, ba. v a b w, v c b w. p 4,p 5., p 4,, p 4., g(v, a) = Φ(v, a) φ(v, a) =4 = (0.447) g(a, b) = Φ(a, b) φ(a, b) =5 0 = 5 (0.448) g(b, w) = Φ(b, w) φ(b, w) =4 = (0.449) g(p 4 ) = min g(k) = (0.450) k=(v,a),(a,b),(b,w) φ(v, a) = +g(p 4 ) = 4 (0.45) φ(a, b) = 0+g(p 4 ) = (0.45) φ(b, w) = +g(p 4 ) = (0.45)

233 . p 5, p 5., g(v, c) = Φ(v, c) φ(v, c) =5 = (0.454) g(c, b) = Φ(c, b) φ(c, b) = 0 = (0.455) g(b, w) = Φ(b, w) φ(b, w) =4 = (0.456) g(p 5 ) = min g(k) = (0.457) k=(v,c),(c,b),(b,w) φ(v, c) = +g(p 5 ) = (0.458) φ(c, b) = 0+g(p 5 ) = (0.459) φ(b, w) = +g(p 5 ) = 4 (0.460)., 4++=8, ().

234 0.40: