[試題] 103下 王有禮 高等圖論 期中考

[m80126colin (許胖)]

課程名稱︰高等圖論
課程性質︰臺大盟校際選課
課程教師︰王有禮
開課學院：
開課系所︰
考試日期（年月日）︰2015/04/29
考試時限（分鐘）：180

試題 :

1. (20%) Prove that the dominating set decision problem is NP-complete.

2. (20%) Find the closed form of the following recurrence formula:

                 0                     if n  = 0,
                 1                     if n  = 1,
          t   =  2                     if n  = 2,
           n     5t    - 8t    + 4t    if n >= 3.
                   n-1     n-2     n-3

3. (20%) Show that, by using the search tree technique, the maximal
                                                           n
         independent set problem can be solved in O*(1.3803 ) time,

         where n is the number of vertices in graph G.

                                            n
4. (20%) Show that there exists an O*(1.4422 )-time algorithm to

         to determine whether X(G) <= 3 gor a graph G of n vertices,

         where X(G) denotes the chromatic number of G.

                                       n
5. (20%) Show that there exists an O*(3 )-time algorithm to solve

         the domatic partition problem for a graph G of n vertices.

--
推 waston0310: 5樓都帶柚子皮帽騎車
→ guncat860924: 五樓柚子皮外再帶西瓜皮
推 andy70332: 蓋
推 myhoo512: 五樓柚子皮加西瓜皮加橘子皮
→ tommyjyyang: 1～4樓全都戴綠帽
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.35.191.249
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1431625649.A.426.html