第十五章欧拉图与哈密顿图课件.ppt

,欧拉图与哈密顿图,欧 拉 图,一欧拉通路、欧拉回路、欧拉图、半 欧拉图的定义,定义 通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。,从定义不难看出，欧拉通路是图中经过所有边的简单的生成通路（经过所有顶点的通路称为生成通路），类似地，欧拉回路是经过所有边的简单的生成回路。 在这里做个规定，即平凡图是欧拉图。,图,在图所示各图中，为（）中的欧拉回路，所以（）图为欧拉图。为（）中的一条欧拉通路，但图中不存在欧拉回路，所以（）为半欧拉图。（）中既没有欧拉回路，也没有欧拉通路，所以（）不是欧拉图，也不是半欧拉图。为（）图中的欧拉回路，所以（）图为欧拉图。（），（）图中都既没有欧拉回路，也没有欧拉通路,二、判别定理 定理 无向图是欧拉图当且仅当是连 通图，且中没有奇度顶点。 证: 若是平凡图，结论显然成立， 下面设为非平凡图，设是条边的阶 无向图。并设的顶点集,. 必要性: 因为为欧拉图，所以中存 在欧拉回路，设为中任意一条欧拉回路，, ，都在上，因而连通所以为连通图。又 ，在上每出现一次获得度，若出现次就获得度，即()，所以中无奇度顶点。 充分性: 由于为非平凡的连通图可知，中边数.对作归纳法。 ()时，由的连通性及无奇度顶点可知，只能是一个环，因而为欧拉图。 ()设()时结论成立，要证明时，结论也成立。由的连通性及,无奇度顶点可知，().类似于例，用扩大路径法可以证明中存在长度大于或等于的圈，设为中一个圈，删除上的全部边，得的生成子图 ，设有个连通分支,，每个连通分支至多有条边，且无奇度顶点，并且设与的公共顶点为 ，,，由归纳假设可知，,都是欧拉图，因而都存在欧拉回路，,.最后将还原（即将,删除的边重新加上），并从上的某顶点开始行遍，每遇到 ，就行遍 中的欧拉回路 ，,，最后回到，得回路 ，此回路经过中每条边一次且仅一次并行遍中所有顶点，因而它是中的欧拉回路 ,故为欧拉图。,由定理立刻可知，图中的三个无向图中，只有（）中无奇度顶点，因而（）是欧拉图，而（）、（）都有奇度顶点，因而它们都不是欧拉图。 定理 : 无向图是半欧拉图当且仅当是连通的，且中恰有两个奇度顶点。 证: 必要性 设是条边的阶无向图，因为为半欧拉图，因而中存在欧拉通路,（但不存在欧拉回路），设 为中一条欧拉通路， . ()，若不在的端点出现，显然()为偶数，若在端点出现过，则()为奇数，因为只有两个端点且不同，因而中只有两个奇数顶点。另外，的连通性是显然的。充分性: 设的两个奇度顶点分别 为 和，对加新边（），,得 ()，则是连通且无奇度顶点 的图，由定理可知，为欧拉图，因而存在欧拉回路，而 ()为中一条欧拉通路，所以为半欧拉图。 由定理立即可知，图中（）是半欧拉图，但（）不是半欧拉图。 定理 有向图是欧拉图当且仅当是强连通的且每个顶点的入度都等于出度。本定理的证明类似于定理 .,定理 有向图是半欧拉图当且仅当是单向连通的，且中恰有两个奇度顶点，其中一个的入度比出度大，另一个的出度比入度大，而其余顶点的入度都等于出度。,图,由定理立即可知，图()图为欧拉图，本图既可以看成圈， ，之并（为清晰起见，将个圈画在（）中），也可看成圈与圈之并（两个圈画在（）中）。将（）分解成若干个边不重的圈的并不是（）图特有的性质，任何欧拉图都有这个性质。,定理 是非平凡的欧拉图当且仅当是连通的且为若干个边不重的圈的并。 本定理的证明可用归纳法。 例 设是非平凡的且非环的欧拉图，证明：（）().（）对于中任意两个不同顶点，都存在简单回路含和.,证 （）由定理可知， ()，存在圈，在中，因而()()，故不是桥。由的任意性()，即是边连通图。 （） ()，由的连通性可知，之间必存在路径，设 ()，则在 中与还必连通，否则，与必处于 的不同的连通分支中，这说明在上存在中的桥，这与（）矛盾。于,是在中存在到的路径，显然与边不重，这说明处于形成的简单回路上。三、求欧拉图中欧拉回路的算法 设为欧拉图，一般来说中存在若干条欧拉回路，下面介绍两种求欧拉回路的算法。,算法，能不走桥就不走桥： （）任取()，令.（）设已经行遍，按下面方法来从(),中选取：（）与相关联；（）除非无别的边可供行遍，否则不应该为,中的桥。（）当（）不能再进行时，算法停止。,可以证明，当算法停止时所得简单回路()为中一条欧拉回路。 例 图()是给定的欧拉图。某人用算法求中的欧拉回路时， 走了简单回路 之后(观看他的错误走法)，无法行遍了，试分析在哪步他犯了错误?,图,解: 此人行遍时犯了能不走桥就不走桥的错误，因而他没行遍出欧拉回路。当他走到时，为图()所示。此时为该图中的桥，而均不是桥，他不应该走，而应该走或，他没有走，所以犯了错误。注意，此人在行遍中，在遇到过桥，处遇到过桥，但当时除桥外他无别的边可走，所以当时均走了桥，这是不会犯错误的。,逐步插入回路法 设为阶无向欧拉图，(),，求中欧拉回路的逐步插入回路法的算法如下： 开始 ，*，. 在中任取一条与关联的边()，将及加入到中得到.若 *，转，否则 ，转.,若()()，结束，否则，令()，在中任取一条与中某顶点关联的边，先将改写成起点（终点）为的简单回路，再置*, ,转. 现在再考虑例中图中图（），用逐步插入回路法可以走出多条欧拉回路。现在走出一条来： 开始时，置*，,，经过步得 ， 是长度为的简单回路，见演示中红边所示。 在中有条边与上的顶点相关联，比如取与，先将改写成以为起点（终点）的简单回路： ， 然后置*，再经过步得 ()，后插入的回路为绿色的。,在中，均与上的顶点关联。比如取与，再将改写成以为起点（终点）的简单回路再置*，再经过步得 （）又插入一个长度为的回路。 则()()，故是的一条欧拉回路。,哈密顿图 一、哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图的定义 定义 经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不,具有哈密顿回路的图称为半哈密顿图。平凡图是哈密顿图。 图中所示的三个无向图都有哈密顿回路，所以都是哈密顿图。有向图中，（）具有哈密顿回路，因而它是哈密顿图。（）只有哈密顿通路，但无哈密顿回路，因而它是半哈密顿图，而（）中既无哈密顿回路，也没有哈密顿通路，因而不是哈密顿图，也不是半哈密顿图。,二、哈密顿图与半哈密顿图的一些必要与充分条件 从定义可以看出，哈密顿通路是图中生成的初级通路，而哈密顿回路是生成的初级回路。判断一个图是否为哈密顿图，就是判断能否将图中所有顶点都放置在一个初级回路（圈）上，但这不是一件易事。与判断一个图是否为欧拉图不一样，到目前为止，人们还没有找到哈密顿图简单的充分必要条件。,下面给出的定理都是哈密顿通路（回路）的必要条件或充分条件。 定理 设无向图是哈密顿图，对于任意 ，且 ，均有 () 其中，()为的连通分支数。 证 设为中任意一条哈密顿回路，易知，当中顶点在上均不相邻时，,()达到最大值，而当中顶点在上有彼此相邻的情况时，均有()，所以有().而是的生成子图，所以，有()(). 本定理的条件是哈密顿图的必要条件，但不是充分条件。可以验证彼得松图（图中（）所示）满足定理中的条件，但它不是哈密顿图。当然，若一个图不满足定理中的条件，它一定不是哈密顿图。,推论 设无向图是半哈密顿图，对于任意的 且 均有 () 证： 设是中起于终于的哈密顿通路，令()（在的顶点之间加新边），易知为哈密顿图，由定理可知，().而有()()().,例 在图中给出的三个图都是二部图。它们中的那些是哈密顿图？哪些是半哈密顿图？为什么？ 解 在（）中，易知互补顶点子集。设此二部图为，则. ()，由定理及其推论可知，不是哈密顿图，也不是半哈密顿图。,设（）中图为，则，其中，易知，()，由定理可知，不是哈密顿图，但是半哈密顿图，其实，为中一条哈密顿通路。 设（）中图为. ，其中，中存在哈密顿回路，如，所以,是哈密顿图。,图,对于二部图还能得出下面结论： 一般情况下，设二部图，且，由定理及其推论可以得出下面结论：（）若是哈密顿图，则。（）若是半哈密顿图，则。 （）若，则不是哈密顿图， 也不是半哈密顿图。,例 设是阶无向连通图。证明：若中有割点或桥，则不是哈密顿图。证 读者用定理证明。 下面给出一些哈密顿图和半哈密顿图的充分条件。,定理 设是阶无向简单图，若对于中任意不相邻的顶点，均有 ()() ()则中存在哈密顿通路。 证： 首先证明是连通图。否则至少有两个连通分支，设是阶数为的两个连通分支，设()，()，因为是简单图，所以 ()() ()(),这与（）矛盾，所以必为连通图。 下面证中存在哈密顿通路。设为中用“扩大路径法”得到的“极大路径”，即的始点与终点不与外的顶点相邻。显然有. ()若，则为中哈密顿通路。 ()若，这说明不是哈密顿通路，即中还存在着外的顶点。但可以证明中存在过上所有顶点的圈。,()若与相邻，即()()，则()为满足要求的圈。 ()若与不相邻，设与上的 相邻（，否则()()，这与（）矛盾），此时，至少与 相邻的顶点之一相邻（否则，()()()），设与 相邻（），见图()所示。于是，回路,过上的所有顶点。,图,()下面证明存在比更长的路径。因为，所以外还有顶点，由的连通性可知，存在()() 与上某顶点相邻，见图()所示。删除边（）得路径 比长度大，对上的顶点重新排序，使其成为 ，对重复（）（），在有限步内一定得到的哈密顿通路。,推论 设为()阶无向简单图，若对于中任意两 个不相邻的顶点，均有 ()()()则中存在哈密顿回路，从而为哈密顿图。 证： 由定理可知，中存在哈密顿通路，设为中一条哈密顿通路，若与相邻，设边()，则为中哈密顿回路。若与不相邻，应用,（），同定理证明中的（）类似，可证明存在过上各顶点的圈，此圈即为中的哈密顿回路。 定理 设为阶无向图中两个不相邻的顶点，且()()，则为哈密顿图当且仅当()为哈密顿图（）是加的新边）。 本定理的证明留作习题。,例 在某此国际会议的预备会议中，共有人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于，问能否将这个人排在圆桌旁，使其任何人都能与两边的人交谈。解： 设个人分别为,，作无向简单图，其中,，, , ，且，若与有共同语言，就在之间连无向边（），由此组成边集合，则为阶无向简单图， ，()为与有共同语言的人数。由已知条件可知， 且，均有()().由定理的推论可知，中存在哈密顿回路，设为中一条哈密顿回路，按这条回路的顺序安排座次即可。,从此例更可以看出，哈密顿图是能将图中所有顶点都能安排在某个初级回路上的图。定理 若为（）阶竞赛图，则中具有哈密顿通路。 证： 对作归纳法。时，的基图为，结论成立。设时结论成立。现在设.设(),。令,，易知为阶竞赛图，由归纳假设可知，存在哈密顿通路，设 为其中一条。下面证明可扩到中去。若存在 （），有()，,，而()，见图（）所示，则 为中哈密顿通路。否则， ,，均有()，见图（）所示，则为中哈密顿通路。,图,例 图所示的三个图中哪些是哈密顿图？哪些是半哈密顿图？,图解： 在（）中，存在哈密顿回路，所以（）为哈密顿图。,在（）中， 取，从图中删除得个连通分支，由定理和推论可知，()不是哈密顿图，也不是半哈密顿图。 在（）中，取，从图中删除的个连通分支，由定理可知，它不是哈密顿图。但（）中存在哈密顿通路，所以（）是半哈密顿图。,从以上的讨论可知，判断给定图是否为哈密顿图是个难题。如果在图中能找出哈密顿回路，或满足某充分性定理的条件，则该图为哈密顿图，但这样的定理是不多的。另外，人们可根据哈密顿图的某些必要条件判断某些图不是哈密顿图。 在本节的最后，谈谈哈密顿图名称的来历。年，数学家哈密（）提出一个问题：能否在正十二面体（见图,中的（）上求一条初级回路，使它含图中所有顶点？他形象地将每个顶点比作一个城市，连接两个顶点之间的边看作城市之间的交通线。于是原始问题就变成了所谓的周游世界问题：能否从某个城市出发沿交通线经过每个城市一次并且仅一次，最后回到出发点？哈密顿自己做了肯定的回答。后人为了纪念这位数学家，将经过图中每个顶点一次且仅一次的回路称为哈密顿回路，将有这种回路的图称为哈密顿图。,带权图与货郎担问题 一、带权图 定义 给定图（为无向图或有向图），设：（为实数集）对中任意的边()（为有向图时，），设()，称实数为边上的权，并将标注在边上，称为带权图，此时常将带权图记作.,设 ，称 ()为的权，并记作( )，即 () ().,二、货郎担问题 带权图应用的领域是相当广的，许多图论算法也是针对带权图的。下面介绍的货郎担问题就是针对阶无向完全带权图的。 设有个城市，城市之间均有道路，道路的长度均大于或等于，可能是（对应关联的城市之间无交通线）。一个旅行商从某个城市出发，要经过每个,城市一次且仅一次，最后回到出发的城市，问他如何走才能使他走的路线最短？这就是著名的旅行商问题或货郎担问题。这个问题可化归为如下的图论问题。 设，为一个阶完全带权图，各边的权非负，且有的边的权可能为.求中一条最短的哈密顿回路，这就是货郎担问题的数学模型。,在讨论货郎担问题之前，首先应该弄清楚，在此问题中不同哈密顿回路的含义。将图中生成圈看成一个哈密顿回路，即不考虑始点（终点）的区别以及顺时针行遍与逆时针行遍的区别。 例 图()所示图为阶完全带权图. 求出它的不同的哈密顿回路，并指出最短的哈密顿回路。,图,解 ： 由于货郎担问题中不同哈密顿回路的含义可知，求哈密顿回路从任何顶点出发都可以。下面先求出从点出发，考虑顺时针与逆时针顺序的不同的哈密顿回路。 ,于是，当不考虑顺（逆）时针顺序时，可知，以 为代表，()（见图（）。，以为代表，()（见图（）。，以为代表，().经过比较可知，是最短的哈密顿回路。 由例的分析可知，阶完全带权图中共存在 ()!种不同的哈密顿回路，经过,比较，可找出最短哈密顿回路。n=4时，有3种不同哈密顿回路，n=5时有12种，n=6时，有60种，n=7时，有360种，n=10时，有59!=1 814 400种，由此可见货郎担问题的计算量是相当大的。对于货郎担问题，人们一方面还在寻找好的算法，另一方面也在寻找各种近似算法。,