第十五章_欧拉图

1、欧拉图欧拉图定义定义 通过图通过图G G的每条边一次且仅一次的回路称为的每条边一次且仅一次的回路称为欧拉回路欧拉回路。存在。存在欧拉回路的图，称为欧拉回路的图，称为欧拉图欧拉图。通过图通过图G的每条边一次且仅一次的的每条边一次且仅一次的开开路路称为称为欧拉路欧拉路，对应的有对应的有半欧拉图半欧拉图。 例例1 1 下图所给出的四个图，哪些是欧拉图、图所给出的四个图，哪些是欧拉图、半欧拉图半欧拉图？YNYN怎么样判断一个图是怎么样判断一个图是欧拉图或欧拉图或半欧拉图半欧拉图？定理定理15.115.1 无向图无向图G G为欧拉图的充要条件为欧拉图的充要条件G G是连通图且没有奇是连通图且没有奇度顶点

2、。度顶点。 定理定理15.215.2 无向图无向图G是半欧拉图的充要条件是半欧拉图的充要条件G是连通的且恰有是连通的且恰有两个奇度的顶点。两个奇度的顶点。 或半欧拉图或半欧拉图有且仅有两个奇点，一个为欧拉路的起点一个有且仅有两个奇点，一个为欧拉路的起点一个为欧拉路的终点。为欧拉路的终点。 例例2 下图中的各图是否可以一笔画出？下图中的各图是否可以一笔画出？NYYNY一笔画问题？一笔画问题？P296定理定理15.1定理定理15.315.3 有向图有向图D D为欧拉图的充要条件为欧拉图的充要条件D D是强连通图且每个是强连通图且每个顶点的入度等于出度。顶点的入度等于出度。 定理定理15.415.4

3、 有向图有向图D是半欧拉图的充要条件是半欧拉图的充要条件D是单向连通的且是单向连通的且恰有两个奇度的顶点，其中一个顶点的入度比出度大恰有两个奇度的顶点，其中一个顶点的入度比出度大1，另一个顶，另一个顶点出度比入度大点出度比入度大1，而其余顶点的入度等于出度。，而其余顶点的入度等于出度。定理定理15.5 G是非平凡的欧拉图的充要条件是非平凡的欧拉图的充要条件G是连通的是连通的且是若干个边不重的圈的并。且是若干个边不重的圈的并。 Y相关应用相关应用哥尼斯堡七桥问题哥尼斯堡七桥问题 18世纪哥尼斯堡（后来的加里宁格勒）位于立世纪哥尼斯堡（后来的加里宁格勒）位于立陶宛的普雷格尔上有陶宛的普雷格尔上有7

4、座桥，将河中的两个岛和河岸连结，如图座桥，将河中的两个岛和河岸连结，如图1所所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个就是七桥问题，一个著名的图论问题著名的图论问题。 瑞士数学家欧拉（瑞士数学家欧拉（Euler）解决）解决 抽象出的图应该是？抽象出的图应该是？抽象出的图应该是？抽象出的图应该是？我们当然不能试走！我们当然不能试走！结论不言而喻！结论不言而喻！ 应用应用1、右图是某展览馆的平

5、面图，一个参观者能否不重、右图是某展览馆的平面图，一个参观者能否不重复地穿过每一扇门？如果不能，请说明理由。如果能，复地穿过每一扇门？如果不能，请说明理由。如果能，应从哪开始走？应从哪开始走？右图中只有右图中只有A，D两个奇点，是一笔画，所以两个奇点，是一笔画，所以答案是肯定的，应该从答案是肯定的，应该从A或或D展室开始走。展室开始走。 例例 一个邮递员投递信件要走的街道如下左图所示，图中的数字一个邮递员投递信件要走的街道如下左图所示，图中的数字表示各条街道的千米数，他从邮局出发，要走遍各街道，最后回表示各条街道的千米数，他从邮局出发，要走遍各街道，最后回到邮局。怎样走才能使所走的行程最短？全

