作者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/cn.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