20161114 path and circuit 含H道路回路定理證明,交錯點互斥,及第二章習(xí)題2.3.4.5.7.8.10.11答案.pptx

1、,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Discrete Mathematics,Graph: Path and Circuit,Yuan Luo,Computer Science and Engineering Department,Shanghai Jiao Tong University,Fall 2016,Yuan Luo Computer Science and Engineering Department Shanghai,Ex

2、ercises,Discrete Mathematics,Content,Chordal Circuit, Bipartite Graph and Connected Component Euler and Hamilton Paths Euler Paths/Circuits Hamilton Paths/Circuits Peterson Graph Exercises,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan

3、 Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,1,2,3,4,Path and circuit: Sequence of vertices ? Not good Sequence of edges ? Not good Sequence of vertices and edges ? GOOD ! Path always has a direction.,Simple (簡單) and Primary (初級) Here simple has no relation with sim

4、ple graph ! Simple: each edge cannot appear more than once Primary: each vertex cannot appear more than once,Basic Concepts,Path and circuit:,Chordal Circuit, Bipartite Graph and Connected Component,Chordal circuit (krdl 帶弦回路): Let be a circuit of graph with the number of vertices greater than 3. If

5、 and are not adjacent in and but adjacent in , then ( , )is called a chord of . Furthermore, is called a chordal circuit. (See Dais book pp.11 Example 2.1.3),Bipartite graph (二分圖): (e.g. LDPC) A simple graph is called bipartite if its vertex set can be partitioned into two disjoint sets 1 and 2 such

6、 that every edge in the graph connects a vertex in 1 and a vertex in 2 . (See textbook pp.602 Definition 5),Connected component (極大連通子圖、連通支): A connected component of a graph is a connected subgraph of that is not a proper (真) subgraph of another connected subgraph of . (See textbook pp.625),Euler a

7、nd Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Chordal Circuit, Bipartite Graph and Connected Component,Chordal Circuit Property,Property. In a simple graph , if d( )3 for each vertex , then there exists a chordal circuit

8、. （僅用到極長初級道路端點性質(zhì)） Proof. Let P be the longest 初級道路 (primary path: each vertex cannot appear more than once) in with start point 0 and end point . Then P cannot be expanded from 0 and , according to “l(fā)ongest (向外延不行) and primary (向內(nèi)延不行)”. Since d( 0 )3, another two neighbors of 0 must be also in P, th

9、en it is easy to construct a chordal circuit.,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Chordal Circuit, Bipartite Graph and Connected Component,Bipartite Graph (Example), 6 is bipartite, as shown in Figure be

10、low, because its vertex set can be partitioned into two sets 1 = 1 , 3 , 5 2 = 2 , 4 , 6 , and every edge of 6 connects a vertex in 1 and a vertex in 2 .,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Chordal Circu

11、it, Bipartite Graph and Connected Component,Fig. Showing that 6 is bipartite,A circuit here should have even number of edges !,Bipartite Graph (Example), 3 is not bipartite, to verify this, note that if we divide the vertex set of 3 into two disjoint sets, one of the two sets must contain two vertic

12、es. If the graph were bipartite, these two vertices could not be connected by an edge, but in 3 each vertex is connected to every other vertex by an edge.,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Chordal Circ

13、uit, Bipartite Graph and Connected Component,Fig. 3,Connected Component (example),What are the connected components of the graph H shown in Figure below?,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Chordal Circu

14、it, Bipartite Graph and Connected Component,Solution: The graph H is the union of three disjoint connected subgraphs 1 , 2 ,and 3 . These three subgraphs are the connected components of .,A simple graph satisfying, 1 2 (1)(2),must be connected ?,Euler Paths/Circuits,Content,Chordal Circuit, Bipartit

15、e Graph and Connected Component Euler and Hamilton Paths Euler Paths/Circuits Hamilton Paths/Circuits Peterson Graph Exercises,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,1,2,3,4,Hamilton Paths/Circuits,Chordal Circuit, Bipartite Graph and Connected C

16、omponent,Euler and Hamilton Paths,Peterson Graph,Eulers Classic Problem,Euler Paths/Circuits (undirected but connected graph),Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discr

17、ete Mathematics,Euler Paths/Circuits,Hamilton Paths/Circuits,Definition : An Euler circuit in a graph G is a simple circuit containing every edge of G. Definition : An Euler path in G is a simple path containing every edge of G,Q: Which of the undirected graphs in figure below have an Euler circuit?

