课程名称︰图论演算法 课程性质︰系所选修 课程教师︰张镇华 开课学院：理学院 开课系所︰数学所 考试日期（年月日）︰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)