6、程多少千米？到邮局。怎样走才能使所走的行程最短？全程多少千米？邮局邮局 2 1 2111 怎么样使非怎么样使非欧拉图欧拉图变为变为欧拉图？欧拉图？除去奇点！除去奇点！添加边或删除边。添加边或删除边。怎么样除去奇点？怎么样除去奇点？该题应该采用的办法？该题应该采用的办法？重复某些边（添加边）。重复某些边（添加边）。解：解：图中共有图中共有8个奇点，不可能不重复地走遍所有的路。必须在个奇点，不可能不重复地走遍所有的路。必须在8个奇点间添加个奇点间添加4条线，才能消除所有奇点，从而成为能从邮局条线，才能消除所有奇点，从而成为能从邮局出发最后返回邮局的一笔画。当然要在距离最近的两个奇点间出发最后返回邮

7、局的一笔画。当然要在距离最近的两个奇点间添加一条连线，如左上图中虚线所示，共添加添加一条连线，如左上图中虚线所示，共添加4条连线，这条连线，这4条条连线表示要重复走的路，显然，这样重复走的路程最短，全程连线表示要重复走的路，显然，这样重复走的路程最短，全程34千米。走法参考右上图千米。走法参考右上图(走法不唯一走法不唯一)。 2 1 21112、右图中每个小正方形的边长都是、右图中每个小正方形的边长都是100米。小明米。小明沿线段从沿线段从A点到点到B点，不许走重复路，他最多能走点，不许走重复路，他最多能走多少米？多少米？该题应该采用的办法？该题应该采用的办法？删除某些边，除去奇点对，将删除某

8、些边，除去奇点对，将A、B变为基点！变为基点！解：解：这道题大多数同学都采用试画的方法，实际上还是用欧拉这道题大多数同学都采用试画的方法，实际上还是用欧拉图的判定定理来求解更合理、快捷。首先，图中有图的判定定理来求解更合理、快捷。首先，图中有8个奇点，在个奇点，在8个个奇点之间至少要去掉奇点之间至少要去掉4条线段，才能使这条线段，才能使这8个奇点变成偶点；其次，个奇点变成偶点；其次，从从A点出发到点出发到B点，点，A，B两点必须是奇点，现在两点必须是奇点，现在A，B都是偶点，必都是偶点，必须在与须在与A，B连接的线段中各去掉连接的线段中各去掉1条线段，使条线段，使A，B成为奇点。所以成为奇点。

9、所以至少要去掉至少要去掉6条线段，也就是最多能走条线段，也就是最多能走1800米，走法如下图。米，走法如下图。作业作业1：一只木箱的长、宽、高分别为：一只木箱的长、宽、高分别为5，4，3厘米厘米(见见右图右图)，有一只甲虫从，有一只甲虫从A点出发，沿棱爬行，每条棱不允点出发，沿棱爬行，每条棱不允许重复，则甲虫回到许重复，则甲虫回到A点时，最多能爬行多少厘米？点时，最多能爬行多少厘米？作业作业2 邮递员要从邮局出发，走遍左下图邮递员要从邮局出发，走遍左下图(单位：千米单位：千米)中所有街道，最后回到邮局，怎样走路程最短？全程多少中所有街道，最后回到邮局，怎样走路程最短？全程多少千米？千米？问题也

10、是由一则游戏引入的：问题也是由一则游戏引入的：1859年，爱尔兰数学家年，爱尔兰数学家Hamilton提出提出的，如图的正十二面体，以的，如图的正十二面体，以12个个正五边形正五边形为面。又称为正则柏拉图为面。又称为正则柏拉图体。这些正五边形的三边相交与体。这些正五边形的三边相交与20个顶点个顶点的一个多面体。的一个多面体。Hamilton用用正十二面体代表地球正十二面体代表地球。游戏题的内容是：沿着正十二面体的棱寻。游戏题的内容是：沿着正十二面体的棱寻找一条旅行路线，找一条旅行路线，通过每个城市恰好一次又回到出发城市通过每个城市恰好一次又回到出发城市。这便是。这便是Hamilton回路问题。

