| 查看: 1386 | 回复: 6 | |||
[求助]
一点小疑问 已有1人参与
|
| 如题，有一点小疑问，如果任意给你一个简单图G，有没有办法构造一个图G'，使得这两个图满足一个关系，即，图G含有一个哈密尔顿圈当且仅当图G'含有一条哈密尔顿路，求大神指教！ |
回复此楼» 猜你喜欢
今天系统多次维护，明天很可能放榜！
已经有5人回复
-
欢迎发来filecode的Mz6后的代码验证其规律
已经有74人回复
-
岩土工程学报什么时候才能终审完呐
已经有4人回复
-
时间戳又变了8-15
已经有25人回复
-
2027广东省杰青
已经有6人回复
-
快农历七夕节了，轻松一下，男人悄悄话，女施主请不要进来。
已经有3人回复
-
哪位老哥知道今年的国自然具体哪一天放榜？
已经有9人回复
-
咱们一起用铁证分析2026国家社科基金中标与否
已经有26人回复
-
我的国基提前知道中了，可是同事的操作让我实在接受不了，怎么会有这样的人
已经有16人回复
-
有时候，自然基金真的不能太认真 （我的申报经验）
已经有12人回复
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
25