課程名稱︰圖論演算法 課程性質︰系所選修 課程教師︰張鎮華 開課學院：理學院 開課系所︰數學所 考試日期（年月日）︰2012/11/16 考試時限（分鐘）：120分鐘。正常人的話也可以am6:00開始, 寫360分鐘。 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : 1. Series-parallel graphs are graphs (G,u,v) with two special terminals u and v, which are defined recursively in the following rules. In this notion, the order of u and v is important. (I) (Initial Graphs.) A complete graph K_2 with vertices u and v is a series-parallel graphs (K_2,u,v). (S) (Series operation.) If (G,u,v) and (H,x,y) are two disjoint series- parallel graphs, then the graph obtained from their union by identi- fying v with x is the series parallel graph (G+H,u,y). (P) (Parallel operation.) If (G,u,v) and (H,x,y) are two disjoint series- parallel graphs, then the graph obtained from their union by identi- fying u with x and v with y is the series parallel graph (G ·H,u,v). (a) Give examples of graphs which are not series-parallel graphs. (b) Establish a dynamic program algorithm to determine the domination number of a seeries-parallel graph. 2. (a) Prove that alpha_2(G) <= grmma(G) for any positive integer k and any graph G. (b) Give examples of graphs for which inequalities in (a) are strict. (c) For a positive integer k and an interval graph G, establish a pri- mal dual algorithm to obtain a maximum 2-independent set, and a minimum dominating set; at the same time also prove that alpha_2(G) = grmma(G). 3. (a) Prove that the independent domination problem is NP-complete for bipartite graphs by reducing the vertex cover problem to it. (b) Is the independent domination problem polynomial-time algorithm for split graphs? --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.239.186 ※ 編輯: magrady 來自: 140.112.239.186 (11/18 02:31)