通俗解释一下:如何判断不是哈密顿图?
发布网友
发布时间：2023-07-16 08:23
共1个回答
热心网友
时间：2024-12-05 16:30
若图的最小度不小于顶点数的一半，则图是哈密顿图；若图中每一对不相邻的顶点的度数之和不小于顶点数，则图是哈密顿图。另外，还有很多用度序列、度和、图的坚韧度等参数给出的充分条件。
定理1： 设无向图G是哈密顿图，V1是V的任意的非空子集， p(G-V1)≤|V1| 其中，p(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得到的图的连通分支。
定理2： 设G是n(n≥3)阶无向简单图，如果G中任何一对不相邻的顶点度数之和都大于等于n，则G是哈密顿图。
定理3： 在n(n≥2)阶有向图D=中，如果所有有向边均用无向边代替，所得无向图中含生成子图Kn，则有向图中存在哈密顿图。
推论： n(n≥3)阶有向完全图为哈密顿图。
扩展资料
哈密顿图（哈密尔顿图）（英语：Hamiltonian graph，或Traceable graph）为一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。
在图论中指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径（Hamiltonian path）。
参考资料来源：百度百科-哈密顿回路
参考资料来源：百度百科-哈密顿图
