如何判定哈密顿回路

来源:学生作业帮助网 编辑:六六作业网 时间:2024/07/07 05:22:50
如何判定哈密顿回路如何判定哈密顿回路如何判定哈密顿回路依据如下可以判断1包含个顶点的图,如果任意两个顶点的度数之和都不小于n-1(即大于等于n-1),则存在哈密尔顿通路.2包含个顶点的图,如果任意两个

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

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