| 查看: 1273 | 回复: 6 | ||
[求助]
一点小疑问 已有1人参与
|
| 如题，有一点小疑问，如果任意给你一个简单图G，有没有办法构造一个图G'，使得这两个图满足一个关系，即，图G含有一个哈密尔顿圈当且仅当图G'含有一条哈密尔顿路，求大神指教！ |
回复此楼» 猜你喜欢
339求调剂
已经有3人回复
-
290调剂生物0860
已经有30人回复
-
化工学硕294分，求导师收留
已经有6人回复
-
297工科，求调剂?
已经有8人回复
-
293求调剂
已经有13人回复
-
一志愿中南大学 0855 机械 286 求调剂
已经有7人回复
-
化学070300 求调剂
已经有11人回复
-
346分，工科0854求调剂，专硕
已经有6人回复
-
一志愿085802 323分求调剂
已经有11人回复
-
山东双非院校考核超级无底线，领导幸灾乐祸，教师遭殃恐
已经有7人回复
sskkyy
银虫 (正式写手)
- 数学EPI: 1
- 应助: 180 (高中生)
- 金币: 1017.9
- 散金: 376
- 红花: 18
- 帖子: 742
- 在线: 245.1小时
- 虫号: 1324155
- 注册: 2011-06-16
- 专业: 拓扑学
2楼2015-11-05 23:10:18
3楼2015-11-06 11:13:21
sskkyy
银虫 (正式写手)
- 数学EPI: 1
- 应助: 180 (高中生)
- 金币: 1017.9
- 散金: 376
- 红花: 18
- 帖子: 742
- 在线: 245.1小时
- 虫号: 1324155
- 注册: 2011-06-16
- 专业: 拓扑学
4楼2015-11-06 12:19:20
5楼2015-11-06 20:21:15
hank612
至尊木虫 (著名写手)
- 数学EPI: 14
- 应助: 225 (大学生)
- 金币: 14270.6
- 散金: 1055
- 红花: 95
- 帖子: 1526
- 在线: 1375.8小时
- 虫号: 2530333
- 注册: 2013-07-03
- 性别: GG
- 专业: 理论和计算化学
★ ★ ★ ★ ★
napoleon_999(feixiaolin代发): 金币+5 2015-11-21 19:19:58
napoleon_999(feixiaolin代发): 金币+5 2015-11-21 19:19:58
|
https://en.wikipedia.org/wiki/Hamiltonian_path_problem There is a simple relation between the problems of finding a Hamiltonian path and a Hamiltonian cycle. In one direction, the Hamiltonian path problem for graph G is equivalent to the Hamiltonian cycle problem in a graph H obtained from G by adding a new vertex and connecting it to all vertices of G. Thus, finding a Hamiltonian path cannot be significantly slower (in the worst case, as a function of the number of vertices) than finding a Hamiltonian cycle. In the other direction, the Hamiltonian cycle problem for a graph G is equivalent to the Hamiltonian path problem in the graph H obtained by copying one vertex v of G, v', that is, letting v' have the same neighbourhood as v, and by adding two dummy vertices of degree one, and connecting them with v and v', respectively. 是这个关系么？ |
» 本帖已获得的红花（最新10朵）
napoleon_999
6楼2015-11-08 03:16:26
7楼2015-11-20 13:28:17
20
