应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 运筹学与控制论 » 一点小疑问
71/1返回列表
查看: 1376  |  回复: 6
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

napoleon_999

木虫 (小有名气)

[求助] 一点小疑问 已有1人参与

如题，有一点小疑问，如果任意给你一个简单图G，有没有办法构造一个图G'，使得这两个图满足一个关系，即，图G含有一个哈密尔顿圈当且仅当图G'含有一条哈密尔顿路，求大神指教！
回复此楼

» 猜你喜欢
1楼 2015-11-05 15:06:14
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sskkyy

银虫 (正式写手)

【答案】应助回帖

感谢参与，应助指数 +1
取G'为G就可以。你的问题没有讲清楚吧，是不是还有 其他要求？
赞一下 回复此楼
2楼2015-11-05 23:10:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

napoleon_999

木虫 (小有名气)
引用回帖:
2楼: Originally posted by sskkyy at 2015-11-05 23:10:18
取G'为G就可以。你的问题没有讲清楚吧，是不是还有 其他要求？

可是前一个是要求哈密尔顿圈，后一个是要求哈密尔顿路啊，这两个是不一样的
赞一下 回复此楼
3楼2015-11-06 11:13:21
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sskkyy

银虫 (正式写手)

【答案】应助回帖

引用回帖:
3楼: Originally posted by napoleon_999 at 2015-11-06 11:13:21
可是前一个是要求哈密尔顿圈，后一个是要求哈密尔顿路啊，这两个是不一样的...

你所谓的”圈“，指的是loop，回路？
“路”是path?
赞一下 回复此楼
4楼2015-11-06 12:19:20
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

napoleon_999

木虫 (小有名气)
引用回帖:
4楼: Originally posted by sskkyy at 2015-11-06 12:19:20
你所谓的”圈“，指的是loop，回路？
“路”是path?...

圈指的是cycle,路指的是path
赞一下 回复此楼
5楼2015-11-06 20:21:15
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

hank612

至尊木虫 (著名写手)
★ ★ ★ ★ ★
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.

是这个关系么？
赞一下(1人) 回复此楼

» 本帖已获得的红花（最新10朵）

napoleon_999
We_must_know. We_will_know.
6楼2015-11-08 03:16:26
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

napoleon_999

木虫 (小有名气)
送红花一朵
引用回帖:
6楼: Originally posted by hank612 at 2015-11-08 03:16:26
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 ...

谢谢你的帮助！不好意思，有事外出，把这茬给忘了。
赞一下 回复此楼
7楼2015-11-20 13:28:17
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 napoleon_999 的主题更新
71/1返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 娱乐 +3 Tide man 2026-08-03 3/150 2026-08-04 09:58 by gltch
[基金申请] 面上提前没消息，有中的吗 +14 archvillain 2026-08-02 17/850 2026-08-04 09:46 by archvillain
[硕博家园] 售SCI一区T0P文章，我:8O.55.1.O.54,科目全,可伽急 +3 f1dmPx051StA 2026-08-03 7/350 2026-08-04 09:31 by v1TJC4qJauAB
[博后之家] 售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急 +3 jRl3mE6ddZGq 2026-08-03 5/250 2026-08-04 09:27 by v1TJC4qJauAB
[教师之家] 售SCI一区文章，我:8O5.5.1.O5.4,科目全,可伽急 +4 jRl3mE6ddZGq 2026-08-03 10/500 2026-08-04 09:26 by v1TJC4qJauAB
[博后之家] 售SCI一区文章，我:8O5.5.1.O5.4,科目全,可伽急 +4 cu9Nq1xK233Z 2026-08-03 9/450 2026-08-04 09:17 by v1TJC4qJauAB
[教师之家] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +5 cu9Nq1xK233Z 2026-08-03 10/500 2026-08-04 09:15 by v1TJC4qJauAB
[有机交流] 一个有机合成实验室都需要哪些设备？ 50+3 kf2781974 2026-07-31 10/500 2026-08-04 08:05 by 88817753
[找工作] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 cu9Nq1xK233Z 2026-08-03 9/450 2026-08-04 07:37 by k7OM8YghWbkC
[硕博家园] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +4 cu9Nq1xK233Z 2026-08-03 13/650 2026-08-04 07:30 by k7OM8YghWbkC
[教师之家] 基础研究怎么拉横向，学校到款任务越来越多，难以完成 拉横向，都有哪些途径啊 +9 锦衣卫寒战 2026-07-28 13/650 2026-08-04 07:21 by Ermito
[硕博家园] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +3 jRl3mE6ddZGq 2026-08-03 6/300 2026-08-04 04:47 by k7OM8YghWbkC
[公派出国] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 cu9Nq1xK233Z 2026-08-03 7/350 2026-08-04 04:46 by k7OM8YghWbkC
[考研] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 cu9Nq1xK233Z 2026-08-03 8/400 2026-08-04 03:21 by k7OM8YghWbkC
[基金申请] 什么时候能放榜呀？ +3 Jacob678 2026-08-03 3/150 2026-08-03 16:14 by gltch
[高分子] UV压敏胶开发 +3 ichall 2026-07-30 5/250 2026-08-03 14:40 by Sunrisepay
[基金申请] 微信指数没变化，科研之友没阅读 +15 wangze12014 2026-07-28 19/950 2026-08-02 20:05 by 蔡棒棒菂
[考博] 2027年申博 50+3 射雕英雄胜 2026-07-30 3/150 2026-08-02 09:36 by lfy8008
[高分子] HXDI做水性聚氨酯乳液，是不是特别容易出渣 15+3 yuyusuv 2026-07-29 3/150 2026-07-31 09:21 by huizingga
[基金申请] 你们的时间戳变了吗 +3 archvillain 2026-07-30 4/200 2026-07-30 18:53 by levinzhwen
信息提示
关闭
请填处理意见
关闭