高考问答上虞市面积:优先队列式分支界限法
来源：百度文库 编辑：高考问答 时间：2024/04/27 20:36:50
解决汉密尔顿图的方法
必要条件：
设图G是哈密尔顿图，如果从图G中删去P个顶点后，得到图G'，则图G'得连同分支数小于等于P。
注意：利用这个定理可以判定某些图不是哈密尔顿图。
充分条件：
定理1.设图G是具有n个顶点（v1...vn）的无向简单图，如果途中任一两个不同的顶点的度数之和大于等于n，即deg(vi)+deg(vj)>=n,(i不等于j)，则图G中具有哈密尔顿回路，即G是哈密尔顿图。
定理2.设图G是具有n个顶点（v1...vn）的无向简单图，如果途中任一两个不同的顶点的度数之和大于等于n-1，即deg(vi)+deg(vj)>=n-1,(i不等于j)，则图G中具有哈密尔顿通路，即G是半哈密尔顿图。
注意：上述定理可确定某些图是哈密尔顿图或半哈密尔顿图，有些哈密尔顿图或半哈密尔顿图不满足上述定理所设条件。
楼主是计算机系的吧？
楼主是计算机系的吧
这是什么方面的问题阿