課程名稱︰圖論一
課程性質︰選修
課程教師︰張鎮華教授
開課學院：理學院
開課系所︰數學所
考試日期（年月日）︰2010/01/13
考試時限（分鐘）：至寫完為止
是否需發放獎勵金：._./是，感恩m(_ _)m
（如未明確表示，則不予發放）
試題 :
1.(25%)
(a) Prove that if G is a graph with n>=3 vertices and d(G) >= n/2,
then G has a Hamiltonian cycle.
(b) For any n>=2, construct a graph G with n vertives and
d(G) = [(n-1)/2](取下界) but does not have a Hamiltonian cycle.
(c) Prove that for any k>=2, a k-regular graph of 2k+1 vertives has a
Hamiltonian cycle.
2.(25%) For any ordering v1,v2,...,vn of the vertices of G,
let χ(v1,v2,...vn)(G) be the numbers of colors used in the greedy coloring
^<<下標>>
method according to this ordering. Let A = {χ(v1,v2,...vn)(G), v1,v2...,vn
is an ordering of the vertives of G}.
(a) Prove that that χ(G) <= min(k∈A)k <= max(k∈A)k <= Δ(G) + 1.
(b) Prove that in fact χ(G) = min(k∈A)k.
(c) Prove that if G is P4-free then min(k∈A)k = max(k∈A)k.
(d) How large can max(k∈A)k be in general.
3.(25%) Denote c(G) the crossing number of a graph G.
(a) Determine c(K5) and c(K3,3). You also need to prove your answer.
(b) Determine c(K6) and c(K3,3,2). You also need to prove your answer.
(c) Prove that c(Kn) >= n^4/120 + O(n^3).
(d) Prove that c(Kn) >= n^4/80 + O(n^3).
4.(25%)
(a)Suppose G is a graph with at least three vertices. Prove that G is
2-connected if and only if for any two distinct vertices x and y there
are two internally vertex-disjoint x-y paths.
(b) Prove that the following statements ane equivalent for a graph G with
least three vertices.
1. G is connected and has no cut-vertex.
2. For any two distice vertices x and y there are two internally vertex-
disjoint x-y paths.
3. For any two distinct vertices there is a cycle contains them.
4. d(G) >= 1 and for any two distinct edges there is a cycle contains them.
--
Google 時の音の精靈| ████████▕検索▏検索オプション | 表示設定
▇▇ ￣￣￣￣￣￣￣ ￣￣￣￣
搜尋： ⊙ウェブ全体から検索 ○日本語のページを検索 ○蘿莉検索
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84