11、回路问题。哈密尔顿图哈密尔顿图定义定义：通过图：通过图G G的每个的每个结点结点一次且仅一次的环称为一次且仅一次的环称为哈密尔顿环哈密尔顿环。具。具有哈密尔顿环的图称为有哈密尔顿环的图称为哈密尔顿图哈密尔顿图。通过图。通过图G G的每个结点一次且仅的每个结点一次且仅一次的开路称为一次的开路称为哈密尔顿路哈密尔顿路。具有哈密尔顿路的图称为。具有哈密尔顿路的图称为半哈密尔半哈密尔顿图。顿图。 例例3 3半半哈密尔顿图哈密尔顿图 哈密尔顿图哈密尔顿图 哈密尔顿图哈密尔顿图N 至今没有一个像欧拉图的充要条件那样的至今没有一个像欧拉图的充要条件那样的“非平非平凡的凡的”(不是定义的同义反复不是定义的同义

12、反复)关于哈密顿图、半哈密关于哈密顿图、半哈密顿图的充分必要条件，但关于它们的充分性和必要性顿图的充分必要条件，但关于它们的充分性和必要性分别有一些研究成果，我们分别给出。分别有一些研究成果，我们分别给出。但能体会到是边多还是边少是哈密顿图的可能大？但能体会到是边多还是边少是哈密顿图的可能大？一、哈密尔顿图的一、哈密尔顿图的必要条件必要条件定理定理15.6 15.6 若图若图G=G=（V V，E E）是哈密尔顿图，则对于）是哈密尔顿图，则对于V V的任意一的任意一个非空子集个非空子集V V1 1，有，有p p（G GV V1 1）|V|V1 1| | 这里这里p p（G GV V1 1）表示从

13、）表示从G G中删除中删除V V1 1（删除（删除S S中的各结点及相关联中的各结点及相关联的边）后所剩图的分图（连通分支）数。的边）后所剩图的分图（连通分支）数。|V|V1 1| |表示表示V V1 1中的结点数。中的结点数。推论推论 若图若图G=G=（V V，E E）是半哈密尔顿图，则对于）是半哈密尔顿图，则对于V V的任意一的任意一个非空子集个非空子集V V1 1，有，有p p（G GV V1 1）|V|V1 1| |1.1. 例例4 在图（在图（a a）中去掉结点）中去掉结点u u以后以后p p（G Guu）=2=2，（，（b b）中去掉）中去掉结点结点u u1 1和和u u2 2以后

14、，以后，p p（G G u u1 1，u u2 2 ）=3=3，由此，由此 可以判定，这两个图可以判定，这两个图都不是哈密尔顿图。都不是哈密尔顿图。P299例例15.4 有割点和桥的图，不是哈密尔顿图。有割点和桥的图，不是哈密尔顿图。 但必须要说明的是满足定理条件的不一定是哈但必须要说明的是满足定理条件的不一定是哈密顿图。密顿图。 如下图如下图著名的彼得森著名的彼得森(Petersen)图图是满足定理条件是满足定理条件的，但不是哈密顿图。的，但不是哈密顿图。利用哈密顿图的必要条件可利用哈密顿图的必要条件可以用来判定某些图以用来判定某些图不是不是哈密哈密顿图顿图, 但不便于应用。因为要但不便于应

15、用。因为要检查检查G的顶点集的顶点集V的的所有所有子集。子集。二、哈密尔顿图的充分但不必要的条件二、哈密尔顿图的充分但不必要的条件定理定理15.7 15.7 设设G G是是n n阶的无向简单图，如果阶的无向简单图，如果G G中任意不相邻的中任意不相邻的顶点顶点u,vu,v，均有，均有d(u)+d(v)d(u)+d(v)n-1,则则G G中存在哈密尔顿通中存在哈密尔顿通路路。推论推论 设设G G是具有是具有n n个（个（n3n3）个结点的图，如果）个结点的图，如果G G中任意不中任意不相邻的顶点相邻的顶点u,vu,v均有均有d(u)+d(v)n, 则则G G是哈密顿是哈密顿图图。 不必要不必要

