ࡱ> nF8!ܢsilPNG  IHDR exgIFxNETSCAPE2.0$NPPLTE3f333f3333f3ffffff3f̙3f3f333f333333333f33333333f33f3ff3f3f3f3333f33̙33333f3333333f3333f3ffffff3f33ff3f3f3f3fff3ffffffffffff3ffff̙fff3fffffff3ffffff3f333f3333f3ffffff3f̙̙3̙f̙̙̙̙3f3f̙333f3̙333f3fff̙fff3f̙̙3f̙3f̙3f333f3333f3ffffff3f̙3f3f9ųtRNS[rbKGDHgIFgdni cmPPJCmp0712HsyIDATWMϱ0?:JU9bW&":"ӯxH}fzIcv?@~9ٛ"}3S lvE\ĽU!b$CV`@!d,3f333f3333f3ffffff3f̙3f3f333f333333333f33333333f33f3ff3f3f3f3333f33̙33333f3333333f3333f3ffffff3f33ff3f3f3f3fff3ffffffffffff3ffff̙fff3fffffff3ffffff3f333f3333f3ffffff3f̙̙3̙f̙̙̙̙3f3f̙333f3̙333f3fff̙fff3f̙̙3f̙3f̙3f333f3333f3ffffff3f̙3f3f *@X JÇ8 E/^"BdQO^ b3X"(Ó CfL37~eE  Continued &     6Incidence Matrix B(G) Let the vertex-set of G be {v1,v2, & , vp} and the edge-set (or arc set) be {e1,e2, & , eq}. Then B(G) = [bi,j]pxq where bi,j = 1 if vi is incident to ej, and bi,j = 0 otherwise. If G is a simple graph, then each column of B(G) has exactly two 1 s. The row sum of B(G) is a zero vector provided the addition is taken modulo 2. If G is a hypergraph, then the above property may not hold. FZ   %          UO><  .    &     (   Walks in Graphs  A walk from u to v in a graph G is a sequence <u = v0, v1, v2, & , vt = v> of vertices in G where vivi+1 is an edge of G for i = 0,1,2, & ,t  1. A trail is a walk such that all edges vivi+1 are distinct and a path is a trail in which all vertices are distinct. A closed trail (u = v) is called a circuit and a circuit without repeating a vertex is a cycle. The length of a walk (or a trail, a circuit, a path, a cycle) is the number of edges in the walk (or respectively trail, & ). Z!      $"   3 /thB    P  (   The Number of Walks   Theorem 1.5 Let G be a graph and V(G) = {v1,v2, & , vp}. Then the number of walks of length n ( 1) from vi to vj is the (i,j)-entry of [A(G)]n. Proof. By induction on n. Problem Find the number of cycles of length 3 and 4.V)33 ,33N4  9  t   Distance in Graphs  The distance of two vertices u and v in G, denoed by dG(u,v), is the length of a shortest path from u to v, i.e. a path with minimum number of edges. The eccentricity of a vertex v in a graph G, eG(v) = max{dG(u,v)| u V(G)}. The diameter of G, diam(G) = max{eG(v) | v V(G)}. The radius of G, rad(G) = max{eG(v) | v V(G)}. Theorem 1.6 rad(G) diam(G) 2rad(G). $pZ)^ &3333333333&33 333333333333&333333  Z Z33333333 Z,+         %     "              Special Graphs (   A graph G is a complete t-partite graph if V(G) can be partitioned into t subsets V1, V2, & , Vt such that two vertices are adjacent if and only if they are from different subsets. Vi is called a partite set of G and G is denoted by K(n1,n2, & ,nt) provided |Vi| = ni for I = 1, 2, & , t. If t = 2, then it is called a complete bipartite graph.*Z_Q,V2_Q _Q_Q _Q_Q _Q_Q  ( (4 $_Q h^      L   Maximum Sizes   ZProposition 2.1 Let G be a bipartite graph of order p. Then G has at most [p2/4] edges. A graph G is H-free if G does not contain a subgraph H. Corollary 2.2 Let G be a K3-free graph. Then G is of size at most [p2/4] provided that G is of order p. Corollary 2.3 If G is of order p and contains no odd cycle, then G has at most [p2/4] edges.[ZM;?  8(M;  * "_QE  4     Turn s Theorem8"0     dTheorem 2.4 If G is of order p and does not contain a subgraph Kt+1, then G is isomorphic to K(n1,n2, & ,nt) where |ni - nj| 1, 1 i j t provided that G is of maximum size. If a graph is H-free, then the maximum size of such a graph of order p is denoted by ex(p;H) and an H-free graph of size ex(p;H) is called an extremal H-free graph. An extremal Kt+1-free graph is also called a turn s graph. Problem: Find ex(p;Kt+1). Z M;4 ((((((("*"*"" "&(" &(W"&E<2"&("* "" "" &M;.M;&M;"7   (            !  ' Petersen Graph  One of the most important graphs in Graph theory is the so-called Petersen graph. In fact it is a (3,5)-cage or simply a 5-cage and it is a unique 5-cage.(?)   # ` @AvffJff` @AvffJff` MMM___` BBb"eIIn>h` @Av́q~דg` ́ޤ^ד` MMMŞffJff>?" dd@,? " Pd@ lF `A@ `" d n?" dd@   @@``PR    @ ` ` p>> ?#^( PhT `T 0 # "0 b 0 # "0\  pp   "0h  s *" pp0 h  s *" 0 p h  s *" 0 n  0" p 0 n  0"P  \  pp   "0h  s *" pp0 h  s *" 0 p h  s *" 0 n  0" p 0 n  0"P  \  pp   "( 0H h  s *" pp0 h  s *" 0 p h  s *" 0 n  0" p 0 n  0"P  \  pp   "x 0h  s *" pp0 h  s *" 0 p h  s *" 0 n  0" p 0 n  0"P  \  pp   "0h  s *" pp0 h  s *" 0 p h  s *" 0 n  0" p 0 n  0"P  B b / !# "P\ pz   "0/n   0"zn   0"pzV\ pz   "`/n   0"zt  6"pzP\ pz  "p/n  0"zn  0"pzV\ pz  " /n  0"zt  6"pzP\ pz  "@  /n  0"zn  0"pzV\ pz  " P/n  0"zt  6"pzP\ pz  "/n  0"zn  0"pzV\ pz  " /n  0"zt   6"pz  6x "P  P cN NN}/kGrjL#j_     0z "  0 cN NN}/kGr ,{Nd\ ,{ Nd\ ,{Vd\ ,{Nd\    6D "0`P  \*   6l "0P   ^*   6T "0 P  ^* H  0޽h ? @AvffJff___PPT92p22 Post Modern:  @?)P^( @@ (҅T De >) "Dewb De< 9)# "De<o\ b< 8) "b<B ^( ZDAo "NNB _( ZDAo "CCB `( ZDAo "LLB a( ZDAo "AAB b( ZDAo "I I B c( ZDAo "> > B d( ZDAo "GGB e( ZDAo "<<6\ < 7) "<L\ C 1) "CB h( TDAo  "B i( TDAo  "B j( TDAo  " B k( TDAo  " B l( ZDAo  "NNB m( ZDAo  ",NNB n( ZDAo  ",CCB o( ZDAo  "CC"b  p p(# "AB q( NDAo "  B r( NDAo "B s( NDAo "pB t( NDAo " p B u( TDAo " B v( TDAo "B w( TDAo "ppB x( TDAo "p p"b  p y(# "> B z( NDAo "  B {( NDAo "B |( NDAo "pB }( NDAo " p B ~( TDAo " B ( TDAo "B ( TDAo "ppB ( TDAo "p p"b  p (# " <B ( NDAo "  B ( NDAo "B ( NDAo "pB ( NDAo " p B ( TDAo " B ( TDAo "B ( TDAo "ppB ( TDAo "p p6\  < 6) " <L\  C 0) " CB ( TDAo  "B ( TDAo  "B ( TDAo  " B ( TDAo  " B ( ZDAo  "GNNB ( ZDAo  "XN NB ( ZDAo  "XC CB ( ZDAo  "GCC"b  p (# " AB ( NDAo "  B ( NDAo "B ( NDAo "pB ( NDAo " p B ( TDAo " B ( TDAo "B ( TDAo "ppB ( TDAo "p p"b  p (# " > B ( NDAo "  B ( NDAo "B ( NDAo "pB ( NDAo " p B ( TDAo " B ( TDAo "B ( TDAo "ppB ( TDAo "p p"b  p (# " <B ( NDAo "  B ( NDAo "B ( NDAo "pB ( NDAo " p B ( TDAo " B ( TDAo "B ( TDAo "ppB ( TDAo "p p6\ ; < 5) "; <L\ ; C /)  "; CB ( TDAo "; ; B ( TDAo "0 0 B ( TDAo "0 0 B ( TDAo "; ; B ( ZDAo "s N NB ( ZDAo " N NB ( ZDAo " C CB ( ZDAo "s C C"b  p (#  ";  AB ( NDAo "  B ( NDAo "B ( NDAo "pB ( NDAo " p B ( TDAo " B ( TDAo "B ( TDAo "ppB ( TDAo "p p"b  p (#  ";  > B ( NDAo "  B ( NDAo "B ( NDAo "pB ( NDAo " p B ( TDAo " B ( TDAo "B ( TDAo "ppB ( TDAo "p p"b  p (#  "; <B ( NDAo "  B ( NDAo "B ( NDAo "pB ( NDAo " p B ( TDAo " B ( TDAo "B ( TDAo "ppB ( TDAo "p p6\ g6< 4) "g6<L\ g6C .)  "g6CB ( TDAo "ggB ( TDAo "\\B ( TDAo "\\ B ( TDAo "gg B ( ZDAo "N%NB ( ZDAo "N6NB ( ZDAo "C6CB ( ZDAo "C%C"b  p (#  "g6AB ( NDAo "  B ( NDAo "B ( NDAo "pB ( NDAo " p B ( TDAo " B ( TDAo "B ( TDAo "ppB ( TDAo "p p"b  p (#  "g6> B ( NDAo "  B ( NDAo "B ( NDAo "pB ( NDAo " p B ( TDAo " B ( TDAo "B ( TDAo "ppB ( TDAo "p p"b  p (#  "g 6<B ( NDAo "  B ( NDAo "B ( NDAo "pB ( NDAo " p B ( TDAo " B ( TDAo "B ( TDAo "ppB ( TDAo "p p6\ b< 3) "b<L\ bC -)  "bCB ( TDAo "B ( TDAo "B ( TDAo " B ( TDAo " B ) ZDAo "NQNB ) ZDAo "NbNB ) ZDAo "CbCB ) ZDAo "CQC"b  p )#  "bAB ) NDAo "  B ) NDAo "B ) NDAo "pB ) NDAo " p B  ) TDAo " B  ) TDAo "B  ) TDAo "ppB  ) TDAo "p p"b  p  )#  "b> B ) NDAo "  B ) NDAo "B ) NDAo "pB ) NDAo " p B ) TDAo " B ) TDAo "B ) TDAo "ppB ) TDAo "p p"b  p )#  " b<B ) NDAo "  B ) NDAo "B ) NDAo "pB ) NDAo " p B ) TDAo " B ) TDAo "B ) TDAo "ppB ) TDAo "p pV DeD 2) "DeDB ") TDAo "DDB #) TDAo "DDB $) TDAo "/DDB %) TDAo "JDDB &) TDAo "[D DB ') TDAo "v D DB () TDAo " D DB )) TDAo "D(DB *) TDAo "D9DB +) TDAo "DTDB ,) TDAo "DeDb P0 ;)# "P0n  ( 0"@ 0n  ( 0"@ 0n  ( 0"P@ t  ( 6"P@ t  ( 6 "p b / )# "bb pz I(# "0/t ( 6"zt ( 6"pzhb pz H(# "`/t ( 6"zz ( <"pzVb pz J(# "p/n K( 0"zn L( 0"pz\b pz M(# " /n N( 0"zt O( 6"pzVb pz P(# "@  /n Q( 0"zn R( 0"pz\b pz S(# " P/n T( 0"zt U( 6"pzVb pz V(# "/n W( 0"zn X( 0"pz\b pz Y(# " /n Z( 0"zt [( 6"pz ( 6L "@  P cN NN}/kGrjL#j_    ( 6 " `    R cN NN}/kGroRjL#j_  ( 6\ "``  \*  ( 6  "`   ^*  ( 6 "`   ^*  ?) C xA`C:\WINNT\Profiles\rebeccal\Desktop\posbul1a.gif"` H ( 0޽h ? @AvffJff 0$(  r  S L(@  r  S ( `    H  0޽h ? @AvffJff  0(  x  c $Uz  z x  c $pVzPp z H  0޽h ? @AvffJff  0(  x  c $Zz  z x  c $|uz @ z H  0޽h ? @AvffJff  0(  x  c $xzP  z x  c $yz   z H  0޽h ? @AvffJff  0(  x  c $zP  z x  c $   H  0޽h ? @AvffJff @8`(    c $N    ,^Cages The girth of G is defined to be the minimum size of a cycle in G denoted by g(G). Therefore, if G is a simple graph of order p which contains a cycle, then 3 g(G) p. A (k,g)-cage is a k-regular graph G with g(G) = g and G is of minimum size. If k = 3, then a (k,g)-cage is called a g-cage. 0 M;  (      (i  (  0 H  0޽h ? @AvffJff vnp(    c $cP    b> Theorem 2.1 Let the order of a (k,g)-cage be f(k,g). Then for k 3, (a) f(k,g) {k(k-1)s-2}/(k-2) if k = 2s+1; (b) f(k,g) {2k(k-1)s-2}/(k-2) if k = 2s. Proof. (a) Start with one vertex and sum the possible number of vertices up. Hence, f(k,g) 1 + k + k(k-1) + k(k-1)2 + . . . + k(k-1)s-1 = k{1 + (k-1) + (k-1)2 + . . . + (k-1)s-1} = {k(k-1)s-2}/(k-2). (b) ?   M; M;5  +        b  {   H  0޽h ? @AvffJffD      (  r  S 0P   r  S   X2  0 X2  00 ` X2  0 P 0 X2  0 0 0X2  0 X2  0 X2  0` X2  0 0 X2  0 X2  0 XB @ 0Do XB  0Do P XB  0Do XB  0Do XB  0Do XB  0Do XB  0Do`  XB @ 0Do 0XB  0Do XB  0Do 0 XB  0Do  ` XB  0Do` 0 `XB  0Do0 `XB @ 0Do P XB  0DԔ 0 H  0޽h ? @AvffJffrT8 [@(tOh+'08R px $ D P \ ht|Preliminaries: Lecture 2ihlfuminQC:\Program Files\Microsoft Office\Templates\Presentation Designs\Post Modern.potrhlfuogr9fuMicrosoft PowerPointoso@  @@uHx@p^ GPg  R('& &&#TNPP2OMi & TNPP &&TNPP     'A x(xKʦ """)))UUUMMMBBB999|PP3f3333f333ff3fffff3f3f̙f3333f3333333333f3333333f3f33ff3f3f3f3333f3333333f3̙33333f333ff3ffffff3f33f3ff3f3f3ffff3fffffffff3fffffff3f̙ffff3ff333f3ff33fff33f3ff̙3f3f3333f333ff3fffff̙̙3̙f̙̙̙3f̙3f3f3333f333ff3fffff3f3f̙3ffffffffff!___wwwkkkkkkkkktRyRtRyRtyyyyykkkkkkkkRyRtRyRtRÙyyyykkkkkkkkkRtRyRtRyØyyyykkkkkkkkktRyRtRyRtyyyyyüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüsgüüüüüüüükkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkttmQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkyRtRtRtRyRtRtRtRyRtRtRtRyRtRtRtRyRtRtRtRyRtRtRtRyRtRtRtRyRtRtRtRyRtRtkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQtQRQkkkyRtkkkQtQkkktRtkkkQRQüükkküüüüüüüüüüüüüüüüüyRtükkkQtQkkktRtkkkQRQkkkfffffffffffffffffffffffffffffffffffffffffyRtkkkffffffffffffffffffffffffffffffffffffffffQtQkkkfffffffffffffffffffffffffffffffffftRtkkkfffffffffffffffffffffffffffffffffffffffffffffQRQüüyüüüffffffüffffüffffüffffüffffüffffüffffffüffffffffüüüüîüÙfffffffffffffffffffffffffffffffffffffffffffffffffîyfffffffffffffffffffffffffffffffffffffffffffîffffffîÙyffffffffffffîÙffffffffffffffîÒyîîüüyüüüüüüüüüüüüüüüüüîüÙîØyîîÙyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyÙÒyyyyyyyyyyyyyyyyyyüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüüü--&TNPP &՜.+,0p    如螢幕大小A-MathY.  Arial 新細明體Times New Roman Wingdings Arial NarrowSymbol Post ModernPreliminariesGraph RepresentationsContinued …Walks in GraphsThe Number of Walks Distance in GraphsSpecial GraphsMaximum SizesTurán’s TheoremSolution Let p = s(a+1) + (t-s)a where a = [p/t]. Hence, p = ta + s. By counting the number of edges directly, we have ex(p;Kt+1) = {(t-1)p2 – s(t-s)}/2t or C(p-a,2) + (t-1)C(a+1,2). (Green is easier!)4Cages The girth of G is defined to be the minimum size of a cycle in G denoted by g(G). Therefore, if G is a simple graph of order p which contains a cycle, then 3  g(G)  p. A (k,g)-cage is a k-regular graph G with g(G) = g and G is of minimum size. If k = 3, then a (k,g)-cage is called a g-cage.  Theorem 2.1 Let the order of a (k,g)-cage be f(k,g). Then for k  3, (a) f(k,g)  {k(k-1)s-2}/(k-2) if k = 2s+1; (b) f(k,g)  {2k(k-1)s-2}/(k-2) if k = 2s. Proof. (a) Start with one vertex and sum the possible number of vertices up. Hence, f(k,g)  1 + k + k(k-1) + k(k-1)2 + . . . + k(k-1)s-1 = k{1 + (k-1) + (k-1)2 + . . . + (k-1)s-1} = {k(k-1)s-2}/(k-2). (b) ? Petersen Graph  使用字型簡報設計範本投影片標題 _6hlfuhlfu  !"#%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)PicturesFCurrent UserSummaryInformation(hRPowerPoint Document($ZDocumentSummaryInformation8