18、 Of those that do not, which have an Euler path?,Euler Paths/Circuits,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Euler Paths/Circuits,Hamilton Paths/Circ

19、uits,Q: Which of the undirected graphs in figure below have an Euler circuit? Of those that do not, which have an Euler path?,Solution: The graph 1 has an Euler circuit, for example, a,e,c,d,e,b,a. Neither of the graphs 2 or 3 has an Euler circuit. However, 3 has an Euler path, namely, a,c,d,e,b,d,a

20、,b. 2 does not have an Euler path.,Note: The problems of Euler path in pseudograph are equivalent to the cases in multigraph. So sometimes we only talk about multigraph.,Euler Paths/Circuits,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Yu

21、an Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Euler Paths/Circuits,Hamilton Paths/Circuits,The sufficient and necessary condition of the existence of Euler circuit : A connected multigraph with at least two vertices has an Euler circuit if and only if each of its v

22、ertices has even degree.,The sufficient and necessary condition of the existence of Euler path: A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.,Euler Paths/Circuits,Chordal Circuit, Bipartite Graph and Connected Component,Eu

23、ler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Euler Paths/Circuits,Hamilton Paths/Circuits,Proof. Main Idea 1. For any given path P, each inner vertex (not the start , not the end) consumes even degree. If P is not

24、a circuit, the start and the end consume odd degree respectively. (歐拉回路的充要條件證明基礎(chǔ)) Main Idea 2. For necessary part, all of the degrees or equivalently all of the edges in the graph are exhausted.,Euler Paths/Circuits Main Idea 3. For sufficient part, Construction of an Euler circuit (See Textbook pp.

25、636, Dais book pp.16 Example 2.3.1) i.e. consider the sufficient part of the proof. Construction of an Euler path (See Textbook pp.637, Dais book pp.16 Corollary 2.3.1) method: adding and then deleting, also refer to Example 2.3.3 in Dais book. The degrees of vertices except for the start vertex and

26、 the last vertex are all even in a Euler path ! (See Dais book Example 2.3.2, 2.3.3, 2.3.4),Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Euler Paths/Circui

27、ts,Hamilton Paths/Circuits,A Generalization of the Euler Theorem.,Content,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Euler Paths/Circuits,Hamilton Paths/

28、Circuits,Chordal Circuit, Bipartite Graph and Connected Component Euler and Hamilton Paths Euler Paths/Circuits Hamilton Paths/Circuits Peterson Graph Exercises,1,2,3,4,Hamiltons A Voyage Round the World Puzzle.,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peters

29、on Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Euler Paths/Circuits,Hamilton Paths/Circuits,Hamilton Paths/Circuits (undirected but connected),Definitions: A simple path in a graph G that passes through every vertex exactly once is called a Hami

30、lton path, and a simple circuit in a graph G that passes through every vertex exactly once is called a Hamilton circuit. That is , the simple path 0 , 1 , ， 1 , in the graph G =(V, E) is a Hamilton path if = 0 , 1 , , 1 , and for 00) is a Hamilton circuit if 0 , 1 , ， 1 , is a Hamilton path.,Note: T

31、he problems of Hamilton path in simple graph are equivalent to the cases in pseudograph. So we only need to consider simple graph here !,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Sha

32、nghai,Discrete Mathematics,Euler Paths/Circuits,Hamilton Paths/Circuits,Hamilton Paths/Circuits,Q: Which of the simple graphs in Figure below have a Hamilton circuit or, if not, a Hamilton path?,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercise

33、s,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Euler Paths/Circuits,Hamilton Paths/Circuits,Hamilton Paths/Circuits,Solution: has a Hamilton circuit: a, b, c, d, e, a. There is no Hamilton circuit in 2 (this can be seen by noting that any circuit containing ever

34、y vertex must contain the edge a,b twice), but 2 does have a Hamilton path, namely, a, b, c, d. 3 has neither a Hamilton circuit nor a Hamilton path, because any path containing all vertices must contain one of the edges a, b, e,f, and c,d more than once.,The sufficient condition of the existence of

35、 Hamilton path (See Dais book pp.18 Theorem 2.4.1 improved) The sufficient condition of the existence of Hamilton circuit (See Dais book pp.19 Corollary 2.4.1 improved) The closure of a graph. The sufficient and necessary condition of the existence of a Hamilton circuit is described by the closure o

