第十五章欧拉图介绍ppt课件.ppt
欧拉图,定义 通过图G的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图，称为欧拉图。通过图G的每条边一次且仅一次的开路称为欧拉路，对应的有半欧拉图。 例1 下图所给出的四个图，哪些是欧拉图、半欧拉图？,Y,N,Y,N,怎么样判断一个图是欧拉图或半欧拉图？,定理15.1 无向图G为欧拉图的充要条件G是连通图且没有奇度顶点。 定理15.2 无向图G是半欧拉图的充要条件G是连通的且恰有两个奇度的顶点。 或半欧拉图有且仅有两个奇点，一个为欧拉路的起点一个为欧拉路的终点。,例2 下图中的各图是否可以一笔画出？,N,Y,Y,N,Y,一笔画问题？P296定理15.1,定理15.3 有向图D为欧拉图的充要条件D是强连通图且每个顶点的入度等于出度。 定理15.4 有向图D是半欧拉图的充要条件D是单向连通的且恰有两个奇度的顶点，其中一个顶点的入度比出度大1，另一个顶点出度比入度大1，而其余顶点的入度等于出度。定理15.5 G是非平凡的欧拉图的充要条件G是连通的且是若干个边不重的圈的并。,Y,相关应用,哥尼斯堡七桥问题 18世纪哥尼斯堡（后来的加里宁格勒）位于立陶宛的普雷格尔上有7座桥，将河中的两个岛和河岸连结，如图1所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。,瑞士数学家欧拉（Euler）解决,抽象出的图应该是？,抽象出的图应该是？,我们当然不能试走！,结论不言而喻！,应用1、右图是某展览馆的平面图，一个参观者能否不重复地穿过每一扇门？如果不能，请说明理由。如果能，应从哪开始走？,右图中只有A，D两个奇点，是一笔画，所以答案是肯定的，应该从A或D展室开始走。,例 一个邮递员投递信件要走的街道如下左图所示，图中的数字表示各条街道的千米数，他从邮局出发，要走遍各街道，最后回到邮局。怎样走才能使所走的行程最短？全程多少千米？,怎么样使非欧拉图变为欧拉图？,除去奇点！,添加边或删除边。,怎么样除去奇点？,该题应该采用的办法？,重复某些边（添加边）。,解：图中共有8个奇点，不可能不重复地走遍所有的路。必须在8个奇点间添加4条线，才能消除所有奇点，从而成为能从邮局出发最后返回邮局的一笔画。当然要在距离最近的两个奇点间添加一条连线，如左上图中虚线所示，共添加4条连线，这4条连线表示要重复走的路，显然，这样重复走的路程最短，全程34千米。走法参考右上图(走法不唯一)。,2、右图中每个小正方形的边长都是100米。小明沿线段从A点到B点，不许走重复路，他最多能走多少米？,该题应该采用的办法？,删除某些边，除去奇点对，将A、B变为基点！,解：这道题大多数同学都采用试画的方法，实际上还是用欧拉图的判定定理来求解更合理、快捷。首先，图中有8个奇点，在8个奇点之间至少要去掉4条线段，才能使这8个奇点变成偶点；其次，从A点出发到B点，A，B两点必须是奇点，现在A，B都是偶点，必须在与A，B连接的线段中各去掉1条线段，使A，B成为奇点。所以至少要去掉6条线段，也就是最多能走1800米，走法如下图。,作业1：一只木箱的长、宽、高分别为5，4，3厘米(见右图)，有一只甲虫从A点出发，沿棱爬行，每条棱不允许重复，则甲虫回到A点时，最多能爬行多少厘米？,作业2 邮递员要从邮局出发，走遍左下图(单位：千米)中所有街道，最后回到邮局，怎样走路程最短？全程多少千米？,问题也是由一则游戏引入的：1859年，爱尔兰数学家Hamilton提出的，如图的正十二面体，以12个正五边形为面。又称为正则柏拉图体。这些正五边形的三边相交与20个顶点的一个多面体。Hamilton用正十二面体代表地球。游戏题的内容是：沿着正十二面体的棱寻找一条旅行路线，通过每个城市恰好一次又回到出发城市。这便是Hamilton回路问题。,哈密尔顿图,定义：通过图G的每个结点一次且仅一次的环称为哈密尔顿环。具有哈密尔顿环的图称为哈密尔顿图。通过图G的每个结点一次且仅一次的开路称为哈密尔顿路。具有哈密尔顿路的图称为半哈密尔顿图。 例3,半哈密尔顿图,哈密尔顿图,哈密尔顿图,N,至今没有一个像欧拉图的充要条件那样的“非平凡的”(不是定义的同义反复)关于哈密顿图、半哈密顿图的充分必要条件，但关于它们的充分性和必要性分别有一些研究成果，我们分别给出。,但能体会到是边多还是边少是哈密顿图的可能大？,一、哈密尔顿图的必要条件定理15.6 若图G=（V，E）是哈密尔顿图，则对于V的任意一个非空子集V1，有p（GV1）|V1| 这里p（GV1）表示从G中删除V1（删除S中的各结点及相关联的边）后所剩图的分图（连通分支）数。|V1|表示V1中的结点数。,推论 若图G=（V，E）是半哈密尔顿图，则对于V的任意一个非空子集V1，有p（GV1）|V1|1.,例4 在图（a）中去掉结点u以后p（Gu）=2，（b）中去掉结点u1和u2以后，p（G u1，u2）=3，由此 可以判定，这两个图都不是哈密尔顿图。,P299例15.4 有割点和桥的图，不是哈密尔顿图。,但必须要说明的是满足定理条件的不一定是哈密顿图。如下图著名的彼得森(Petersen)图是满足定理条件的，但不是哈密顿图。,利用哈密顿图的必要条件可以用来判定某些图不是哈密顿图, 但不便于应用。因为要检查G的顶点集V的所有子集。,二、哈密尔顿图的充分但不必要的条件,定理15.7 设G是n阶的无向简单图，如果G中任意不相邻的顶点u,v，均有d(u)+d(v)n-1,则G中存在哈密尔顿通路。推论 设G是具有n个（n3）个结点的图，如果G中任意不相邻的顶点u,v均有d(u)+d(v)n, 则G是哈密顿图。,不必要 如一个六边形！,证 先证G为一连通图。反证法：若不然，G由若干连通分支所组成。令v1，v2分属于连通分支G1，G2；G1，G2各有n1，n2个顶点。显然n1n，n2n，于是deg(v1) n1 1 ，deg(v2) n2 1，而deg(v1) +deg(v2) n1 + n2 2 n 1，与题设矛盾。,为证G有哈密顿通路，只要在G中构作出一条长为n1的通路。为此令P为G中任意一条长为p1(pn)的通路，设其顶点序列为v1，v2，vp 。我们来扩充这一通路。 （1）如果有v v1，v2，vp，它与v1或vp间有边相关联，那么可立即扩充P为长度为p的通路。 （2）如果v1，vp均只与原通路P上的顶点相邻，如下可证：G中有一条包含v1，v2，vp，长度为p的回路。 如果v1与vp相邻，那么我们已经如愿。 如果v1与vi1 ,vi2 , ,vir相邻，1i1，i2, , irp,考虑vp：,（2.1）若vp与vi1-1 ,vi2-1 , , vir-1之一，例如vi1-1相邻，那么我们便可得到包含v1，v2，vp的回路：（v1，v2，vi1-1 ,vp , vp -1 , ，vi1 , v1）如图8.25（a）所示。 （2.2）若vp不与vi1-1 ,vi2-1 , , vir-1中任何一个相邻，那么deg(vp) p - r - l，因而 deg(v1) + deg(vp) r + p r l = p 1n 1 与题设矛盾，因此（2.2）不可能发生。,现考虑G中这条包含v1，v2，vp、长度为p的回路。由于pnl，故必有回路外顶点v与回路上顶点（例如vk）相邻，如图8.25（b）所示，那么我们可以得到一条长度为p的、包含v1，v2，vp的通路：（v, vk ,vk-1, v1,vi1 ,vi1+1, vp ,vi1-1 , vk+1），如图8.25（c）所示。 重复过程（l），（2）不断扩充通路P，直至它的长度为n 1 ，这时便得到G中的一条哈密顿通路。定理的后半部分仿上可证。,推论 若G是有n(3)个顶点的简单图，对于每一个顶点v满足d(v)n/2，则G是哈密顿图。证明：若G中任意两点都相邻，则有一条哈密顿回路：v1,v2,v3,vn,v1。若G中存在不相邻的点，则对于任意两个都不相邻的点u,v，有d(u)+d(v)=n,由定理 知G是哈密顿图。显然3的完全图是哈密顿图。,定义 给定图G=有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G，对图G重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为是原图G的闭包，记作C(G)。,定理 15.8 当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。,定义：P273 设D为n阶有向简单图,若D的基图为n阶无向完全图Kn ,则称D是n阶竞赛图。,定理15.9 若D为n(n 2)阶竞赛图, 则D中具有哈密顿通路。,证 对n作归纳法。,1) 当n = 2时, D的基图为K2, 结论成立。2) 当n = k时, 结论成立。3) 设V(D) = v1, v2, , vk, vk+1 。令D1 = D - vk+1, 显然, D1为k阶竞赛图。由归纳假设可知: D1存在哈密顿通路。不妨假设: 1=v1v2vk是一条哈密顿通路。下面证明: vk+1可扩到1中。3.1) 存在vr(1 r k), 有: E(D)(i = 1.r-1), E(D), 如下图(a)所示, 则 = v1v2vr-1vk+1vrvk为D中哈密顿通路。3.2) i 1, 2, , k , 均有: E(D), 见下图(b)所示, 则 = 为D中哈密顿通路。,四、应 用：带权图与货郎担问题,定义15.3 给定图G = (G为无向图或有向图), 设W: ER(R为实数集), 对e = (vi, vj)()E(G), 设W(e) = wij, 称实数wij为边e上的权(Weight),在G上, 将权wij标注在边e上, 称G为带权图通常将带权图G记作称eE(G)W(e)为G的权, 记作W(G),货郎担问题设有n个城市, 城市之间有道路, 道路的长度均大于或等于0, 可能是(城市之间无交通线)。一个旅行商从某个城市出发, 要经过每个城市一次且仅一次, 最后回到出发的城市, 问如何才能使他所走的路线最短？这就是著名的旅行商问题或货郎担问题。这个问题可化归为图论问题。,设G = 为一个n阶完全带权图Kn, 各边的权非负, 且有些边的权可能为。求G中一条最短的哈密顿回路, 这就是货郎担问题的数学模型。,例15.7 下图(a)为完全带权图K4, 求出其不同的哈密顿回路, 并指出最短的哈密顿回路。,由货郎担问题中不同哈密顿回路的含义可知: 求哈密顿回路可从任何顶点出发。下面先求出从a点出发, 考虑顺时针与逆时针顺序的不同的哈密顿回路。C1 = abcdaC2 = abdcaC3 = acbdaC4 = acdbaC5 = adbcaC6 = adcba于是, 当不考虑时针顺序时, 可知: C1 = C6, W(C1) = 8 (见图(b)C2 = C4, W(C2) = 10 (见图(c)C3 = C5, W(C3) = 12经过比较可知, C1是最短的哈密顿回路。,在n阶完全带权图中, 共存在(n-1)!/2种不同的哈密顿回路, 经过比较可找出其最短的哈密顿回路。当n=4时, 有3种不同的哈密顿回路当n=5时, 有12种不同的哈密顿回路当n=6时, 有60种不同的哈密顿回路当n=11时, 有59! = 1,814,400种不同的哈密顿回路由此可见: 货郎担问题的计算量是非常大的。对于货郎担问题, 人们一方面在寻找好的算法, 另一方面也在寻找各种近似算法(找次佳的回路或可接受的回路)。,例4 已知关于a，b，c，d，e，f和g的下述事实： a 讲英语； b 讲英语和汉语； c 讲英语、意大利语和俄语； d 讲日语和汉语； e 讲德国和意大利语； f 讲法语、日语和俄语； g 讲法语和德语。 试问这七个人应如何排座位，才能使每个人都能和他身边的人交谈？,解 用结点表示人，用边表示连接的两个人能讲同一种语言，构造出图G如下：,练习4-4 1对下图的4个图，判断哪些是欧拉图，哪些是哈密尔顿图，分别在相应的括号中填入“Y”或“N”来回答。 是否欧拉图 是否哈密尔顿图,（a） （ Y ） （ Y ）,（b） （ Y ） （ N ）,（c） （ N ） （ Y ）,（d） （ N ） （ N ）,2、判别图各图是否为哈密顿图，若不是，请说明理由，并回答它是否有哈密顿通路。,人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。,