16、如一个六边形！如一个六边形！ 证证 先证先证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)的通路，的通

17、路，设其顶点序列为设其顶点序列为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：

18、 （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）不可能发生。）不可能发

19、生。 现考虑现考虑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 ，这时便得到这时便得到

20、G中的一条哈密顿通路。定理的后半部分仿上可证。中的一条哈密顿通路。定理的后半部分仿上可证。 推论推论 若若G G是有是有n(3)n(3)个顶点的简单图，对于每个顶点的简单图，对于每一个顶点一个顶点v v满足满足d(v)n/2d(v)n/2，则，则G G是哈密顿图。是哈密顿图。证明：若证明：若G G中任意两点都相邻，则有一条哈密顿回路：中任意两点都相邻，则有一条哈密顿回路：v v1 1,v,v2 2,v,v3 3, ,v vn n,v,v1 1。若若G G中存在不相邻的点，中存在不相邻的点，则对于任意两个都不相邻的点则对于任意两个都不相邻的点u,vu,v，有有d(u)+d(v)=n,d(u)+d

21、(v)=n,由定理由定理 知知G G是哈密顿图。是哈密顿图。显然显然33的完全图是哈密顿图。的完全图是哈密顿图。 例例5 哈路哈路哈环哈环定义定义 给定图给定图G=有有n个结点，若将图个结点，若将图G中度数之和至中度数之和至少是少是n的非邻接结点连接起来得图的非邻接结点连接起来得图G，对图，对图G 重复上述步重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称骤，直到不再有这样的结点对存在为止，所得到的图，称为是原图为是原图G的的闭包闭包，记作，记作C(G)。定理定理 15.8 当且仅当当且仅当一个简单图的闭包是汉密尔顿图时，一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。这个

22、简单图是汉密尔顿图。定义：定义：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阶竞赛图。阶竞赛图。由归纳假设可知由归纳假设可知: D

23、1存在哈密顿通路。存在哈密顿通路。不妨假设不妨假设: 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为无向

24、图或有向图为无向图或有向图), 设设W: ER(R为实数集为实数集), 对对 e = (vi, vj)() E(G), 设设W(e) = wij, 称实数称实数wij为边为边e上的权上的权(WeightWeight)在在G上上, 将权将权wij标注在边标注在边e上上, 称称G为带权图为带权图通常将带权图通常将带权图G记作记作称称 e E(G)W(e)为为G的权的权, 记作记作W(G)货郎担问题货郎担问题设有设有n个城市个城市, 城市之间有道路城市之间有道路, 道路的长度均大于道路的长度均大于或等于或等于0, 可能是可能是(城市之间无交通线城市之间无交通线)。一个旅行商从某个城市出发一个旅行商从

25、某个城市出发, 要经过每个城市一次且要经过每个城市一次且仅一次仅一次, 最后回到出发的城市最后回到出发的城市, 问如何才能使他所走的路问如何才能使他所走的路线最短？这就是著名的旅行商问题或货郎担问题。线最短？这就是著名的旅行商问题或货郎担问题。这个问题可化归为图论问题。这个问题可化归为图论问题。设设G = 为一个为一个n阶完全带权图阶完全带权图Kn, 各边的权非负各边的权非负, 且且有些边的权可能为有些边的权可能为。求。求G中一条最短的哈密顿回路中一条最短的哈密顿回路, 这就是货郎这就是货郎担问题的数学模型。担问题的数学模型。例例15.7 下图下图(a)为完全带权图为完全带权图K4, 求出其不

26、同的哈密顿回路求出其不同的哈密顿回路, 并指出最短的哈密顿回路。并指出最短的哈密顿回路。由货郎担问题中不同哈密顿回路的含义可知由货郎担问题中不同哈密顿回路的含义可知: 求哈密顿求哈密顿回路可从任何顶点出发。回路可从任何顶点出发。下面先求出从下面先求出从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种不同的哈密顿回