[转录][试题] 93下 张镇华 图论算法 期末考

楼主: askia (过客)   2006-07-12 12:30:18
※ [本文转录自 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.

Links booklink

Contact Us: admin [ a t ] ucptt.com