如何判定哈密顿回路

来源:学生作业帮助网 编辑:作业帮 时间:2024/04/30 07:31:02
如何判定哈密顿回路

如何判定哈密顿回路
如何判定哈密顿回路

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