PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Hamiltonian Circuit問題

看板Prob_Solve (計算數學 Problem Solving)作者ferng1021 (菘~~~)時間11年前 (2013/05/31 00:58)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/2 (看更多)

任意挑一個 leaf 當作 root 把這棵樹掛起來扣掉這個 root 之後下面會是 full binary tree 也就是除了 leaf 之外每個點都有 2 個小孩假設 B,C 是 leaves, A 是他們的 parent 加上那 k 條邊之後會從左邊的圖變成右邊 | | A A / \ / \ B C -B-C- 這個結構其實對任意的 sub-tree 都是通用的 A 是 root, B 和 C 是 A 下面的 sub-tree 我們可以利用這個結構來做歸納先看一個 leaf 的狀況 | -B- 一個 Hamilton Circuit 一定會通過 {上,左,右} 三條邊中的恰好兩條 | | | -B- -B- -B- 對 B 來說 {上左}, {上右}, {左右} 各有 1 種可能再看 A 是 root, B 和 C 是 sub-tree 的狀況 | | | A A A / \ / \ / \ -B-C- -B-C- -B-C- (a) (b) (c) (a) 如果 B 選 {上左}，那 C 就一定要 {上右}，整個 A sub-tree 就是 {左右} (b) 如果 B 選 {上右}，那 C 就一定要 {左右}，整個 A sub-tree 就是 {上左} (c) 如果 B 選 {左右}，那 C 就一定要 {上左}，整個 A sub-tree 就是 {上右} 如果不是這三種情形，就一定連不成 Hamilton circuit 在這三種情形中我們都可以把整個 A sub-tree 縮成一個點來繼續推論 A 的 parent 和 sibling 要選哪些邊進 Hamilton circuit (B -> A 和 A sub-tree -> parent(A) 的關係一樣) 簡而言之一旦 B 的邊決定了 C 和 A 的邊也就跟著決定了更進一步說一旦 A sub-tree 的邊決定了 A 的 parent 的邊也就決定了也就是整棵樹的 Hamilton circuit 就決定了!! 所以其實無論 N 多大答案都是 3 理由是第一個葉子(上面的B)有三種選邊的方法而這個葉子每一種方法都可以推出一個 Hamilton circuit (也只會推出一個) 那題目說的線性複雜度要用在哪裡? 用在檢查 input 是不是符合規定的圖題目敘述有說可能會有不合規定的 input 這時候要輸出 -2 在 Codility 的 demo: https://codility.com/demo/results/demoAB76TX-6HV/ 檢查 input 寫得很醜請見諒 ※ 引述《FRAXIS (喔喔)》之銘言： : 我在嘗試解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: 36.231.16.216