离散数学欧拉.pptVIP

8.2 欧拉图;一、哥尼斯堡七桥问题;1736年瑞士著名数学家欧拉用图论的方法解决了这个问题;当图中的点是偶数度时，该图的特点是能进能 出或能出能进。 ; 当图中的点是奇数度时，该图的特点是能出 不能进或能进不能出。 ; 当连通图的各个顶点都是偶数度时，该图可 以一笔画，且始点和终点重合。;二、欧拉定理; 定理：一个无向连通图是欧拉图的充分必要条件 是：图中各点度数都为偶数。 一个无向连通图是半欧拉图的充分必要条 件是：图中至多有两个奇数度点。;由此，在七桥问题中，其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处?;3. 指出下列图中哪些是欧拉图，哪些是半欧拉图， 如果是，请画出它们的欧拉回路或通路。;将上述方法推广到有向图中可得：; 图9.31(a)是强连通的且每一个结点的入度等于出度，都等于1，所以(a)中有一个欧拉回路，是欧拉图；图9.31 (b)是单向连通的且有两个结点入度与出度相等，有两个结点入度与出度不相等，其中一个结点入度比出度大1，另一个结点入度比出度小1。故有一个欧拉路，但没有欧拉回路，不是欧拉图；图9.31(c)的四个结点入度与出度都不相等，没有欧拉路，更没有欧拉回路。 ;欧拉回路问题既是一个有趣的游戏问题, 又是一个具有实用价值的问题。 作为欧拉回路的应用，邮递员送递信件时一般的邮递路线是需要遍历某些特定的街道, 理想地, 他应该走一条欧拉路, 即不重复地走遍图中的每一??边。 一般邮递员感兴趣的是图中的边。;一个邮递员在递送邮件时，每次要走遍他 所负责投递范围内的各条街道，然后再回 到邮局，他应该按什么样的路线走，能使 所走的路程最短？ ;这个问题是我国数学家管梅谷教授于 1960年首先提出解决的，所以国际上常 称为中国邮路问题;如果邮递员所走街道的图形是一个欧拉图，则中国邮路问题可以理解为图中任何一条欧拉回路都是最优回路。; 图中有两个度数为奇数的顶点：B和E，可以把构成B到 E的一条通路的各边都增加一条重复边（即平行边）。;思考:求下图中国邮路问题的解.