課程名稱︰圖論一 課程性質︰數學系選修 課程教師︰張鎮華 開課學院：理學院 開課系所︰數學系 考試日期︰2012年01月12日 考試時限：240分鐘，早上6:00-10:00 是否需發放獎勵金：是 試題 : Final Exam for Graph Theory I　　　　　　　　(2012-01-12) 1. (25%) (a) Suppose G is a graph with connectivity κ(G), edge-connectivity κ'(G) and minimum degree δ(G). Prove that κ(G)≦κ'(G)≦δ(G). 　 (b) Prove that a graph of at least three vertices is 2-connected if and 　　only if there are two internally vertex-disjoint paths between any two 　　distinct vertices. 2. (25%) (a) Prove Euler's formula: If G is a connected plane graph with n 　　vertices, e edges and f faces, then n-e+f=2. 　 (b) Suppose G is a planar graph of n vertices and girth k≧3. Prove that G 　　has at most (n-2)k/(k-2) edges. 　 (c) Prvoe that K_5 , K_(3,3) and the Peterson graph are not planar. 　 (d) The Headwood graph H = (V,E) has its vertex set V={0,1,...,13} and edge 　　set E = {ij : i∈V , j = (i+1)mod 14}∪{ij : i∈V, i odd, j = (i+5)mod 14}. 　　Prove that the Headwood graph is not planar. 3. (25%) Suppose G is a graph of n vertices. For any vertex ordering v1,v2,..., 　　vn of graph G. let χ_(v1,v2,...,vn)(G) be the number of colors used when 　　apply the greedy coloring method according to this ordering. The greedy co- 　　loring spectrum of the graph G is the set χ_spec (G) = {χ_(v1,v2,...,vn): 　　v1,v2,...,vn is a vertex ordering of G}. 　　Let χ_min (G) = min{p:p∈χ_spec (G)} and χ_max (G)=max{p:p∈χ_spec (G)} 　　(a) Prove that χ(G)=χ_min (G)≦χ_max (G)≦Δ(G)+1 for any graph G. 　　(b) Determine χ_sepc (P_n), χ_min (P_n), χ_max (P_n) 　　　　for any path of n≧1 vertices. 　　(c) Determine χ_sepc (C_n), χ_min (C_n), χ_max (C_n) 　　　　for any cycle of n≧3 vertices. 　　(d) Prove that χ(G) = χ_max (G) for any P_4-free graph G. 4. (25%) (a) Suppose G is a graph of n≧3 vertices in which there are two 　　non-adjacent vertices u and v with deg(u)+deg(v)≧n. Prove that G has a 　　Hamiltonian cycle if and only if G+uv has a Hamiltonian cycle. 　　(b) The Hamiltonian closure C(G) of graph G is the graph obtained from G by 　　adding the edge uv in (a) repeatedly until there is no such pair (u,v). 　　Prove that the notion C(G) is well-defined, i.e., it is unique and independ 　　-ent to the ordering of adding the edges. 　　(c) Suppose G is a graph with degree sequence d1≦d2≦...≦dn. Prove that 　　G has a Hamiltonian cycle if the following condition hold: If 1≦i,j≦n, 　　i+j≧n, vivj不屬於E(G), deg(vi)≦i and deg(vj)<j, then deg(vi)+deg(vj)≧n. --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.252.31