36、f a graph (See Dais book pp.20 Theorem 2.4.2),Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Euler Paths/Circuits,Hamilton Paths/Circuits,Hamilton Paths/Circ

37、uits,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Euler Paths/Circuits,Hamilton Paths/Circuits,Hamilton Paths/Circuits,The sufficient condition of the exis

38、tence of Hamilton Path:,If G is a simple graph with n3 such that deg(u)+deg(v)n-1 for every pair of nonadjacent vertices u and v in G, then G has Hamilton Path.,Corollary. If G has no Hamilton Path, then there exists a pair of nonadjacent vertices u and v, such that deg(u)+deg(v) n-1.,Proof of the s

39、ufficient condition of the existence of Hamilton Path. (哈密頓道路存在的充分條件證明),Step 1: G is connected. Otherwise, for nonadjacent vertices u and v of different connected components, contradiction: deg(u)+deg(v) 1 1 + 2 1 2. Step 2: For longest junior (i.e. primary) path 極長初級道路 =( 1 , ), Case 1: if =, finis

40、h. Case 2: if , there is a junior circuit 初級回路 C including P. Otherwise, 1 and are nonadjacent and then (兩端在P外無相鄰點，且交錯點互斥見下頁圖) contradiction: deg( 1 )+deg( ) ( 1 鄰點)+ ( 1 鄰點前點)1( ) = 12. Step 3: In Case 2, expanding the junior circuit C since G is connected: 若非遍歷，則再刪邊打開、擴點 New P will include all of

