[試題] 100上 張鎮華 圖論一 期末考
課程名稱︰圖論一
課程性質︰數學系選修
課程教師︰張鎮華
開課學院：理學院
開課系所︰數學系
考試日期︰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
推
01/13 05:53, , 1F
01/13 05:53, 1F
→
01/13 12:33, , 2F
01/13 12:33, 2F
→
01/13 15:40, , 3F
01/13 15:40, 3F