GraphTheory离散数学、图论、双语.ppt

1、Graph TheoryChapter 1 An Introduction to Graphs,大葉大學資訊工程系黃鈴玲,Ch1-2,Outline,1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs,Ch1-3,Graph Theory 的起源,1736, Euler sol

2、ved the Knigsberg Bridge Problem (七橋問題),Q: 是否存在一 種走法，可以走過每座橋一次，並回到起點？,(Ch7 Euler graph),Ch1-4,Knigsberg Bridge Problem,Ans: 因為每次經過一個點，都需要從一條邊進入該點，再用另一條邊離開，所以經過每個點一次要使用掉一對邊。 每個點上連接的邊數必須是偶數才行 此種走法不存在,Q: 是否存在一種走法，可以走過每條邊一次，並回到起點？,Ch1-5,An elementary example of graphs,4 students: A, B, C, D 4 positions:

3、 FF, SC, W, BS 四人各有喜好的工作：(如下圖，連線表示有興趣),Q: Can all four students find jobs they like?,Ans: No,(Ch6 Matching),Ch1-6,Definition of a graph,A graph G is a finite nonempty set V(G) of vertices (also called nodes, 點) and a (possibly empty) set E(G) of 2-element subsets of V(G) called edges (or lines, 邊).

4、V(G) : vertex set of G (只有一個 G 時常簡寫為 V) E(G) : edge set of G (只有一個 G 時常簡寫為 E) 常見的 edge 表示法: u, v = v, u = uv (or vu) 當邊有方向性時稱 G 為 directed graph (digraph),Ch1-7,Example,A graph G=(V,E), where V=u, v, w, x, y, z E=u,v, u,w, w,x, x,y, x,z E=uv, uw, wx, xy, xz G 的 diagram表示法:,Ch1-8,u, v : vertices of a

5、 graph G u and v are adjacent in G if uv E(G)( u is adjacent to v, v is adjacent to u) e=uv (e joins u and v) (e is incident with u, e is incident with v),Adjacent and Incident,Ch1-9,Graphs types,undirected graph: (simple) graph: loop (), multiedge () multigraph: loop (), multiedge () Pseudograph: l

6、oop (), multiedge (),Ch1-10,order and size,The number of vertices in a graph G is called its order (denoted by |V(G)| ). The number of edges is its size(denoted by |E(G)| ). Proposition 1:If |V(G)| = p and |E(G)| = q, then A graph of order p and size q is called a (p, q) graph.,Ch1-11,Application of

7、 graphs,一群人間兩兩互相認識或不認識(i.e., 沒有A認識B但B不認識A的情形)，在安排一張圓桌的晚餐座位時，是否存在一種排法能讓坐在一起的人都相互認識？ eg. Tom, Dick know Sue, Linda. Harry knows Dick and Linda. ,acquaintance graph:(連線表示認識),(Ch8 Hamiltonian graph),Q: 圖中是否有一個通過 所有點的cycle?,Ch1-12,eg. Animals: A, B, C, D, E AC 不能與 BD 同區， E不能與其他動物同區,Application of graphs,

8、動物園要用圍牆劃分區域，避免同區的動物互相捕食，至少需分多少區？,Q: 將圖形的點著色 (一色表示一區)， 若相鄰兩點需塗不同色， 最少需多少顏色才夠？,Ans: 3 色 3 區,(Ch 10 Graph Coloring),Ch1-13,Homework,Exercise 1.1: 1, 2, 3, 4,Ch1-14,Outline,1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 C

9、ut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs,Ch1-15,1.2 The degree of a vertex,Definition. For a vertex v of G, its neighborhood N(v) = u V(G) | v u E(G) . The degree of vertex v isdeg(v) = | N(v) |.,N(u) = x, w, v, N(y)= ,deg(u) = 3, deg(y) =0,Ch1-16,Notes,If |V(G)| = p, then0 deg(v) p-1

