课程名称︰图形算法特论
课程性质︰选修
课程教师︰赵坤茂
开课学院：电机资讯学院
开课系所︰资讯工程学系
考试日期（年月日）︰2021/05/30
考试时限（分钟）：170分钟
试题 :
Unless specified explicitly, a graph G or a tree T is assumed to be simple,
undirected and connected, and their edge weights w are positive. Let n be the
number of vertices and m be the number of edges in the input graph. Let C(T)
denote the routing cost of a given tree T, i.e.,
C(T) = Σ d (u, v).
u,v T
Both the correctness and efficiency of your answers will be evaluated.
1. (10%) Let the vertex set V be {1, 2, 3, 4, 5, 6, 7, 8}.
Decode the following Prufer sequences: (a) P = (1, 1, 2, 2, 8, 8), and
(b) P = (5, 6, 5, 6, 5, 6).
2. (10%) Give an approximation algorithm with a ratio bound of 2 for the
traveling-salesperson problem with triangle inequality. Justify your answer.
(You may use an example to describe your method and its approximation
ratio.)
3. (10%) Give an O(m log log n)-time algorithm for solving the minimum spanning
tree problem. Justify your answer.
4. (10%) Give an example to show Dijkstra's algorithm might fail if there
exists a negative edge.
5. (15%) (a) (10%) Prove that a shortest-paths tree (SPT) rooted at the median
of a graph is a 2-approximation of a minimum routing cost spanning tree
(MRCT) of the graph. (b) (5%) Give an example showing that such an SPT may
not be optimal for an MRCT.
6. (10%) (a) (5%) For any edge e in E(T), if the numbers of vertices on both
sides of e are at least δn, where 0 ≦δ≦1/2, the routing load on e is at
least [ A ]. (b) (5%) Furthermore, for any edge of a tree T, the routing
load is upper bounded by [ B ]. (Complete [ A ] and [ B ] and justify your
answers.)
7. (10%) (a) (5%) Show that any 1/5-separator of a tree must contain a
centroid. (b) (5%) Give an algorithm for finding a minimal 1/5-separator of
a given tree.
8. (10%) Let T denote a minimum routing cost spanning tree of a given graph G.
Let P = (p , p , ..., p ) be a minimal 1/3-separator of T. Let p be a
1 2 k q
centroid of T. We know that p must be included in V(P). Construct
q
S = SP (p , p ) U SP (p , p ).
G 1 q G q k
Fill in the coefficient of the inequality as small as possible and prove
that
Σ d (v, S) ≦ Σd (v, P) + [ ? ]w(P).
v G v T
9. (15%) Let T denote a minimum routing cost spanning tree of a given graph G.
Let S be a minimal 1/4-separator of T. Let Y be a spanning tree by
connecting each vertex with a shortest path to S, i.e., a general star of S.
Fill in the coefficient of the inequality C(Y) ≦[ ? ]C(T) as small as
possible. Justify your answer.