如何判定哈密顿回路

那有静悄 1年前 已收到1个回答 举报

真直子 幼苗

共回答了14个问题采纳率:85.7% 举报

依据如下可以判断
1包含个顶点的图, 如果任意两个顶点的度数之和都不小于n-1(即大于等于n-1), 则存在哈密尔顿通路.
2包含个顶点的图, 如果任意两个顶点的度数之和都不小于n(即大于等于n), 则存在哈密尔顿回路.
存在哈密尔顿路也就是存在哈密尔顿回路.
“通路”(连通),“回路”(任意一顶点出发,都可以回到该顶点)

1年前

7
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.075 s. - webmaster@yulucn.com