10、, v V(G). If deg(v) = 0, then v is called an isolated vertex (孤立點). v is an odd vertex if deg(v) is odd.v is an even vertex if deg(v) is even.,Ch1-17,Handshaking theorem,Theorem 1.1 (Handshaking theorem)Let G be a graph,pf. 在計算degree總和時，每條邊會被計算兩次。,Example,Ch1-18,Handshaking theorem,Corollary 1.1 Eve

11、ry graph contains an even number of odd vertices.,pf. If the number of vertices with odd degree is odd, then the degree sum must be odd. ,Ch1-19,Regular graph,Definition. A graph G is r-regular if every vertex of G has degree r. A graph G is regular if its r-regular for some r.,2-regular,Note. There

12、 is no 1-regular graph or 3-regular graph of order 5. (by Corollary 1.1),Example,Ch1-20,Complement,Definition. The complement G of a graph G is a graph with V(G) = V(G), and uv E(G) iff uv E(G).,Ch1-21,Application of degree,Q: n people. (n 2)Is it possible that every two of them are acquainted with

13、a different number of people in the group?(Suppose if A knows B, then B knows A.),A: Consider the acquaintance graph。 若任兩人所認識的人數不等， 表示圖形中所有點的 degree 都不相等。 n 點的圖形中， degree 只可能是 0, 1, , n-1 (共 n 種)， 必有一點 x 的 degree 為 0，另一點 y 的 degree 為 n-1， 也就是 x 不認識 y ，但 y 認識 x ，矛盾。,Ch1-22,Exercise 1 Prove that every

14、 graph of order n 2 has at least two vertices with the same degree.,pf. If not, then there exist vertices x and y with deg(x) = 0 and deg(y) = n-1. Its impossible.,(Hint. The problem in previous page.),Ch1-23,Exercise 9. Every vertex of a graph G of order 14 and size 25 has degree 3 or 5. How many v

15、ertices of degree 3 does G have?,sol. Suppose there are x vertices of degree 3, then there are 14-x vertices of degree 5. |E(G)| =25 degree sum=50 3x + 5(14-x) = 50 x = 10,Ch1-24,Exercise 10. A graph G of order 7 and size 10 has six vertices of degree a and one of degree b. What is b?,sol. 6a + b =

16、20 (a, b) = (0, 20) () (1, 14) () (2, 8) () (3, 2) () a=3, b=2.,Ch1-25,Homework,Exercise 1.2: 4, 7, 11,Ch1-26,Outline,1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digr

17、aphs,Ch1-27,1.3 Isomorphic graphs,v1,v3,v4,v5,u1,u2,u3,u4,u5,G1,G2,G1 and G2 are the same (after moving some vertices).,Ch1-28,Isomorphic,Definition.Two graph G1 and G2 are isomorphic (同構) (denoted by G1 G2 ) if there is a 1-1 and onto function from V(G1) to V(G2) such that uv E(G1) iff f (u) f (v)

18、E(G2). (對應過去後，仍能保持兩點間相連與否的關係) The function is called an isomorphism. In previous page, f (vi) = ui for each i.,Ch1-29,Isomorphic,Definition.Two graph G1 and G2 are equal if V(G1) = V(G2) and E(G1) = E(G2).,1 跟 2 是判斷兩個圖是否 isomorphic 的初步檢查條件,Proposition. 1. If G1 G2, then |V(G1)| = |V(G2)| and |E(G1)|

19、 = |E(G2)|. 2. If G1 G2 and is an isomorphism from V(G1) to V(G2), then,(So the degree sequences of these graphs must be the same.),Ch1-30,Definition.Trivial graph: The graph of order 1.,Exercise 1Find two nonisomorphic 3-regular graphs of order 6 and size 9.,Sol.,Ch1-31,Exercise 8Determine whether

