※ [本文轉錄自 NTU-Exam 看板]
作者: denehs (DE) 看板: NTU-Exam
標題: [試題] 93下 張鎮華 圖論演算法 期末考
時間: Sun Jun 19 17:49:07 2005
課程名稱︰圖論演算法
課程性質︰選修
課程教師︰張鎮華 教授
開課系所︰數學系
考試時間︰2005/06/14 10:20-12:10
試題：
Final Examination for Graph Algorithms
2005-06-14 (G.J.Chang)
*************************************************************
*Each problem weights 20 points even some of them are easier*
*and some harder. If you get x points, the real score s(x)=x*
*for 0<=x<=80, s(x)=40+x/2 for 80<=x<=100 and s(x)=65+x/4 *
*for 100<=x<=140 *
*************************************************************
1. Suppose G = (X,Y,E) is a bipartite graph in which every edge ij is
associated with a real number w . Recall that a w-vertex cover is a
ij
vector (u,v) where each vertex i屬於X has a non-negative real u and
i
each vertex j屬於Y has a nonnegative real v such that w ≦u +v
j ij i j
for each edge ij屬於E.
For any matching M, let w(M) = Σ u + Σ v . Prove that
i屬於X i j屬於Y j
w(M)≦cost(u,v).
Also, give necessary and sufficient conditions for the inequality above
to be an equality.
2. Use depth-first-search to help designing an efficient algorithm to
determine wherher the edges of a connected graph can be directed to
produced a strongly connected digraph.
3. Design a Turning machine to accept the strings of the form
a b c
10 10 10
such that a,b,c are non-negative integers with a+b = c.
4. Polynomially transform the clique problem to the vertex cover problem.
(The clique problem: Does a graph have a clique of size k?)
(The vertex cover problem: Does a graph have a vertex cover of size k?)
5. Let G = (V,E) be an acyclic digraph. We wish to find a minimum number of
directed vertex-disjoint paths which cover all the vertices; i.e., every
vertex is on exactly one path. The paths may start anywhere and end anyware
, and their lengths are not restricted in any way. A path may be of zero
length; i.e. consist of one vertex.
(a) Describe an algorithm for achieving this goal, and make it as efficient
as possible. (Hint: Form a network as follows.
V' = {s,t}∪{x1,x2,...,x|V|}∪{y1,y2,...,y|V|}
E' = {s->xi:1≦i≦|V|}∪{yi->t:1≦i≦|V|}∪{xi->yj:vi->vj in G}.
The capacity of each is 1. Show that the minimum number of paths
which cover V in G is equal to |V|-F where F is the maximum total
nflow of the network.)
(b) Is the condition that G is acyclic essential for the validity of
your algorithm? Explain.
(c) Give the best upper bound you can on the time complexity of your
algorithm.
6. Recall that a k-L(2,1)-labeling of a graph G = (V,E) is a function f: V->
{0,1,2,...,k} such that |f(x)-f(y)|≧2 if xy 屬於 E and f(x)≠f(y) if
d(x,y) = 2. The L(2,1)-labeling number λ(G) is the minimum k such that G
has a k-L(2,1)-labeling.
Determine λ(Cn) for n≧3. Prove your answer.
7. Recall that an interval graph is a graph in which each vertex can be
associated with an interval in such a way that two distinct vertices are
adjacent if and only if their corresponding intervals overlap.
Determine for which n, the cycle Cn is an interval graph. Prove your
answer.