为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
哈密尔顿回路
来自NOCOW
下面的部分章节可能侵犯了版权
如果已经得到版权所有者许可，请注明来源以及所有者关于版权的声明（如果来源处已经写明可以省略）
可能来自http://class.htu.cn/lisanshuxue/neirong/7_4.htm 汉密尔顿图
汉密尔顿回路的问题与欧拉回路非常类似。1859年，咸廉?汉密尔顿爵士(Sir Willian Hamilton)在给他朋友的一封信中，首先谈到关于十二面体的一个数学游戏：能不能在图7-4.6中找到一条回路，使它含有这个图的所有结点?他把每个结点看成一个城市，联结两个结点的边看成是交通线，于是他的问题就是能不能找到旅行路线，沿着交通线经过每个城市恰好一次，再回到原来的出发地? 他把这个问题称为周游世界问题。
按图7-4.6中所给的编号，可以看出这样一条回路是存在的。
对于任何连通图也有类似的问题。
定义7-4.3 给定图G，若存在一条路经过图中的每个结点恰好一次，这条路称作汉密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。
具有汉密尔顿回路的图称作汉密尔顿图。
定理7-4.3 若图G＝<V，E>具有汉密尔顿回路，则对于结点集v的每个非空子集S均有W(G-S)≤|S|成立。其中W(G-S)是G-S中连通分支数。
证明 设C是G的一条汉密尔顿回路，则对于v的任何一个非空子集S在C中删去S中任一结点a1，则C-a1是连通的非回路，若再删去S中另一结点a2，则W(C-a1-a2)≤2，由归纳法可得：
W(C-S)≤|S|
同时C-S是G-S的一个生成子图，因而
W(G-S) ≤W(C-S) 所以 W(G-S)≤|S|
利用定理7-4．3可以证明某些图是非汉密尔顿图。如图7-4.7中若取S＝{v1，v4}，则G-S中有三个分图，故G不是汉密尔顿图。
需要指出，用定理7-4.3来证明某一特定图是非汉密尔顿图，这个方法并不是总是有效的。例如，著名的彼得森(Petersen)图，如图7-4.8中所示，在图中删去任一个结点或任意两个结点，不能使它不连通；删去3个结点，最多只能得到有两个连通分支的子图；删去4个结点，只能得到最多三个连通分支的子图；删去5个或5个以上的结点，余下子图的结点数都不大于5，故必不能有5个以上的连通分支数。所以该图满足W(G-S)≤|S|，但是可以证明它是非汉密尔顿图(此证明留作习题)。
4 汉密尔顿图的充分条件
虽然汉密尔顿回路问题与欧拉回路问题在形式上极为相似，但对图G是否存在汉密尔顿回路还无充要的判别准则。下面我们给出一个无向图具有汉密尔顿路的充分条件。 定理7-4.4 设G具有n个结点的简单图，如果G中每一对结点度数之和大于等于n-1，则在G中存在一条汉密尔顿路。 证明 我们首先证明G是连通图。若G有两个或更多个互不连通的分图，设一个分图中有n1个结点，任取一个结点v1。没另一个分图中有n2个结点，任取一个结点v2，因为d(v1)≤n1-1，d(v2)≤n2-1，故d(v1)+d(v2)≤n1+n2-2<n-1，这与题设矛盾，故G必连通。 其次，我们从一条边出发构成一条路，证明它是汉密尔顿路。 设在G中有p一1条边的路，p＜n，它的结点序列为v1，v2，…，vp。如果有v1或vp邻接于不在这条路上的一个结点，我们立刻可扩展这条路，使它包含这一个结点，从而得到p条边的路，，否则，v1和vp都只邻接于这条路上的结点，我们证明在这种情况下，存在一条回路包含结点v1，v2，…，vp。若v1邻接于vp，则v1，v2，…，vp，v1即为所求的回路。假设与v1邻接的结点集是
这里2≤l，m，…，j，…，t≤p-1，如果vp是邻接于v1-1，vm-1，…，vj-1，…，vt-1中之一，譬如说vj-1，如图7-4.9(a)所示，v1 v2 v3…vj-1 vp vp-1…vj v1是所求的包含结点v1，v2，…，vp的回路
如果vp不邻接于v1-1，vm-1，…，vt-1中任一个，则vp至多邻接于p-k-1个结点，deg(vp)≤p-k-1，deg(v1)＝k，故deg(vp)+deg(v1) ≤p-k-1+k＝p-1<n-1，即v1与vp度数之和至多为n一2，得到矛盾。
至此，我们有包含所有结点v1，v2，…，vp的一条回路，因为G是连通的，所以在G中必有一个不属于该回路的结点vx与v1v2…vp中的某一个结点vk邻接，如图7-4.9(b)所示，于是就得到一条包含p条边的路(vx，vk，vk+1，…，vj-1，vp，vp-1，…，vj，…，v1，v2，…，vk-1)。如图7-4.9(c)所示，重复前述构造法，直到得到n-1条边的路。
容易看出定理7-4.4的条件对于图中汉密尔顿路的存在性只是充分的，但并不是必要条件。设G是n边形，如图7-4.10，其中n＝6，虽然任何两个结点度数之和是4<6-1，但在G中有一条汉密尔顿路。
例题1 考虑在七天内安排七门课程的考试，使得同一位教师所任的两门课程考试不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的，
证明设G为具有七个结点的图，每个结点对应于一门课程考试，如果这两个结点对应的课程考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任课程数不超过4，故每个结点的度数至少是3，任两个结点的度数之和至少是6，故G总是包含一条汉密尔顿路，它对应于一个七门考试课目的一个适当的安排。
定理7-4.5 设G是具有n个结点的简单图。如果G中每一对结点度数之和大于等于n，则在G中存在一条汉密尔顿回路。
证明 由定理7－4.4可知必有一条汉密尔顿路，设为v1v2…vn，如果v1与vn邻接，则定理得证。
如果v1与vn不邻接，假设v1邻接于{vi1，vi2，…，vikk}2≤ij≤n-1，可以证明vn必邻接于vi1-1，vi2-1，…，vik-1中之一。如果不邻接于vi1-1，vi2-1，…，vik-1中任一结点，则vn至多邻接于n-k-1个结点，因而d(vn)≤n-k-1， 而d(v1)＝k
故d(v1)+d(vn)≤n-k-1+k＝n-1，与题设矛盾，所以必有汉密尔顿回路v1v2…vj-1vnvn-1vjv1，如图7-4.11所示。
5 汉密尔顿图的充要条件
定义7-4.4 给定图G＝<V，E>有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G′，对图G′重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为是原图G的闭包，记作C(G)。
例如图7-4.12给出了对六个结点的一个图G，构造它的闭包的过程。在这个例子中C(G)是完全图。一般情况下，C(G)也可能不是完全图。 定理7-4.6 当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。 证明略。 关子图中没有汉密尔顿路的判别尚没有确定的方法，下面介绍一个说明性的例子。
例题2 指出图7-4.13(a)所示的图G中没有汉密尔顿路。 解用A标记任意一个结点a，所有与a邻接的结点均标记B，继续不断地用A标记所有邻接于B的结点，用B标记所有邻接于A的结点，直到所有结点标记完毕。这个有标记的图如图7-4.13(b)所示，如果在图G中有一条汉密尔顿路，那么它必交替通过结点A和结点B，然而本例中共有九个A结点和七个B结点，所以不可能存在一条汉密尔顿路。
注意：如果在标记过程中，遇到相邻结点出现相同标记时，可在此对应边上增加一个结点，并标上相异标记。如图7-4.14所示。请读者考虑用这种方法能否判断汉密尔顿路的存在性。