20、the graphs G1 and G2 shown below are isomorphic.,G1,G2,Ans: No,Ch1-32,Note. 1. 要證明 G1 G2 時，必須給出 isomorphism f 這個函數，也就是必須明確說出 G1 的哪一點 對應 G2 的哪一點。 2. 要證明 G1 G2 時，只需說明原因 (如：點數 邊數不同，degree sequence不同，或圖形結 構哪裡不同等)。,Ch1-33,Homework,Exercise 1.3: 4, 7, 9,Ch1-34,Outline,1.1 What is a graph? 1.2 The Degree o

21、f a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs,Ch1-35,1.4 Subgraphs,Definition.A graph H is a subgraph of a graph G if V(H) V(G) and E(H) E(G). (denote H G), G,Example,Ch1-36,Definition.Let S V(G),

22、 S . The subgraph induced by S is the maximal subgraph of G with vertex set S. (denoted by ) A subgraph H of a graph G is a vertex-induced subgraph if H= for some S V(G).,Induced Subgraph,H is not an induced subgraph of G.,H xw才是,Ch1-37,The deletion of vertices,Definition.Let S V(G). The graph G-S =

23、 . If S=v, then we write G-v instead.,Let S=x,u ,G-S,v,w,y,Ch1-38,Definition.Let X E(G), X . The subgraph induced by X is the minimal subgraph of G with edge set X. (denoted by ) A subgraph H of a graph G is an edge-induced subgraph if H= for some X E(G).,Edge Induced Subgraph,Let X=uv,vw ,Ch1-39,De

24、finition.A subgraph H G is a spanning subgraph of G if V(H) = V(G).,Definition.H = G + uv, uw means E(H) = E(G) uv, uw , where uv, uwE(G).,Exercise 5If H=, does it follows that H=?,No,Ch1-40,Homework,Exercise 1.4: 1, 3,Exercise 6Let G be a labeled (p, q) graph. How many different edge-induced subgra

25、phs does G have?,Note. 不同的邊集合會造出不同的 edge-induced subgraph,Ans. 2q-1 ( X E(G) 且 X , 共有 2q-1 種 X ),Ch1-41,Outline,1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs,C

26、h1-42,1.5 Degree Sequence,Definition.Let G=(V, E), V=v1, v2, , vp. Then s: deg(v1), deg(v2), , deg(vp) is called a degree seqence of G. (For convenient, assume s is nonincreasing, then s is unique.),s: 3, 3, 2, 1, 1, 0,Ch1-43,If d1, d2, , dp is the degree sequence of some graph, then and 0 d i p-1 i

27、. For a given sequence s: d1, d2, , dp of integers such that and 0 d i p-1 i, there is no guarantee that s is the degree sequence of some graph. ex. s: 5, 5, 3, 2, 1, 0,Note,(Moreover, d1 p is impossible. ),( p-1 and 0 cant exist at the same time),Ch1-44,Definition.We call a sequence of nonnegative

28、integers graphical if it is the degree sequence of some graph.,Theorem 1.2 (Havel-Hakimi)Let s be a sequence: d1, d2, , dp, where di N, i. Let s1 be the sequence: Then s is graphical iff s1 is graphical.,(Note. s1 即是把 d1 扣掉，剩下的前 d1 項各減 1。),Ch1-45,Proof of Thm 1.2:,( ) If s1 : is graphical graph G1 s

29、.t. s1 is the degree sequence of G1,d2,d3,dd1+1,dd1+2,dp, s : d1, d2, , dp is graphical.,Ch1-46,( ) If s : d1, d2, , dp is graphical graph G s.t. s is the degree sequence of G with deg(vi) = di for 1 i p, and is maximum.,Proof of Thm 1.2: (continued),Claim: v1v2, v1v3, , v1vd1+1 E(G),i.e.,If the cla

