离散数学 欧拉图

《离散数学 欧拉图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8.2欧拉图欧拉通路欧拉回路欧拉图半欧拉图1一、哥尼斯堡七桥问题十八世纪德国哥尼斯堡城位于普雷格尔河畔,河中有两个岛,河两岸和河中的两个岛架起了七座桥与两岛相连.游人从任何一个地点出发走过七座桥且每座桥只走一次,问是否最后又能回到原地,这就是著名的七桥问题.21736年瑞士著名数学家欧拉用图论的方法解决了这个问题欧拉用点表示岛和两岸,用边表示桥。于是问题就归结为这个图是否能一笔画的问题该问题转化为：从图中任意一点出发一笔画出这个图形，并且最后回到出发点。3当图中的点是偶数度时，该图的特点是能进能出或能出能进。欧拉在解决七桥问题时引进了“度”的概念，并对此作了

2、详细分析。4当图中的点是奇数度时，该图的特点是能出不能进或能进不能出。5当连通图的各个顶点都是偶数度时，该图可以一笔画，且始点和终点重合。当一个图中仅有两个奇数度点时，该图也可以一笔画，但必须把其中一个奇数度点作为起点，另一个奇数度点作为终点。由此，欧拉得到如下结论：6二、欧拉定理定义1如果图中存在一条通过各边一次且仅一次的回路，称此回路为欧拉回路或称为欧拉圈。定义2如果图中存在一条通过各边一次且仅一次的通路，称此通路为欧拉通路或称为欧拉链。具有欧拉回路的图称为欧拉图，具有欧拉通路的图称为半欧拉图.几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图

3、.欧拉通路是简单通路,欧拉回路是简单回路.环不影响图的欧拉性.7定理：一个无向连通图是欧拉图的充分必要条件是：图中各点度数都为偶数。一个无向连通图是半欧拉图的充分必要条件是：图中至多有两个奇数度点。8由此，在七桥问题中，其4个顶点都是奇数度点，所以，七桥图不是欧拉图，也不是半欧拉图。因此，这个图不可能一笔画成。9PLAY10如图9.30(a)的每一个结点的度数都是偶数2，所以(a)中有一个欧拉回路，是欧拉图；在图9.30(b)中有两个结点的度数是奇数3，故(b)中有一个欧拉通路，但没有欧拉回路，不是欧拉图；在图9.30(c)中四个结点的度数都是奇数3，(c)

4、中没有欧拉通路，更没有欧拉回路，不是欧拉图。11如图中,(1),(4)为欧拉图;(2),(5)为半欧拉图;(3)，(6)既不是欧拉图,也不是半欧拉图.在(3),(6)中各至少加几条边才能成为欧拉图?121.如图所示的街区，试问甲、乙二人以同样的速度分别从A.B处同时出发走遍所有街道而谁先到达C处?思考:2.一只昆虫是否可以从立方体的一个顶点出发,沿着棱爬行经过每一条棱一次且仅一次,并且最终回到原地.133.指出下列图中哪些是欧拉图，哪些是半欧拉图，如果是，请画出它们的欧拉回路或通路。14将上述方法推广到有向图中可得：定理：一个有向连通图是欧拉图的充分必要条件

5、是：图中每个点的出度和入度相等。一个有向连通图是半欧拉图的充分必要条件是：图中至多有两个奇数度点。其中一个顶点的入度比出度大1，另一个顶点的入度比出度小1。而其他顶点的入度和出度相等。因此，在画欧拉图时，可以从任一点出发，经过图中一条边一次然后回到始点。在画半欧拉图时，从出度比入度大1的那一点出发，经过图中各边，回到入度比出度大1的那一点。15图9.31(a)是强连通的且每一个结点的入度等于出度，都等于1，所以(a)中有一个欧拉回路，是欧拉图；图9.31(b)是单向连通的且有两个结点入度与出度相等，有两个结点入度与出度不相等，其中一个结点入度比出度大1，另一

6、个结点入度比出度小1。故有一个欧拉路，但没有欧拉回路，不是欧拉图；图9.31(c)的四个结点入度与出度都不相等，没有欧拉路，更没有欧拉回路。16欧拉回路问题既是一个有趣的游戏问题,又是一个具有实用价值的问题。作为欧拉回路的应用，邮递员送递信件时一般的邮递路线是需要遍历某些特定的街道,理想地,他应该走一条欧拉路,即不重复地走遍图中的每一条边。一般邮递员感兴趣的是图中的边。17一个邮递员在递送邮件时，每次要走遍他所负责投递范围内的各条街道，然后再回到邮局，他应该按什么样的路线走，能使所走的路程最短？这个问题实际上是在赋权图上找到一条通过各边一次的回路，且各边的权

7、之和最小，称这样的回路为最优回路。18这个问题是我国数学家管梅谷教授于1960年首先提出解决的，所以国际上常称为中国邮路问题19如果邮递员所走街道的图形是一个欧拉图，则中国邮路问题可以理解为图中任何一条欧拉回路都是最优回路。如果图中有度数为奇数的顶点，如图中各边上的权为街道的长度。20图中有两个度数为奇数的顶点：B和E，可以把构成B到E的一条通路的各边都增加一条重复边（即平行边）。由于B到E的通路可以有多条，因此邮递员所走的最短路径问题就归结为求B到E的各通路中重复边的权之和最小的问题，显然（a）图为最优。（a）(b)21思考:求下图中国邮路问题的解.解:如

8、图可知有四个奇数度结点.分别为:deg(v1)=de