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

楼主: FRAXIS (喔喔)   2019-01-27 11:44:01
※ 引述《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"。
作者: rockieloser (友善大队长)   2019-01-27 12:00:00
作者: Leaving   2019-01-27 12:02:00
推推
作者: magic83v (R7)   2019-01-27 12:05:00
我以为是令两个点叫u.v 把s.t接在上面就好要考虑所有点才对==
作者: dumpling1234 (dumpling)   2019-01-27 12:29:00
感恩大神

Links booklink

Contact Us: admin [ a t ] ucptt.com