[問題] Hamiltonian Circuit問題
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間11年前 (2013/05/30 21:18)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/2 (看更多)
我在嘗試解Codility上面 Eta 2011的問題
http://codility.com/train/
題目的大意是這樣，給定一個m個頂點的unrooted binary tree，m為偶數。
（原題是說圖上有兩種節點，一種節點degree為3，另一種節點degree為1，
而且邊數只有 m - 1，所以應該就是unrooted binary tree）
然後給一個從樹上一點出發的in-order traversal order。
令所有leaves在此order出現的順序為 l1, l2, ..., lk, k為leaf的個數。
接著在樹上增加k條邊，分別是 (l1, l2), (l2, l3), ..., (lk-1, lk), (lk, l1)
（原題是給你一個tour，每條邊都被visit兩次，degree為1的點被visit一次，
degree為3的點被visit 3次，依照degree為1的點被visit的順序，建立一個cycle去
連接這些degree為1的點）
問在此圖上有多少條Hamiltonian Circuit。
雖然我可以知道這個圖是3-regular，同時也是planar，但是好像對於找出
Hamiltonian Circuit的數量沒有太大幫助。
而且題目的時間複雜度要求為線性，所以複雜度高的圖論演算法或是Heuristic搜尋
都不可能是解答。
我是不是漏了什麼重要線索？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 129.170.195.150
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