41、the vertices.,Remark 1,花絮小知識-交錯點互斥性質(zhì)圖解 哈密頓道路、回路存在的充分性條件證明基礎(chǔ),若不存在初級回路 C 包含該極長初級道路 P，則端點 和 互不相鄰。又因極長道路兩端點的鄰點都在P內(nèi)， 所以有交錯點互斥性質(zhì)( 即若 同 相鄰，則 , 不會同 相鄰）: deg( 1 )+deg( ) ( 1 鄰點)+ ( 1 鄰點前點)1( ) = 1.,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Eule

42、r Paths/Circuits,Hamilton Paths/Circuits,Hamilton Paths/Circuits,Remark 2,Proof of the ORE sufficient condition of the existence of Hamilton Circuit (哈密頓回路存在的充分條件證明) According to the former result, there exists a Hamilton path H. If there is no Hamilton circuit, let 1 and be the nonadjacent start po

43、int and end point of H. Then it is easy to see from the“交錯點互斥圖解” that ( 1 , ) and ( ,1 , ) cannot be edges at the same time. Thus deg( 1 )+deg( ) ( 1 鄰點)+ ( 1 鄰點前點)1( ) =1. which is a contradiction. Proof of the sufficient and necessary condition of the existence of Hamilton Circuit: Closure in one

44、step and then Closure in full steps.,Exercises,Example 2.4.5 (Dais book) H path and double counting,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Solution,S

45、ince 3, for any two nonadjacent vertices and , there exists k such that ( , ) ( , ) since any two of them know all of the others. Thus, ( )+ 2 +1=1. So there is H circuit., 對 和 的度各貢獻一次,Exercises,Example 2.4.6 (Dais book) H circuit and bipartite graph,Chordal Circuit, Bipartite Graph and Connected Co

46、mponent,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,A,B,A,A,A,A,A,B,B,B,B,B,B,Since the graph is bipartite, if there is H circuit, it should have even vertices, but =13 which is a contradiction. So there is no H

47、 circuit.,Exercises,Example 2.4.7 (Dais book: 4-Color Map) H circuit and planar graph If there is an H circuit in a planar graph, one can use four colors to distinguish the regions. Proof. Since there is no vertex inside the H circuit, any three regions inside the circuit are not pairwise adjacent.

48、So one can use two colors to distinguish the inner regions. Similarly, So one can use another two colors to distinguish the outer regions.,Chordal Circuit, Bipartite Graph and Connected Component,Euler and Hamilton Paths,Peterson Graph,Exercises,Yuan Luo Computer Science and Engineering Department S

49、hanghai,Discrete Mathematics,Peterson Graph,The degree of all vertices in a Peterson graph is 3. (See textbook pp.646 Exercise 46) The nonexistence of Euler circuit The nonexistence of Euler path The existence of Hamilton path,The nonexistence of Hamilton circuit,Chordal Circuit, Bipartite Graph and

50、 Connected Component,Peterson Graph,Euler and Hamilton Paths,Exercises,Yuan Luo Computer Science and Engineering Department Shanghai,Discrete Mathematics,Fig. Peterson graph,Some Homework,2. Chinese textbook p35 習(xí)題二第二題,若G不連通，證明 G 必連通。 證明：任取結(jié)點 1 , 2 。 若 1 , 2 在G中不相鄰，則 1 , 2 在 G 中相鄰。 若 1 , 2 在G中相鄰，取G中

51、另一連通支上的點 3 ； 1 , 3 在G中不相鄰但在 G 中相鄰；同理 2 , 3 在G中不相鄰但在 G 中相鄰。因此，道路 ( 1 , 3 ) ( 2 , 3 )使 1 , 2 在 G 中相通。,3. Chinese textbook p35 習(xí)題二第三題,設(shè) 1 , 2 均為最長，長度為。反證，若 , 不相交，找到兩道路間最近的兩點： 1 1 , 2 2 . 1 分割 1 后留過半長 2 的一段， 2 分割 2 后留過半長 2 的一段， 這兩段經(jīng) 1 , 2 間的通路鏈接，得到長于的道路。矛盾。,4. Chinese textbook p35 習(xí)題二第四題,Lemma,Solution,

52、5a. Chinese textbook p35 習(xí)題二 5a提示,For each edge e=( , ) , if ( )=, then ( ) since there is no triangle in the simple graph with edges and vertices. So ( )+ , =( , ) ( )+ , 2 () = =( , ) ( )+ 注：積累了 ( )個 ( ).,5b. Chinese textbook p35 習(xí)題二 5b提示,2= () 1+ + 1 =2 2 2,one point with max degree k,k points co

53、nnected with the maximal one (no triangle),other n-k-1 points,7. Chinese textbook p36 習(xí)題二第七題: If there is H path in G, show that the number of components in + where is a set of vertices.,Solution,Since and =() , the number of components in the number of components in . It is easy to verify that the

54、number of components in 1+|.,8. Chinese textbook p36 習(xí)題二第八題:,Solution,If G has no Hamilton circuit, then there exist two nonadjacent vertices and such that ( )+ 1. Let G=G , then , () = () + ( )+ ( ) G握手定理及完全圖 3 2 +(1) () = , () + ( )+ ( ) 3 2 + 1 +(1) = 1 2 +2 握手定理 2= () 1 2 +2 1 2 1 2 +1 contradic

55、tion.,10. Chinese textbook p36 習(xí)題二第十題: this is a problem of Hamilton circuit, which can be proved by using the sufficient condition as in OREs theorem.,Solution,Since 4, for any two nonadjacent vertices and , 1: there exists k such that ( , ) ( , ) since any two of them know all of the others; 2: si

56、milarly, there exists such that ( , ) ( , ) . Thus, ( )+ 2 +1+1=. ., 對 和 的度各貢獻一次, 對 和 的度各貢獻一次,11. Chinese textbook p36 習(xí)題二第十一題: this is also a problem of Hamilton circuit, which can be proved by using the sufficient condition as in OREs theorem.,Solution,將這任意給定的條互不相鄰邊，分別壓縮為個不同的點。 那么簡單圖中就少了個點: =； 同時最

57、小度至多減少: 。 因此 + 2 = 2 . 然后利用 OR E s theorem證實 存在 回路。最后將這個壓縮的點還原回去， 就存在包含任意給定的條互不相鄰邊的 回路。,Supplementary 1. Shortest-Path Problem (最短路徑) (in connected weighted simple graph, 6th Edt. English Textbook P649.),Minimum Spanning Tree: Weight on edge Huffman Tree: Weight on node and label on edge Shortest-Pa

58、th Problem: Weight on edge and node Traveling Salesman Problem: Hamilton circuit + Weight on edge Chinese Postman Problem: Euler circuit (with copy-edges in a clever manner)+Weight on edge,Relative Concepts:,Chinese postman problem remark: The problem of finding the minimum length, edge-covering tou

59、r of a graph G(N, A) with no restrictions placed on G other than that it be connected and undirected. The solution procedure consists of adding, in a judicious manner, artificial edges, parallel to the existing ones, to the original graph G to obtain a new graph G1(N, A1) on which an Euler tour can be drawn. T