作者FRAXIS (喔喔)
看板Grad-ProbAsk
標題Re: [理工] 107 交大 資演 10
時間Sun Jan 27 11:44:01 2019
※ 引述《dumpling1234 (dumpling)》之銘言：
: https://imgur.com/Wt5ikwe
我提供我的方法，或許會有更簡單的解法。
HamP(G)
Input: an udirected graph G
Output: "Yes", if G has a Hamiltonian path; "No", otherwise
給定一個 HamP(G) 的演算法，求解這個問題
HamEx(G, x)
Input: an undirected graph G, and a node x in G
Ouput: "Yes", if G has a Hamiltonian path from node u to v so that
u != x and v != x; "No", otherwise
方法：
令 G(V, E), x in V 為 HamEx(G, x) 的 input
建一個圖 G' = (V', E'), 其中
V' = V ∪ {s, t, s', t'}, |V'| = O(|V|)
E' = E ∪ {(s, s'), (t, t')}
∪ {(s', y) | for all y != x)}
∪ {(z, t') | for all z != x)}
因為 |V'| = O(|V|), |E'| = O(|E| + |V|)，
圖 G' 頂多花 O(|E| + |V|) 的時間就可以建好。
接著我們要證明 HamEx(G, x) = "Yes" iff HamP(G') = "Yes"
(1) if HamEx(G, x) = "Yes", then HamP(G') = "Yes"
令 HP 為 G 中的 Hamiltonian path，且 HP 頭尾不為 x。
因為 s' 跟 G 中所有不是 x 的點相連且 t' 跟 G 中所有不是 x 的點相連，
那麼 s - s' - HP - t' - t 必是一條 G' 上的 Hamiltonian path。
(2) if HamP(G') = "Yes", then HamEx(G, x) = "Yes"
令 HP 為 G' 中的 Hamiltonian path。
因為 s 和 t 在 G' 中的 degree 只有 1 ，所以 HP 的頭尾必為 s 和 t。
又 s 和 t 只分別跟 s' 和 t' 相連，HP 必為以下形式 s - s' - HP' - t' - t。
其中 HP' 必為 G 上的 Hamiltonian path。
又因為 s' 和 t' 都不與 x 相連，所以 HP' 的頭尾必不為 x ，
因此 HamEx(G, x) = "Yes"。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.202.90.47
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1548560644.A.EB0.html
1F：推 rockieloser: 推 01/27 12:00
2F：推 Leaving: 推推 01/27 12:02
3F：推 magic83v: 我以為是令兩個點叫u.v 把s.t接在上面就好 01/27 12:05
4F：→ magic83v: 要考慮所有點才對== 01/27 12:24
5F：推 dumpling1234: 感恩大神 01/27 12:29
※ 編輯: FRAXIS (73.202.90.47), 02/03/2019 12:50:42