汉密尔顿图
汉密尔顿图
与欧拉回路非常类似的问题是汉密尔顿回路的问题。
1859年，威廉·汉密尔顿爵士在给他朋友的一封信中，首先谈到关于十二面体的一个数学游戏：能不能在图中找到一条回路，使它含有这个图的所有结点？（见图）
他把每个结点看成一个城市，联结两个结点的边看成是交通线。于是他的问题就是能不能找到旅行路线，沿着交通线经过每个城市恰好一次，再回到原来的出发地，他把这个问题称为周游世界问题。
定义1 给定图G，若存在一条路经过图中的每个结点恰好一次，这条路称作汉密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。
具有汉密尔顿回路的图称作汉密尔顿图。
定理1 若图G=<V,E>具有汉密尔顿回路，则对于结点集V的每个非空子集S均有 W(G-S)≤|S|成立。其中W(G-S)是G-S中连通分支数。
定理2 设G具有n个结点的简单图，如果G中每一对结点度数之和大于等于n-1，则在G中存在一条汉密尔顿路。
定理3 设G是具有n个结点的简单图。如果G中每一对结点度数之和大于等于n,则在G中存在一条汉密尔顿回路。
定义2 给定图G=<V,E>有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G’，对图G’重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为是原图G的闭包，记作C(G)。
定理4 当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。