| 查看: 1246 | 回复: 6 | |||
[求助]
一点小疑问 已有1人参与
|
| 如题，有一点小疑问，如果任意给你一个简单图G，有没有办法构造一个图G'，使得这两个图满足一个关系，即，图G含有一个哈密尔顿圈当且仅当图G'含有一条哈密尔顿路，求大神指教！ |
回复此楼» 猜你喜欢
材料学求调剂
已经有6人回复
-
303求调剂
已经有5人回复
-
一志愿武理085500机械专业总分300求调剂
已经有7人回复
-
考研调剂
已经有4人回复
-
281求调剂
已经有4人回复
-
0805 316求调剂
已经有6人回复
-
085601求调剂总分293英一数二
已经有3人回复
-
08工学调剂
已经有17人回复
-
340求调剂
已经有4人回复
-
311求调剂
已经有3人回复
sskkyy
银虫 (正式写手)
- 数学EPI: 1
- 应助: 180 (高中生)
- 金币: 1016.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 (高中生)
- 金币: 1016.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
