| 查看: 1182 | 回复: 6 | ||
[求助]
一点小疑问已有1人参与
|
| 如题，有一点小疑问，如果任意给你一个简单图G，有没有办法构造一个图G'，使得这两个图满足一个关系，即，图G含有一个哈密尔顿圈当且仅当图G'含有一条哈密尔顿路，求大神指教！ |
回复此楼» 猜你喜欢
三甲基碘化亚砜的氧化反应
已经有4人回复
-
请问下大家为什么这个铃木偶联几乎不反应呢
已经有5人回复
-
请问有评职称，把科研教学业绩算分排序的高校吗
已经有5人回复
-
孩子确诊有中度注意力缺陷
已经有12人回复
-
2025冷门绝学什么时候出结果
已经有3人回复
-
天津工业大学郑柳春团队欢迎化学化工、高分子化学或有机合成方向的博士生和硕士生加入
已经有4人回复
-
康复大学泰山学者周祺惠团队招收博士研究生
已经有6人回复
-
AI论文写作工具：是科研加速器还是学术作弊器？
已经有3人回复
-
论文投稿，期刊推荐
已经有4人回复
-
硕士和导师闹得不愉快
已经有13人回复
sskkyy
银虫 (正式写手)
- 数学EPI: 1
- 应助: 180 (高中生)
- 金币: 1014.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 (高中生)
- 金币: 1014.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