30、im is true, then G-v1 is a graphwith degree sequence s1 s1 is graphical.,Ch1-47,If not, there must be two vertices vj and vk (j dk s.t. v1vk E(G) but v1vj E(G).,Claim: v1v2, v1v3, , v1vd1+1 E(G)Proof:,Since dj dk, vnV(G) s.t. vjvn E(G), vkvn E(G).,Let G2 = G - v1vk, vjvn + v1vj, vkvn,G2 has degree s

31、eq s but larger , ,Ch1-48,Algorithm,s: d1, d2, , dp sequence of integers To determine whether s is graphical: (1) If di=0, i, then s is graphical. If di0 for some i, then s is not graphical. Otherwise, go to (2). (2) Reorder s to a nonincreasing sequence if necessary. (3) Let s = s1, (s1的產生方式同 Thm 1

32、.2), return to (1).,Ch1-49,Example 1,s: 4, 4, 3, 3, 2, 2 s1: 3, 2, 2, 1, 2 (delete the first 4) s1: 3, 2, 2, 2, 1 (reorder) s2: 1, 1, 1, 1 (delete 3) s3: 0, 1, 1 (delete the first 1) s3: 1, 1, 0 (reorder) s4: 0, 0 (delete the first 1) s is graphical,Ch1-50,Draw the graph,s: 4, 4, 3, 3, 2, 2 s1: 3, 2

33、, 2, 1, 2 s1: 3, 2, 2, 2, 1 s2: 1, 1, 1, 1 s3: 0, 1, 1 s3: 1, 1, 0 s4: 0, 0 s is graphical,G,Ch1-51,Example 2,s: 5, 4, 3, 2, 1, 1 s1: 3, 2, 1, 0, 0 (delete 5) s2: 1, 0, -1, 0 (delete 3) s is not graphical,Ch1-52,Definition.Let G=(V,E), the set D (G)=deg(v) | vV is called the degree set of G.,Ex.s: 4

34、, 4, 3, 3, 2, 2D (G)= 2, 3, 4 (去掉順序及重複性),Kapoor et al 7 showed thatEvery finite set of nonnegative integers is the degree set of some graph.,Ch1-53,Exercise 6 Let |V(G)|=12, D (G)4, 5, 6.Show that G contains either (i) at least 4 vertices of degree 4, (ii) at least 6 vertices of degree 5, (iii) at l

35、east 5 vertices of degree 6.,Proof If not, deg 4 點數 3 deg 5 點數 5 deg 6 點數 4,3+5+4=12 ,deg 4 點數 = 3 deg 5 點數 = 5 deg 6 點數 = 4, degree總和不為偶數 ,Ch1-54,Exercise 8 Let G be a graph with D (G) = m, n, where G contains m vertices of degree m and n vertices of degree n.Prove that if G contains an odd vertex,

36、 then every vertex of G is odd.,Proof degree sum = m2 + n2 If m is odd then n must be odd, and vice versa.,Ch1-55,Homework,Exercise 1.5:1, 3, 5, 7, 9,Ch1-56,Outline,1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-V

37、ertices and Bridges 1.8 Special graphs 1.9 Digraphs,Ch1-57,1.6 Connected graphs,Definition.A walk in a graph G is an alternating sequence W: v0, e1, v1, e2, v2, , vn-1, en, vn (n0)of vertices and edges, where ei=vi-1vi, i.( 故 W 中的 ei 可省略) (W is also called a v0 -vn walk) W is said to have length n.

38、A trail is a walk without repeated edges. A path is a walk without repeated vertices.,walk: x, w, v, x, w trail: x, w, v, x, y path: x, w, v,Ch1-58,Theorem 1.3Every u-v walk in a graph contains a u-v path.,Proof. 去掉重複的點或邊即可,Definition(1) A cycle is a walk v0, v1, v2, , vn-1, vn in which n3, v0 = vn,

39、 and v1, v2, , vn-1, vn are distinct. (n-cycle) (2) A u-v walk is closed if u=v. (closed walk) (3) A nontrivial closed trail is called a circuit.,Ch1-59,Definition(1) Let u,vV(G), u is connected to v if u-v path. (2) G is connected if u is connected to v u,v V(G), otherwise, G is called disconnected

40、. (3) A subgraph H of G is a component of G if H is a maximal connected subgraph of G. (4) The number of components of G is denoted by k (G).,Note. “is connected to” is an equivalence relation,Ch1-60,Exercise 7 Let G be a graph. |V(G)|=p, p2.Suppose d(G) (p-1)/2.Prove that G is connected.,Proof If G

41、 is disconnected, since d(G) (p-1)/2, each component must contain (p+1)/2 vertices. ,Ch1-61,Exercise 10 Prove that if a graph G has a closed walk of odd length, then it has a cycle of odd length.,(1) 若點沒有重複此walk本身即odd cycle,(2) 若點 x 重複出現,設此walk P: v0=x, v1, v2, , vi=x, vi+1, , vn, v0=x 其中 vi 是從v0走到v

42、n的過程中， x 最後一次出現 則可將P分成兩個closed walk:P1: v0=x, v1, v2, , vi=xP2: vi=x, vi+1, , vn, v0=x 兩者必有一為odd length 取此一walk仿照上述方法再拆，最後必可得一odd cycle.,Proof.,Ch1-62,Exercise 11 Show that a graph G contains (1) a path of length d(G), and (2) a cycle of length at least d(G) +1 if d(G) 2.,Proof: Let P: v0, v1, , vk

43、be a longest path of G.,Then deg(v0) d(G), and N(v0 ) V(P) for otherwise P is not longest.,It follows that the length of P is at least d(G).,Let vn be the vertex of P with v0vn E(G) and n is largest.,Since N(v0) V(C),It is clear that the length of C is at least d(G) +1.,If d(G) 2, then n 2. Let C: v

44、0, v1, , vn, v0.,Ch1-63,Homework,Exercise 1.6:1, 2, 3, 4, 5, 8, 9,Ch1-64,Outline,1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Graphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs,Ch1-65,1.7 Cut Vertices and Brid

45、ges,Definition 1 A vertex v in a graph G is called a cut-vertex if k(G - v) k(G). So v is a cut-vertex in a connected graph G if G - v is disconnected.,Ch1-66,e.g. G : cut-vertex： v3, v5 cut-edge： v5v6,v1,v5,v3,v2,v4,v6,Ch1-67,Definition 2 An edge e in a graph G is called a bridge (cut-edge) if k(G

46、- e) k(G). e.g. The graph in previous page: v5v6 is a bridge. Note. (1) if v is a cut-vertex of a connected graph G, then k(G - v) 2 (2)If e is a bridge of a connected graph G, then k(G - e) =2,Ch1-68,Proof. () Let e be a bridge of G. Suppose e =uv, and assume, to the contrary, that e lies on a cycl

47、e C：u, v, w, , x, u. Then C - e：v, w, , x, u is a u-v path of G - e. Claim: G - e is connected. (If the claim is true, ),Theorem 1.4 An edge e of a connected graph G is a bridge iff e does not lie on a cycle of G.,(e is not a bridge),Ch1-69,(Proof of above Claim) Let u1, v1 V(G-e)=V(G) G is connecte

48、d u1-v1 path P in G. If e P, then P is also a path in G-e u1-v1 path in G-e If e P, then (PC)-e is a u1-v1 walk in G-e u1-v1 path in G-e Therefore, G-e is connected.,Ch1-70,() Suppose e=uv is an edge that lies on no cycle of G. Then G-e contains no u-v path. Otherwise, if P is a u-v path in G-e, the

49、n P uv is a cycle containing e, .,Ch1-71,Definition 3 A nontrivial connected graph without a cut-vertex is called a nonseparable graph. A block B of a nontrivial connected graph G is a subgraph of G that itself is a maximal nonseparable graph.,# of vertices 2,Ch1-72,e.g. G,v1,G has 3 blocks： , , ,v3

50、,v2,v4,v5,v6,Ch1-73,Note: 1. A block is necessarily an induced subgraph. 2. The blocks of a graph produce a partition of the edge set of the graph. 3. Every two blocks have at most one vertex in common. 4. If v V(B1)V(B2), where B1, B2 are block of G, then v is a cut-vertex. 5. If G is nonseparable,

51、 then G is a block.,Ch1-74,Definition A block of a graph G that contains exactly one cut-vertex of G is called an end-block of G. Theorem 1.5 Let G be a connected graph with at least one cut-vertex. Then G has at least two end-blocks. (介紹到tree時再証),Ch1-75,Homework,Exercise 1.7: 1, 2, 4, 5, 6, 7,Ch1-7

52、6,Sol： (a) If G has a bridge e, assume G = G1G2 e, where e=ab, G1 and G2 are the two components of G-e.,HW3 (a) Show that if G is an r-regular connected graph, where r is even, then G contains no bridges. (b) Is the statement in (a) still true if r is odd?,Ch1-77,Consider the subgraph G1 v V(G1), de

53、gG (v)= r if v a r-1 if v=a r is even is odd ,1,Ch1-78,(b) No, e.g. r = 1 G： r = 3 G：,Ch1-79,HW4 Find a counterexample (a) If G is a connected graph that contains only even vertices, then G contains no cut-vertices. Sol.,Ch1-80,HW8 A connected graph G contains three distinct vertices u, v and w with

54、 the property that every u-w path in G contains v. Show that v is a cut-vertex. Proof. Consider G-v, there is no u-w path in G-v. k(G-v)1 = k(G) v is a cut-vertex.,Ch1-81,Outline,1.1 What is a graph? 1.2 The Degree of a Vertex 1.3 Isomorphic Graphs 1.4 Subgraphs 1.5 Degree Sequences 1.6 Connected Gr

55、aphs 1.7 Cut-Vertices and Bridges 1.8 Special graphs 1.9 Digraphs,Ch1-82,1.8 Special Graphs,Def 1. Complete graph (Kp) : p vertices, p 1 , uv, u,v V (Kp) Note. (1) Kp is (p-1) regular (2) Kp has edges.,Ch1-83,Def 2. A path of order n (denoted by Pn) : a path of n vertices. (length n-1) Def 3. n-cycl

56、e (denoted by Cn) : a cycle of n vertices, n 3. even cycle : a cycle of even vertices odd cycle : a cycle of odd vertices,Ch1-84,Def 4. A graph G is bipartite if V(G)=V1 V2 s. t. every edge of G joins a vertex of V1 and a vertex of V2. ( (V1, V2) is called a bipartition of G. ),e.g.,G:,v1,redrawn of

57、 G,Ch1-85,Def 5. (先補充) If u-v path in G , the distance between u and v, denoted by d(u, v), is the length of shortest u-v path. If u-v path in G, d(u, v) = . e.g. 上圖 G 中 d(v1, v4) = 1 d(v1, v6) = 2 d(v4, v6) = 3,Ch1-86,Thm 1.6 A nontrivial graph G is bipartite iff G has no odd cycles. Pf: ) Assume G

58、 is a bipartite graph with bipartition (V1,V2). If Cn : v1,v2,vn,v1 is any cycle of G. (n3) Suppose v1V1, then v2V2, v3V1, v4V2, , vnV2 Hence n must be even, G has no odd cycles.,Ch1-87,) It clearly suffices to prove the converse of connect graphs. Let G be a connected graph without odd cycles. Choose any vertex uV(G), define V1 = wV(G) | d(u, w) is even V2 = wV(G) | d(u, w) is odd (Show that (V1, V2) is a bipartition of G).,Ch1-88,Choose an