| 查看: 1196 | 回复: 6 | ||
[求助]
一点小疑问 已有1人参与
|
| 如题，有一点小疑问，如果任意给你一个简单图G，有没有办法构造一个图G'，使得这两个图满足一个关系，即，图G含有一个哈密尔顿圈当且仅当图G'含有一条哈密尔顿路，求大神指教！ |
回复此楼» 猜你喜欢
上海工程技术大学【激光智能制造】课题组招收硕士
已经有6人回复
-
带资进组求博导收留
已经有11人回复
-
自荐读博
已经有5人回复
-
求个博导看看
已经有16人回复
-
上海工程技术大学张培磊教授团队招收博士生
已经有4人回复
-
求助院士们，这个如何合成呀
已经有4人回复
-
临港实验室与上科大联培博士招生1名
已经有9人回复
-
写了一篇“相变储能技术在冷库中应用”的论文，论文内容以实验为主，投什么期刊合适？
已经有6人回复
-
最近几年招的学生写论文不引自己组发的文章
已经有11人回复
-
中科院杭州医学所招收博士生一名（生物分析化学、药物递送）
已经有3人回复
sskkyy
银虫 (正式写手)
- 数学EPI: 1
- 应助: 180 (高中生)
- 金币: 1015.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 (高中生)
- 金币: 1015.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