哈密顿图论.doc

哈密顿图十二面体中的哈密顿路径哈密顿图（英语：Hamiltonian path，或Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶的路径称作哈密顿路径。美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。哈密尔顿回路问题与欧拉回路类似。 它是1859年哈密尔顿首先提出的一个关于12面体的数学游戏： 能否在图10.4.9中找到一个回路，使它含有图中所有结点一次且仅一次？ 若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地呢？为此，这个问题也被称作周游世界问题（10.4.9）对图10.4.9 ， 图中粗线给出了这样的回路。 定义 10.4.3 给定图G， 若有一条路通过G中每个结点恰好一次， 则这样的路称为哈密尔顿路；若有一个圈， 通过G个每个结点恰好一次， 这样的圈称为哈密尔顿回路（或哈密尔顿圈）。 具有哈密尔顿回路的图称为哈密尔顿图。 尽管哈密尔顿回路与欧拉回路问题在形式上极为相似，但是到目前为止还不知道一个图为哈密尔顿图的充要条件，寻找该充要条件仍是图论中尚未解决的主要问题之一。下面先给出一个简单而有用的必要条件。 定理10.4.4 设图GV ,E是哈密尔顿图， 则对于V的每个非空子集S， 均有 W（GS）|S| 成立， 其中W（GS）是图GS的连通分支数。 证明: 设是G的哈密尔顿回路， S是V的任一非空子集。 在GS中， 最多被分为|S|段， 所以 W（GS）|S| 利用本定理可判别某些图不为哈密尔顿图。 如在图10.4.10中， 若取Sv1， v4， 则GS有 3 个连通分支， 故该图不是哈密尔顿图。 判断哈密尔顿图的充分条件很多， 我们仅介绍其中一个。 定理 10.4.5 设GV ,E是有n个结点的简单图， 1） 如果任两结点u， vV， 均有 deg(u)deg(v) n1， 则在G中存在一条哈密尔顿路； 2） 如果对任两结点u， vV， 均有 deg(u)deg(v) n， 则G是哈密尔顿图。 证明 略。 【例10.4.3】某地有个风景点。若每个景点均有两条道路与其他景点相通，问是否可经过每个景点恰好一次而游完这处？ 解 将景点作为结点，道路作为边，则得到一个有个结点的无向图。 由题意，对每个结点vi，有 deg(vi)2（i5）。 则对任两点vi， vj（i， j5）均有 deg(vi)deg(vj)22451 可知此图一定有一条哈密尔顿路，本题有解。 我们再通过一个例子，介绍一个判别哈密尔顿路不存在的标号法。 【例10.4.4】证明图10.4.11所示的图没有哈密尔顿路。 证明: 任取一结点如v1，用A标记，所有与它相邻的结点标B。继续不断地用A标记所有邻接于B的结点，用B标记所有邻接于A的结点，直到图中所有结点全部标记完毕。 如果图中有一条哈密尔顿路，则必交替通过结点A和B。因此或者结点A和B数目一样，或者两者相差个。 （10.4.11）而本题有个结点标记A，个结点标记B，它们相差个，所以该图不存在哈密尔顿路。 作为哈密尔顿回路的自然推广是著名的货郎担问题。问题是这样叙述的：设有一个货郎，从他所在的城镇出发去n个城镇。要求经过每个城镇恰好一次，然后返回原地，问他的旅行路线怎样安排才最经济？从图论的观点来看，该问题就是： 在一个有权完全图中找一条权最小的哈密尔顿回路。研究这个问题是十分有趣且有实用价值的。但很可惜，至今没有找到一个很有效的算法。 当然我们可以用枚举法来解，但是当完全图的结点较多时，枚举法的运算量在计算机上也很难实现。下面介绍的“最邻近方法”给出了问题的近似解。最邻近方法的步骤如下： 1) 由任意选择的结点开始， 找与该点最靠近（即权最小）的点， 形成有一条边的初始 路径。 2) 设表示最新加到这条路上的结点， 从不在路上的所有结点中选一个与最靠近的结点， 把连接与这一结点的边加到这条路上。 重复这一步， 直到G中所有结点包含在路上。 3) 将连接起始点与最后加入的结点之间的边加到这条路上， 就得到一个圈， 即为问题的近似解。 【例10.4.5】某流动售货员居住在城，为推销货物他要访问，d城后返回城。若该城间的距离如图10.4.12所示，试用最邻近方法找出完成该旅行的最短路线？ 解 按最邻近方法一共有步，见图10.4.13。 得到的总距离为46。 （10.4.12）寻找哈密顿路径是一个典型的NP-完全问题。后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP-完全的。寻找哈密顿路的确定算法虽然很难有多项式时间的，但是这并不意味着只能进行时间复杂度为O(n!*n)暴力搜索。利用状态压缩动态规划，我们可以将时间复杂度降低到O(2n*n3)，具体算法是建立方程fiSj，表示经过了i个节点，节点都是集合S的，到达节点j时的最短路径。每次我们都按照点j所连的节点进行转移。哈密顿路图论在许多领域,诸如物理、化学、运筹学、计算机科学、信息论、控制论、网