哈密顿图

维基百科,自由的百科全书
(重定向自哈密頓圖
跳到导航 跳到搜索
十二面体中的哈密顿回路

哈密顿图(台湾作漢米頓圖)又稱漢密頓圖,是指存在哈密頓環無向圖,由哈密顿爵士提出。

定義[编辑]

G=(V,E)是一个图,若G中一条通路通过且仅通过每一个顶点一次,称这条通路为哈密尔顿通路。若G中一个圈通过且仅通过每一个顶点一次,称这个圈为哈密尔顿圈。若一个图存在哈密尔顿圈,就称为哈密尔顿图。

性質[编辑]

哈密尔顿图的必要条件: 若G=(V,E) 是一个哈密尔顿图,则对于V的每一个非空子集S,均有W(G-S) ≤|S|。其中|S|是S中的顶点数,W(G-S)表示图G擦去属于S中的顶点后,剩下子图的连通分支的个数。

哈密尔顿图的充分条件: 设 是一个无向简单图,。若对于任意的两个顶点 ,那么 ,即 满足 ,那么, 是哈密尔顿图。此条件由美国图论数学家奥勒在1960年给出。

寻找哈密顿路径是一个典型的NP-完全问题。后来人们也证明了,找一条哈密顿路的近似比为常数的近似算法也是NP-完全的。

寻找哈密顿路的确定算法虽然很难有多项式时间的,但是这并不意味着只能进行时间复杂度暴力搜索。利用状态压缩动态规划[來源請求],可以将时间复杂度降低到,具体算法是建立方程f[i][S][j],表示经过了i个节点,节点都是集合S的,到达节点j时的最短路径。每次都按照点j所连的节点进行转移。

例子[编辑]

參見[编辑]

參考文獻[编辑]