課程名稱︰圖形演算法特論 課程性質︰選修 課程教師︰趙坤茂 開課學院：電機資訊學院 開課系所︰資訊工程學系 考試日期（年月日）︰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. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.134 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1617076912.A.AAB.html