課程名稱︰圖論一
課程性質︰
課程教師︰張鎮華
開課學院：
開課系所︰數學系
考試日期（年月日）︰2007.11.08
考試時限（分鐘）：120
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
1.(40%)For integers n and k satisfying n≧k≧1, let Gn,k=(Vn,k，En,k) be the
n
graph with Vn,k={a1...an} and En,k={{a1...an,b1...bn}: Σ│ai-bi│=k}.
i=1
Answer the following questions with proofs.
(a)How many components does Gn,k have?
(b)For which n and k does Gn,k have an Eulerian tour?
(c)Construct a graph not isomorphic to Gn,k , but has the same degree
sequence as Gn,k.
2.(20%)Suppose x1,x2,...xn are n distinct numbers. The following method finds
the maximum of these n numbers using n-1 comparisons:
max=x1;
do i=2 to n;
if max<xi then max=xi;
Similarly, we may find the minimum by using n-1 comparisons. Consequently, we
may find the maximum and the minimum by using totally 2n-2 comparisons.
Design an algorithm to find the maximum and the minimum by using less than
2n-2 comparisons. Is your method the best possible one?(need proof)
3.(20%)In a tree T, a branch at a vertex u is the maximal sub-tree containing
u as a leaf. The branch weight b(u) of u is the maximun number of edges in a
branch at u. A centroid vertex is a vertex with the minimum branch weight
b(u).
Prove that every tree has exactly onecentroid vertex or has exactly two
centroid vertices that are adjacent.
4.(20%)Suppose Gn is the graph with vertex set Vn={a1,a2,...an,b1,b2,...bn} and
edge set En={ai ai+1,bi bi+1:1≦i≦n-1}∪{ai bi:1≦i≦n}
Prove that τ(Gn)=4τ(Gn-1)-τ(Gn-2) for n≧3. Determine τ(Gn) in terms of
n for all n≧1.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.222.24