关于哈密尔顿回路和桥的关系

Question

请问bobo老师，能不能说：如果图中有桥就说明一定没有Hamilton loop呢，这两者能否是充要条件

Answer 1

liuyubobobo 2019-11-15 11:29:44

可以，毕竟过去了就回不来了。

但是，没有桥不意味着一定有哈密尔顿回路。比如：

0       3
| \   / |
|   2   |
| /   \ |
1       4

这个图中没有桥，也没有哈密尔顿回路：）

继续加油！：）

• 提问者 慕移动9062336 #1

  谢谢bobo老师

• 提问者 慕移动9062336 #2

  所以是充分条件是嘛

• liuyubobobo 回复 提问者 慕移动9062336 #3

  有桥，则不存在哈密尔顿回路。这个命题和哈密尔顿回路的存在在性没关系。我们一般探究存在性的充分或者必要条件。

点开查看后面1条评论