Re: [理工] 107 交大資演 10

看板Grad-ProbAsk作者FRAXIS (喔喔)時間6年前 (2019/01/27 11:44)推噓4(4推 0噓 1→)

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

※ 引述《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://www.ptt.cc/bbs/Grad-ProbAsk/M.1548560644.A.EB0.html

推

rockieloser

01/27 12:00, 6年前 , 1^F

01/27 12:00, 1^F

推

Leaving

01/27 12:02, 6年前 , 2^F

01/27 12:02, 2^F

推

magic83v

01/27 12:05, 6年前 , 3^F

01/27 12:05, 3^F