复旦大学：《离散数学》PPT教学课件（赵一鸣）14/28

☆53.2 Hamilton paths (b)

❖5.3.2 Hamilton paths

Definition 20: A Hamilton paths is a path that contains each vertex exactly once. A Hamilton circuit is a circuit that contains each vertex exactly once except for the first vertex, which is also the last

❖ Definition 20: A Hamilton paths is a path that contains each vertex exactly once. A Hamilton circuit is a circuit that contains each vertex exactly once except for the first vertex, which is also the last

g Theorem 5.8: Suppose G(V,E that has a Hamilton circuit, then for each nonempty proper subset s of V(G), the result which o(G S)sS holds, where G-S is the subgraph of g by omitting all vertices of s from V(G). o(G-S)=1,|S b The graph G has not any Hamilton circuit if there is a nonempty purely subgraph s of G-a.d? G so that a(G-s)>s

❖ Theorem 5.8: Suppose G(V,E) that has a Hamilton circuit, then for each nonempty proper subset S of V(G), the result which (G￾S)≤|S| holds, where G-S is the subgraph of G by omitting all vertices of S from V(G). (G-S)=1，|S|=2 The graph G has not any Hamilton circuit, if there is a nonempty purely subgraph S of G so that (G-S)>|S|

Omit (b, h, i] from V, BO(G-s=4>3=S, The graph has not any Hamilton circuit g

❖ Omit {b,h,i} from V, ❖ (G-S)=4>3=|S|，The graph has not any Hamilton circuit

o If o(G-S)ss for each nonempty proper subset s of g. then g has a hamilton circuit or has not any Hamilton circuit 8 For example: Petersen graph

❖ If (G-S)≤|S| for each nonempty proper subset S of G, then G has a Hamilton circuit or has not any Hamilton circuit. ❖ For example: Petersen graph

oo Proof: Let C be a Hamilton circuit of G(V, E) Then o(c-sss for each nonempty proper subset s of v Why? .o Let us apply induction on the number of elements of s s=1, ☆ The result holds %o Suppose that result holds for sEk 冷Let|S|=k+1 .o Let S=s Utv), then SEk .o By the inductive hypothesis, a(C-sss 冷VCS)=V(Gs) %o Thus C-s is a spanning subgraph of G-s y Therefore olG-Sso(C-SSISVVVAV

❖ Proof: Let C be a Hamilton circuit of G(V,E). Then (C-S)≤|S| for each nonempty proper subset S of V ❖ Why? ❖ Let us apply induction on the number of elements of S. ❖ |S|=1, ❖ The result holds ❖ Suppose that result holds for |S|=k. ❖ Let |S|=k+1 ❖ Let S=S'∪{v}，then |S'|=k ❖ By the inductive hypothesis, (C-S')≤|S'| ❖ V(C-S)=V(G-S) ❖ Thus C-S is a spanning subgraph of G-S ❖ Therefore (G-S)≤(C-S)≤|S|

o Theorem 5.9: Let G be a simple graph with n vertices. where n>2 G has a hamilton circuit if for any two vertices u and y of g that are not adjacent, d(u)+d(v2n 8,d(u)=d(v) u and v are not adjacent, d(u)+d(v)=6<8 But there is a hamilton circuit in the graph Note: 1)ifG has a Hamilton circuit then g has a Hamilton path Hamilton circuit.v,v,v..v.v 1 Hamilton path:V1,V2, V3,.Vns 2)IfG has a Hamilton path, then G has a Hamilton circuit or has not any Hamilton circuit 7

❖ Theorem 5.9: Let G be a simple graph with n vertices, where n>2. G has a Hamilton circuit if for any two vertices u and v of G that are not adjacent, d(u)+d(v)≥n. n=8,d(u)=d(v)=3, u and v are not adjacent, d(u)+d(v)=6<8, But there is a Hamilton circuit in the graph. Note:1)if G has a Hamilton circuit , then G has a Hamilton path Hamilton circuit :v1 ,v2 ,v3 ,…vn ,v1 Hamilton path:v1 ,v2 ,v3 ,…vn , 2)If G has a Hamilton path, then G has a Hamilton circuit or has not any Hamilton circuit

corollary 1: Let G be a simple grap with n vertices. n>2.g has a hamilton circuit if each vertex has degree greater than or equal to n/2 g Proof: If any two vertices of G are adjacent then G has a Hamilton circuit V1V2,V3y…VnV1° .s If g has two vertices u and y that are not adjacent, then d(u+d(v2n. &By the theorem 5.9g has a hamilton circuit .&K has a hamilton circuit where n>3

❖ Corollary 1: Let G be a simple graph with n vertices, n>2. G has a Hamilton circuit if each vertex has degree greater than or equal to n/2. ❖ Proof: If any two vertices of G are adjacent ,then G has a Hamilton circuit v1 ,v2 ,v3 ,…vn ,v1。 ❖ If G has two vertices u and v that are not adjacent, then d(u)+d(v)≥n. ❖ By the theorem 5.9, G has a Hamilton circuit. ❖ Kn has a Hamilton circuit where n≥3

Theorem 5.10: Let the number of edges of G be m. Then G has a Hamilton circuit if m2(n 3n+6)/2, where n is the number of vertices of %o Proof: If any two vertices of G are adjacent, then G has a Hamilton circuit 192939···n1 o Suppose that u and v are any two vertices of G that are not adiacent o Let h be the graph produced by eliminating u and y from g Thus H has n-2 vertices and m-d(u-d(v) eages

❖ Theorem 5.10: Let the number of edges of G be m. Then G has a Hamilton circuit if m≥(n2 - 3n+6)/2,where n is the number of vertices of G. ❖ Proof: If any two vertices of G are adjacent ,then G has a Hamilton circuit v1 ,v2 ,v3 ,…vn ,v1 . ❖ Suppose that u and v are any two vertices of G that are not adjacent. ❖ Let H be the graph produced by eliminating u and v from G. ❖ Thus H has n-2 vertices and m-d(u)-d(v) edges

Theorem 5. 11: Letg be a simple graph with n vertices. n>2 G has a hamilton path if for any two vertices u andv of g that are not adjacent, d(u)+d(v2n-1

❖ Theorem 5. 11：Let G be a simple graph with n vertices, n>2. G has a Hamilton path if for any two vertices u and v of G that are not adjacent, d(u)+d(v)n-1