汉密尔顿图

2015/2/6 posted in  算法&数据结构

基本概念

汉密尔顿通路:给定图G,若存在一条经过图中的每个顶点一次且仅一次的通路,则称这条通路为汉密尔顿通路。

哈密尔顿回路:若存在一条回路,经过图中的每个顶点一次且仅一次,则称这条回路为汉密尔顿回路。

汉密尔顿图:具有汉密尔顿回路的图称为汉密尔顿图。

相关定理

定理1:若无相连通图G(V,E)具有汉密尔顿回路,则对于顶点集合V的人已非空子集S,均有W(G-S)<=|S|成立。其中|S|表示集合S中边的数目,W(G-S)表示G-S中连通分量的数目。

但是注意,用定理1来证明某一个特定图是非汉密尔顿图,这个方法并不是总是有效的,比如彼得森图符合定理1但是属于非汉密尔顿图。

定理2:设G是具有n个顶点的简单图,如果G中每一对顶点度数之和大于等于n-1,则在G中存在一条汉密尔顿回路。

定理3:设G是具有n个顶点的简单图,如果G中每一对顶点度数之和大于等于n,则在G中存在一条汉密尔顿回路。

注意:定理2和定理3是充分关系。