离散数学 欧拉图离散数学 欧拉图.pptVIP

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