第十五章-欧拉图介绍

欧拉图定义通过图G的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图，称为欧拉图。通过图G的每条边一次且仅一次的开路称为欧拉路，对应的有半欧拉图。例1下图所给出的四个图，哪些是欧拉图、半欧拉图？YNYN怎么样判断一个图是欧拉图或半欧拉图？定理15.1无向图G为欧拉图的充要条件G是连通图且没有奇度顶点。定理15.2无向图G是半欧拉图的充要条件G是连通的且恰有两个奇度的顶点。或半欧拉图有且仅有两个奇点，一个为欧拉路的起点一个为欧拉路的终点。例2下图中的各图是否可以一笔画出？NYYNY一笔画问题？P296定理15.1定理15.3有向图D为欧拉图的充要条件D是强连通图且每个顶点的入度等于出度。定理15.4有向图D是半欧拉图的充要条件D是单向连通的且恰有两个奇度的顶点，其中一个顶点的入度比出度大1，另一个顶点出度比入度大1，而其余顶点的入度等于出度。定理15.5G是非平凡的欧拉图的充要条件G是连通的且是若干个边不重的圈的并。Y相关应用哥尼斯堡七桥问题18世纪哥尼斯堡（后来的加里宁格勒）位于立陶宛的普雷格尔上有7座桥，将河中的两个岛和河岸连结，如图1所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。瑞士数学家欧拉（Euler）解决抽象出的图应该是？抽象出的图应该是？我们当然不能试走！结论不言而喻！应用1、右图是某展览馆的平面图，一个参观者能否不重复地穿过每一扇门？如果不能，请说明理由。如果能，应从哪开始走？右图中只有A，D两个奇点，是一笔画，所以答案是肯定的，应该从A或D展室开始走。例一个邮递员投递信件要走的街道如下左图所示，图中的数字表示各条街道的千米数，他从邮局出发，要走遍各街道，最后回到邮局。怎样走才能使所走的行程最短？全程多少千米？邮局212111怎么样使非欧拉图变为欧拉图？除去奇点！添加边或删除边。怎么样除去奇点？该题应该采用的办法？重复某些边（添加边）。解：图中共有8个奇点，不可能不重复地走遍所有的路。必须在8个奇点间添加4条线，才能消除所有奇点，从而成为能从邮局出发最后返回邮局的一笔画。当然要在距离最近的两个奇点间添加一条连线，如左上图中虚线所示，共添加4条连线，这4条连线表示要重复走的路，显然，这样重复走的路程最短，全程34千米。走法参考右上图(走法不唯一)。2121112、右图中每个小正方形的边长都是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（G–V1）≤|V1|这里p（G–V1）表示从G中删除V1（删除S中的各结点及相关联的边）后所剩图的分图（连通分支）数。|V1|表示V1中的结点数。推论若图G=（V，E）是半哈密尔顿图，则对于V的任意一个非空子集V1，有p（G–V1）≤|V1|＋1.例4在图（a）中去掉结点u以后p（G–{u}）=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个（n≥3）个结点的图，如果G中任意不相邻的顶点u,v均有d(u)+d(v)≥n,则G是哈密顿图。不必要如一个六边形！证先证G为一连通图。反证法：若不然，G由若干连通分支所组成。令v1，v2分属于连通分支G1，G2；G1，G2各有n1，n2个顶点。显然n1≤n，n2≤n，于是deg(v1)≤n1–1，deg(v2)≤n2–1，而deg(v1)+deg(v2)≤n1+n2–2＜n–1，与题设矛盾。为证G有哈密顿通路，只要在G中构作出一条长为n－1的通路。为此令P为G中任意一条长为p－1(p＜n)的通路，设其顶点序列为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相邻，1＜i1，i2,…,ir＜p,考虑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–1＜n–1与题设矛盾，因此（2.2）不可能发生。现考虑G中这条包含v1，v2，…，vp、长度为p的回路。由于p≤n－l，故必有回路外顶点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的完全图是哈密顿图。例5哈路哈环定义给定图G=V,E有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=v’1v’2…v’k是一条哈密顿通路。下面证明:vk+1可扩到1中。3.1)存在v’r(1rk),有:v’i,vk+1E(D)(i=1..r-1),vk+1,v’rE(D),如下图(a)所示,则=v’1v’2…v’r-1vk+1v’r…v’k为D中哈密顿通路。3.2)i{1,2,…,k},均有:v’i,vk+1E(D),见下图(b)所示,则='∪v’k,vk+1为D中哈密顿通路。四、应用：带权图与货郎担问题定义15.3给定图G=V,E(G为无向图或有向图),设W:E→R(R为实数集),对e=(vi,vj)(vi,vj)E(G),设W(e)=wij,称实数wij为边e上的权(Weight)在G上,将权wij标注在边e上,称G为带权图通常将带权图G记作V,E,W称eE(G)W(e)为G的权,记作W(G)货郎担问题设有n个城市,城市之间有道路,道路的长度均大于或等于0,可能是∞(城市之间无交通线)。一个旅行商从某个城市出发,要经过每个城市一次且仅一次,最后回到出发的城市,问如何才能使他所走的路线最短？这就是著名的旅行商问题或货郎担问题。这个问题可化归为图论问题。设G=V,E,W为一个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时,有5×9!=1,814,400种不同的哈密顿回路…由此可见:货郎担问题的计算量是非常大的。对于货郎担问题,人们一方面在寻找好的算法,另一方面也在寻找各种近似算法(找次佳的回路或可接受的回路)。例4已知关于a，b，c，d，e，f和g的下述事实：a讲英语；b讲英语和汉语；c讲英语、意大利语和俄语；d讲日语和汉语；e讲德国和意大利语；f讲法语、日语和俄语；g讲法语和德语。试问这七个人应如何排座位，才能使每个人都能和他身边的人交谈？解用结点表示人，用边表示连接的两个人能讲同一种语言，构造出图G如下：练习4-41．对下图的4个图，判断哪些是欧拉图，哪些是哈密尔顿图，分别在相应的括号中填入“Y”或“N”来回答。是否欧拉图是否哈密尔顿图（a）（Y）（Y）（b）（Y）（N）（c）（N）（Y）（d）（N）（N）2、判别图各图是否为哈密顿图，若不是，请说明理由，并回答它是否有哈密顿通路。2n人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古