欧拉图和哈密顿图.ppt
离散数学,第四篇 图 论,第九章 欧拉图和哈密顿图,9.1 欧拉图9.2 哈密顿图,9.1 欧拉图,9.1.1 欧拉图的引入和定义 18世纪中叶，在东普鲁士哥尼斯堡城，有一条贯穿全城的普雷格尔河，河中有两个岛，通过七座桥彼此相连，如图9.1.1(a)所示。（a）（b）图,定义9.1.1 设G是无孤立节点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)。若存在一个圈，此圈通过G中每条边一次且仅一次，则此圈成为欧拉圈。具有欧拉回路的图称为欧拉图，具有欧拉通路但无欧拉回路的图称为半欧拉图。,规定：平凡图是欧拉图。以上定义既适合无向图，又适合有向图。例9.1.1 判断下图的6个图中，是否是欧拉图？是否存在欧拉通路。(a)(b)(c)(d)(e)(f),分析：如果说图中存在欧拉通路（回路），具体找出一条经过图中每边一次且仅一次的通路(回路)即可；如果说图中不存在欧拉通路(回路)，则要试遍了边的所有全排列，它们都不能构成通路（回路）。解：在6个图中，图(a)和(d)是欧拉图；图(b)和(e)不是欧拉图，但存在欧拉通路；图(c)和(f)不存在欧拉通路。,9.1.2 欧拉图的判定 判断一个图（无向图或有向图）是否有欧拉通路（回路），要考察所有边的所有全排列，几乎是不可能的，所幸已有简单的判别法。定理 设无向图G=是连通的，则（1）当且仅当G的每个顶点都是偶顶点时，G是欧拉图。（2）当且仅当G除两个顶点是奇顶点外，其它顶点都是偶顶点时，G有欧拉通路。,图 例9.1.2 图G如图所示。问图G是否为欧拉图？若是，求出其欧拉圈。由于G中的六个节点均为偶顶点且G连通，根据欧拉定理可知G为欧拉图。,在图中任意找一简单圈C：(1,2,3,1)；发现还有七条边不在此圈中，边(3,4)不在C中且在圈中的节点3相关联，由节点3出发经过边(3,4)可得到一简单圈C(3,4,5,3)，将C 并入C得到了一个新的更长的简单圈C：(1,2,3,4,5,3,1)。此时仍有四条边不在圈C中，边(4,6)不在C中且与节点4相关联，由节点4出发经过边(4,6)又可得到一个简单圈C：(4,6,5,2,4)，将C 并入C得到一个更长的简单圈C：(1,2,3,4,6,5,2,4,5,3,1)。可以看到，G中所有的边已全在C中了，故知此圈C即为G中的一条欧拉圈。,定理 设G=是有向弱连通图，则（1）当且仅当G的每个顶点的入度等于出度时，G是欧拉图。（2）当且仅当G除两个顶点外，其它顶点的入度等于出度，而除外的两个顶点，一个的入度比出度多1，另一个的入度比出度少1时，G有欧拉通路。定理和定理提供了欧拉通路与欧拉回路的十分简便的判别准则。,例如，由定理可知，下图(a)图为欧拉图，本图既可以看成圈v1 v2 v8 v1，v2 v3 v4 v2，v4 v5 v6 v4，v6 v7 v8 v6之并(为清晰起见，将4个圈画在(b)中)，也可看成圈v1 v2 v3 v4 v5 v6 v7 v8 v1与圈v2 v4 v6 v8 v2之并(两个圈画在(c)中)。将(a)分解成若干个边不重的圈的并不是(a)图特有性质，任何欧拉图都有这个性质。（a）（b）（c）定理9.1.3 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。,9.1.3 欧拉图的难点 对于欧拉图，需要大家注意以下几点：1仅有欧拉通路而无欧拉回路的图不是欧拉图。2.图中是否存在欧拉通路、欧拉回路的判定非常简单，只要数一下图中节点的度数即可。9.1.4 欧拉图的应用 一笔画问题 所谓“一笔画问题”就是画一个图形，笔不离纸，每条边只画一次而不许重复地画完该图。“一笔画问题”本质上就是一个无向图是否存在欧拉通路（回路）的问题。如果该图为欧拉图，则能够一笔画完该图，并且笔又回到出发点；如果该图只存在欧拉通路，则能够一笔画完该图，但笔回不到出发点；如果该图中不存在欧拉通路，则不能一笔画完该图。,9.2 哈密顿图,9.2.1 哈密顿图的引入和定义 1859年威廉哈密顿爵士发明了一个小玩具，这个小玩具是一个木刻的正十二面体，每面系正五角形，三面交于一角，共有20个角，每角标有世界上一个重要城市，如图所示。他提出一个问题：要求沿正十二面体的边寻找一条路通过20个城市，而每个城市只通过一次，最后返回原地。哈密顿将此问题称为周游世界问题。,图 上述周游世界问题可用图论语言描述为：能否在图所示的图中找到一条包含所有节点的基本回路。按照图中所给城市的编号，容易找到一条从节点1到2，再到3，到4，最后到达20，再回到1的包含图中每个节点的基本回路，即周游世界是可行的。,将这个问题加以推广，即在任意连通图中是否存在一条包含图中所有节点的基本通路或基本回路。定义9.2.1 通过图中每个顶点一次且仅一次的通路（回路）称为哈密顿通路（回路）。一个具有哈密顿回路的图称为哈密顿图。规定：平凡图为哈密顿图。另外，以上定义既适合无向图，又适合有向图。,9.2.2 哈密顿图的判定 尽管讨论哈密顿通路和哈密顿回路在形式上与欧拉通路和欧拉回路非常相似，但遗憾的是到目前为止，仍然没有找到一个合适的条件来作为判断哈密顿通路或哈密顿回路存在的充要条件。不过，可以给出哈密顿通路和哈密顿回路存在的充分条件或必要条件。定理设无向图G=是哈密顿图，V1是V的任意非空子集，则 p(GV1)|V1|其中，p(GV1)是从G中删除V1（删除V1中各个顶点及关联的边）以后所得的连通分支数。,注意：(1)定理给出的是哈密顿图的必要条件，但非充分条件。即，满足此条件的图也未必就是哈密顿图。然而，可以利用该定理判断某些图不是哈密顿图。如图所示的彼得森图，对V的任意非空子集V1，均满足p(G-V1)|V1|，但它不是哈密顿图。图,(2)定理在应用中它本身用处不大，但它的逆否命题却非常有用。经常利用定理的逆否命题来判断某些图不是哈密顿图，即：若存在V的某个非空子集V1使得 p(G-V1)|V1|，则G不是哈密顿图。例如在下图中取V1=v1,v3，则p(G-V1)=4|V1|=2，因而该图不是哈密顿图。,例9.2.2 证明图9.2.4(a)中不存在哈密顿回路。（a）（b）图,分析：利用定理的逆否命题，寻找V的某个非空子集V1使得p(GV1)|V1|，则G不是哈密顿图。找到V1=d,e,f满足要求。证明：在图9.2.4(a)中，删除节点子集d,e,f，得图9.2.4(b)，它的连通分支为4个，由定理知，图9.2.4(a)不是哈密顿图，因而不会存在哈密顿回路。下面给出一些哈密顿图的充分条件。定理设G=是具有n个节点的简单无向图，若对任意的u,vV均有deg(v)+deg(u)n1 则G中存在哈密顿通路。,容易看出，定理中的条件对图中是否存在哈密顿路是充分而不必要的。如图所示的六边形G，虽然任意两个节点度数之和等于4是具有n个节点的简单无向图，n3。如果对任意vV，均有deg(v)n/2，则G是哈密顿图。,定理设G=是具有n个节点的简单无向图，如果对任意两个不相邻的节点u，vV，均有deg(v)+deg(u)n 则G中存在哈密顿回路。这一定理启发引进下述定义，即所谓G的闭包。定义9.2.2 G具有个n顶点，在G中，逐一连接其度数之和至少是n的非邻接顶点对，直到不再有这样的顶点对时为止，这样得到的图称为G的闭包，记作C(G)。可以证明G的闭包是唯一的。图给出了从G构造C(G)的过程。,图 定理9.2.4 无向图G=是哈密顿图，当且仅当G的闭包C(G)是哈密顿图。证明：在构造C(G)的过程中，逐次使用推论就得到这一定理。注意定理形式上给出了判断G是不是哈密顿图的一个充要条件，但因C(G)不一定是完全图，所以在一般情况下判断C(G)是不是哈密顿图的问题仍然没有解决。,如图的闭包还是此图。图 因为至少有三个顶点的完全图是哈密顿图，故由定理可得下面推论。推论9.2.4 设G是无向简单图，n3。若C(G)是完全图，则G是哈密顿图。例9.2.3 某地有5个风景点，若每个风景点均有2条通道与其它点相通。问游人可否经过每个风景点恰好一次而游完这5处？,分析：利用定理即可。解：将5个风景点看成是有5个节点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条通道与其它节点相通，故每个节点的度数均为2，从而任意两个不相邻的节点的度数之和等于4，正好为总节点数减1，故知图中存在一条哈密顿通路。因此游人可以经过每个风景点恰好一次而游完这5处。对于图中有没有哈密顿通路（回路）虽然没有很有效的判别方法，但对于一些较为简单或特殊的图，人们还是积累了一些可行的方法。,关于有向图的哈密顿通路，只给出一个充分条件。定理9.2.5 设G=是有n(n2)个节点的简单有向图。如果忽略G中边的方向所得的无向图中含生成子图Kn，则有向图G中存在哈密顿通路。在下图中，它所对应的无向图中含完全图K5，由定理知，图中含有哈密顿通路。事实上，通路v3 v5 v4 v2 v1是一条哈密顿通路。,这里介绍一种特殊的有向图竞赛图的哈密顿问题。定义 完全图的有向图称为竞赛图。（a）（b）（c）（d）图 图中的(a)、(b)、(c)、(d)分别表示了具有四个节点的竞赛图。定理9.2.6 设G=是一个竞赛图，|V|=n，则G中必有一条哈密顿通路。,在一个竞赛图中，将n个节点代表n个羽毛球运动员，如节点vi到vj间有一条有向边，则表示vi打败了vj。那么竞赛图表示了这n个羽毛球运动员间进行的单循环赛的战绩。由上述定理可以知道：在这样的比赛中，总可以排出一个次序，使得第一名打败第二名，第二名打败第三名。,9.2.3 哈密顿图的难点 对于哈密顿图，需要注意以下几点：1仅有哈密顿通路而无哈密顿回路的图不是哈密顿图。2.还没有判断图中是否存在哈密顿通路、哈密顿回路的简单判定定理，只能对节点较少的图凭经验判定。3.在哈密顿图中有些定理仅是判别的必要条件，必要条件正方面的叙述无法用来判断一个图是否是哈密顿图，此时该定理是毫无用处的，但必要条件的等价逆否命题却非常重要，可以用来判断一个图不是哈密顿图。,9.2.4 哈密顿图的应用 1.巡回售货员问题 巡回售货员问题也称为货郎担问题。有一个售货员，从他所在城市出发去访问n1个城市，要求经过每个城市恰好一次，然后返回原地，问他的旅行路线怎样安排才最经济（即线路最短）？这个问题用图论术语叙述就是：G=是n个节点的赋权完全图，这里V=v1,v2,vn是城市的集合，E是连接城市的道路的集合，W是从E到正实数集合的一个函数（即W(vi,vj)是城市vi与vj之间的距离），显然对V中任意三个城市vi,vj,vk，它们之间的距离应满足三角不等式：W(vi,vj)+W(vj,vk)W(vi,vk)试求出该赋权图上的最短哈密顿回路。,显然，研究这个问题是十分有趣且有实用价值的。但是很可惜，至今尚未找到一个很有效的算法。当然，从理论上说，可以用枚举法来解，但是当完全图的节点较多时，枚举法的运算量是十分惊人的，即使是使用计算机也是很难实现的。我们知道，从第一个城市到第二个城市有n-1种走法，从第二个城市到第三个城市有n-2种走法因而共有(n-1)!种走法，若考虑v1v2vnv1和v1vnvn-1v2v1是同一条回路，还共有1/2(n-1)!条不同的哈密顿回路。为了比较权的大小，对每条哈密顿回路要做n1次加法，故加法的总数为(1/2)(n-1)(n-1)!。例如当有40个城市时，(1/2)(n-1)(n-1)!的近似值为3.771047，假设一台计算机每秒完成1011次（百亿）次加法，将需要超过1.191029年才能完成所需的加法次数，显然是不可能的。,例9.2.7 图9.2.17(a)所示图为4阶完全赋权图K4，求出它的不同哈密顿回路，并指出最短的哈密顿回路。（a）（b）（c）（d）图 C1=a b c d a C4=a c d b a C2=a b d c a C5=a d b c a C3=a c b d a C6=a d c b a,算法9.2.1 最邻近算法（1）以vi为始点，在其余n1个节点中，找出与始点最邻近的节点vj（如果与vi最邻近的节点不唯一，则任选其中的一个作为vj），形成具有一条边的通路vi vj；（2）假设x是最新加入到这条通路中的节点，从不在通路上的节点中选取一个与x最邻近的节点，把连接x与此节点的边加到这条通路中。重复这一步，直到G中所有节点都包含在通路中；（3）把始点和最后加入的节点之间的边放入，就得到一条回路。例9.2.8 用最邻近算法计算图9.2.18(a)的以a为始点的一条近似最短哈密顿回路。分析：利用算法，每次选择与最新加入通路节点最近的节点构成更长的通路。,
