《离散数学欧拉图(精品).ppt》由会员分享，可在线阅读，更多相关《离散数学欧拉图(精品).ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、8.2 欧拉图欧拉图欧拉通路欧拉通路欧拉回路欧拉回路欧拉图欧拉图半欧拉图半欧拉图 1一、哥尼斯堡七桥问题一、哥尼斯堡七桥问题十八世纪德国哥尼斯堡城位于普雷格尔河畔十八世纪德国哥尼斯堡城位于普雷格尔河畔,河中有两个岛河中有两个岛,河两岸和河中的两个岛架起了七座桥与两岛相连河两岸和河中的两个岛架起了七座桥与两岛相连.游人从任何一个地点出发走过七座桥且每座桥只走一次游人从任何一个地点出发走过七座桥且每座桥只走一次,问是否最后又能回到原地问是否最后又能回到原地,这就是著名的七桥问题这就是著名的七桥问题.21736年瑞士著名数学家欧拉用图论的方法解决了这个问题年瑞士著名数学家欧拉用图论的方法解决了这个问
2、题欧拉用点表示岛和两岸欧拉用点表示岛和两岸,用边表示桥。用边表示桥。于是问题就归结为这个图是否能一笔画的问题于是问题就归结为这个图是否能一笔画的问题该问题转化为：从图中任意一点出发一笔画出这个图形，该问题转化为：从图中任意一点出发一笔画出这个图形，并且最后回到出发点。并且最后回到出发点。3l当图当图中的点是偶数度时，该图的特点是能进能中的点是偶数度时，该图的特点是能进能 出或能出能进。出或能出能进。欧拉在解决七桥问题时引进了欧拉在解决七桥问题时引进了“度度”的的概念，并对此作了详细分析。概念，并对此作了详细分析。4l当图中的点是奇数度时，该图的特点是能出当图中的点是奇数度时，该图的特点是能出不
3、能进或能进不能出。不能进或能进不能出。5当连通图的各个顶点都是偶数度时，该图可当连通图的各个顶点都是偶数度时，该图可 以一笔画，且始点和终点重合。以一笔画，且始点和终点重合。当一个图中仅有两个奇数度点时，该图也可以一笔画，但必须当一个图中仅有两个奇数度点时，该图也可以一笔画，但必须把其中一个奇数度点作为起点，另一个奇数度点作为终点。把其中一个奇数度点作为起点，另一个奇数度点作为终点。l 由此，欧拉得到如下结论：由此，欧拉得到如下结论：6二、欧拉定理二、欧拉定理l定义定义1 如果图中存在一条通过各边一次且仅如果图中存在一条通过各边一次且仅 一次的回路，称此回路为欧拉回路或一次的回路，称此回路为欧
4、拉回路或 称为欧拉圈。称为欧拉圈。定义定义2 如果图中存在一条通过各边一次且仅如果图中存在一条通过各边一次且仅 一次的通路，称此通路为欧拉通路或一次的通路，称此通路为欧拉通路或 称为欧拉链。称为欧拉链。具有欧拉回路的图称为欧拉图，具有欧拉回路的图称为欧拉图，具有欧拉通路的图称为半欧拉图具有欧拉通路的图称为半欧拉图.几点说明：几点说明：上述定义对无向图和有向图都适用上述定义对无向图和有向图都适用.规定平凡图为欧拉图规定平凡图为欧拉图.欧拉通路是简单通路欧拉通路是简单通路,欧拉回路是简单回路欧拉回路是简单回路.环不影响图的欧拉性环不影响图的欧拉性.7 定理：一个无向连通图是欧拉图的充分必要条件定理
5、：一个无向连通图是欧拉图的充分必要条件 是：图中各点度数都为偶数。是：图中各点度数都为偶数。一个无向连通图是半欧拉图的充分必要条一个无向连通图是半欧拉图的充分必要条 件是：图中至多有两个奇数度点。件是：图中至多有两个奇数度点。8由此，在七桥问题中，其由此，在七桥问题中，其4个顶点都是奇数度点，个顶点都是奇数度点，所以，七桥图不是欧拉图，也不是半欧拉图。所以，七桥图不是欧拉图，也不是半欧拉图。因此，这个图不可能一笔画成。因此，这个图不可能一笔画成。9PLAY10 如图如图9.30(a)的每一个结点的度数都是偶数的每一个结点的度数都是偶数2，所以，所以(a)中有一个欧拉回路，是欧拉图；在图中有一个
6、欧拉回路，是欧拉图；在图9.30(b)中有两个结点中有两个结点的度数是奇数的度数是奇数3，故，故(b)中有一个欧拉通路，但没有欧拉回中有一个欧拉通路，但没有欧拉回路，不是欧拉图；在图路，不是欧拉图；在图9.30(c)中四个结点的度数都是奇数中四个结点的度数都是奇数3，(c)中没有欧拉中没有欧拉通通路，更没有欧拉回路，不是欧拉图。路，更没有欧拉回路，不是欧拉图。11如图中如图中,(1),(4)为欧拉图为欧拉图;(2),(5)为半欧拉图为半欧拉图;(3)，(6)既不是欧拉图既不是欧拉图,也不是半欧拉图也不是半欧拉图.在在(3),(6)中各至少加几条边才能成为欧拉图中各至少加几条边才能成为欧拉图?1
7、21.如如图所示的图所示的街区，试问甲、乙二人以同样的速度分别街区，试问甲、乙二人以同样的速度分别从从A.B处同时出发走遍所有街道而谁先到达处同时出发走遍所有街道而谁先到达C处处?思考思考:2.2.一只昆虫是否可以从立方体的一个顶点出发一只昆虫是否可以从立方体的一个顶点出发,沿着棱沿着棱爬行经过每一条棱一次且仅一次爬行经过每一条棱一次且仅一次,并且最终回到原地并且最终回到原地.13l3.指出下列图中哪些是欧拉图，哪些是半欧拉图，指出下列图中哪些是欧拉图，哪些是半欧拉图，如果是，请画出它们的欧拉回路或通路。如果是，请画出它们的欧拉回路或通路。14将上述方法推广到有向图中可得：将上述方法推广到有向
8、图中可得：定理：一个有向连通图是欧拉图的充分必要条件定理：一个有向连通图是欧拉图的充分必要条件 是：是：图中每个点的出度和入度相等。图中每个点的出度和入度相等。一个有向连通图是半欧拉图的充分必要条件是：一个有向连通图是半欧拉图的充分必要条件是：图中至多有两个奇数度点。其中一个顶点的入度图中至多有两个奇数度点。其中一个顶点的入度 比出度大比出度大1，另一个顶点的入度比出度小，另一个顶点的入度比出度小1。而其他顶点的入度和出度相等。而其他顶点的入度和出度相等。l因此，在画欧拉图时，可以从任一点出发，经过因此，在画欧拉图时，可以从任一点出发，经过图中一条边一次然后回到始点。图中一条边一次然后回到始点
9、。l在画半欧拉图时，从出度比入度大在画半欧拉图时，从出度比入度大1的那一点出发，的那一点出发，经过图中各边，回到入度比出度大经过图中各边，回到入度比出度大1的那一点。的那一点。15 图图9.31(a)是强连通的且每一个结点的入度等于出度，是强连通的且每一个结点的入度等于出度，都等于都等于1，所以，所以(a)中有一个欧拉回路，是欧拉图；图中有一个欧拉回路，是欧拉图；图9.31(b)是单向连通的且有两个结点入度与出度相等，有两个结是单向连通的且有两个结点入度与出度相等，有两个结点入度与出度不相等，其中一个结点入度比出度大点入度与出度不相等，其中一个结点入度比出度大1，另一，另一个结点入度比出度小个
10、结点入度比出度小1。故有一个欧拉路，但没有欧拉回路，。故有一个欧拉路，但没有欧拉回路，不是欧拉图；图不是欧拉图；图9.31(c)的四个结点入度与出度都不相等，没的四个结点入度与出度都不相等，没有欧拉路，更没有欧拉回路。有欧拉路，更没有欧拉回路。16l欧拉回路问题既是一个欧拉回路问题既是一个有趣的游戏有趣的游戏问题问题,又是一个具有又是一个具有实用价值实用价值的问题。的问题。l作为欧拉回路的应用，邮递员送递信件时一般作为欧拉回路的应用，邮递员送递信件时一般的邮递路线是需要的邮递路线是需要遍历某些特定的街道遍历某些特定的街道,理想理想地地,他应该走一条欧拉路他应该走一条欧拉路,即即不重复地走遍图不
11、重复地走遍图中的每一条边中的每一条边。l一般邮递员一般邮递员感兴趣的是图中的边感兴趣的是图中的边。17一个邮递员在递送邮件时，每次要走遍他一个邮递员在递送邮件时，每次要走遍他所负责投递范围内的各条街道，然后再回所负责投递范围内的各条街道，然后再回到邮局，他应该按什么样的路线走，能使到邮局，他应该按什么样的路线走，能使所走的路程最短？所走的路程最短？这个问题实际上是在赋权图上找到一条通过各这个问题实际上是在赋权图上找到一条通过各边一次的回路，且各边的权之和最小，称这样边一次的回路，且各边的权之和最小，称这样的回路为最优回路。的回路为最优回路。18l这个问题是我国数学家管梅谷教授于这个问题是我国数
12、学家管梅谷教授于1960年首先提出解决的，所以国际上常年首先提出解决的，所以国际上常称为称为中国邮路问题中国邮路问题19l如果邮递员所走街道的图形是一个欧拉图，如果邮递员所走街道的图形是一个欧拉图，则中国邮路问题可以理解为图中任何一条欧则中国邮路问题可以理解为图中任何一条欧拉回路都是最优回路。拉回路都是最优回路。l如果图中有度数为奇数的顶点，如图中各边上如果图中有度数为奇数的顶点，如图中各边上 的权为街道的长度。的权为街道的长度。20 图中有两个度数为奇数的顶点：图中有两个度数为奇数的顶点：B和和E，可以把构成可以把构成B到到 E的一条通路的各边都增加一条重复边（即平行边）。的一条通路的各边都
13、增加一条重复边（即平行边）。由于由于由于由于B B到到到到E E的通路可以有多条，因此邮递员所走的最短路径问题就的通路可以有多条，因此邮递员所走的最短路径问题就的通路可以有多条，因此邮递员所走的最短路径问题就的通路可以有多条，因此邮递员所走的最短路径问题就归结为求归结为求归结为求归结为求B B到到到到E E的各通路中重复边的权之和最小的问题，显然的各通路中重复边的权之和最小的问题，显然的各通路中重复边的权之和最小的问题，显然的各通路中重复边的权之和最小的问题，显然（a a）图为最优。图为最优。图为最优。图为最优。（a）(b)21思考思考:求下图中国邮路问题的解求下图中国邮路问题的解.解解:如图可知有四个奇数度结点如图可知有四个奇数度结点.分别为分别为:deg(v1)=deg(v2)=deg(v5)=deg(v7)且且W(v1,v2)=3,W(v1,v5)=8,W(v1,v7)=9,W(v2,v5)=5,W(v2,v7)=7,W(v5,v7)=5从中选出两条长度总和最小的通路从中选出两条长度总和最小的通路p1=v1v2和和p2=v7v8v5.构造出如图所示的邮路问题的解构造出如图所示的邮路问题的解.22