离散数学 欧拉图.ppt.ppt

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