离散数学 课件 6.4 欧拉图

第六章·图论6.4欧拉图EulerGraphs从“哥尼斯堡七桥问题”到图论的经典模型目录CONTENTS01欧拉图的概念与起源从经典的哥尼斯堡七桥问题切入，探究欧拉路与欧拉回路的数学定义与历史渊源。02欧拉图的判定方法系统梳理无向图与有向图的欧拉性判定定理，掌握核心的图论算法逻辑。03欧拉图的应用解析经典的“一笔画”谜题，并探讨欧拉图在“中国邮递员问题”中的最优路径规划应用。6.4.1欧拉图的概念：哥尼斯堡七桥问题18世纪普鲁士哥尼斯堡（今俄罗斯加里宁格勒）

普雷格尔河上的七座桥连接两岸和两个岛屿图论的起源与诞生历史背景：数学界的经典难题1736年，瑞士数学家欧拉(Euler)解决了该问题，并以此撰写了论文，标志着图论(GraphTheory)这一学科的诞生。核心问题：路径的可行性能否从任意一块陆地出发，经过每座桥恰好一次，最后返回到出发点？抽象化建模思维将陆地抽象为“结点(Vertex)”，桥抽象为“边(Edge)”。问题转化为寻找经过每条边一次且仅一次的回路。定义6.24：欧拉路与欧拉回路给定一个没有孤立结点的无向图G，若存在一条通路，经过图中每一边一次且仅一次，称该通路为欧拉路(Eulerpaths)；若存在一条回路，经过图中每一边一次且仅一次，称该回路为欧拉回路(Eulercircuits)。具有欧拉回路的图称为欧拉图(Euleriangraph)。欧拉路·最短通路欧拉路是经过图中所有边的通路中长度最短的通路，其长度等于图中边的总数。欧拉回路·最短回路欧拉回路是经过图中所有边的回路中长度最短的回路，其长度也等于图中边的总数。欧拉图、欧拉路与非欧拉图示例图(a)·欧拉图当图中所有结点的度数均为偶数时，该图存在欧拉回路，被称为欧拉图。图(b)·存在欧拉路当图中恰好有2个奇数度结点，其余均为偶数度时，该图存在欧拉路，但不是欧拉图。图(c)·无欧拉路当图中奇数度结点数量超过2个时，该图既不存在欧拉路，也不存在欧拉回路。6.4.2欧拉图的判定方法定理6.11：无向图欧拉路的判定无向图G存在欧拉路，当且仅当G是连通的，且有0个或2个奇数度结点。注：若奇数度结点数为0，则G存在欧拉回路(起点=终点)；若为2，则这两个结点分别是欧拉路的起点和终点。必要性证明思路在欧拉路中，除了起点和终点外，每一个中间结点都满足“每进入一次，必离开一次”。因此，这些中间结点的度数一定是偶数。只有起点和终点的度数可以是奇数（若存在）。充分性证明思路采用“构造法”证明：从奇数度结点出发（若无奇数度结点，则任选一点），每步选取一条未走过的边向前延伸，逐步构建出一条完整的通路。由于图是连通的且满足度数条件，最终可以遍历所有边形成欧拉路。推论6.2：无向图欧拉图的判定推论内容无向图G存在欧拉回路（即G是欧拉图），当且仅当G是连通的，并且所有结点的度数均为偶数。本质解析这是定理6.11的一个特例，即图中奇数度结点数量为0的情况。此时，欧拉路径的起点和终点完全重合，从而形成一条闭合的回路，即欧拉回路。推论6.3：有向图的判定欧拉回路(EulerCircuit)一个有向图G具有一条单向欧拉回路，当且仅当G是强连通的，并且：图中每个结点的入度等于出度。欧拉路(EulerPath)一个有向图G存在欧拉路，当且仅当G是连通的，且满足：●有且仅有一个结点的出度=入度+1（作为路径起点）●有且仅有一个结点的入度=出度+1（作为路径终点）●其余所有结点的入度等于出度例题6.16：判断欧拉路与欧拉图图(a)·欧拉图经过度数统计，图中所有结点的度数均为偶数。根据判定定理，该图存在欧拉回路，是欧拉图。图(b)·无欧拉路经计算，图中奇数度结点的数量超过2个。根据判定定理，该图既没有欧拉路，也不是欧拉图。图(c)·存在欧拉路经统计，图中恰好存在2个奇数度的结点。根据判定定理，该图存在欧拉路，但不是欧拉图。6.4.3欧拉图的应用：一笔画问题问题本质：判断一个图形能否“一笔画”，本质上就是判断该图形对应的图是否存在欧拉路或欧拉回路。1.欧拉路图中有且仅有两个奇数度结点，可以一笔画。从一个奇数度结点出发，到另一个结束。2.欧拉回路图中所有结点的度数均为偶数，可以一笔画。从任意结点出发，最后回到该结点。3.无解情况图中奇数度结点的数量超过两个，无法一笔画。例题6.17：无向图一笔画判断图(a)：存在欧拉路•度数分析：结点b和c的度数为3（奇数），其余所有结点的度数均为偶数。•结论：图中存在欧拉路，一笔画时必须从奇数度顶点出发，因此可以从b或c开始。图(b)：存在欧拉回路•度数分析：图中所有结点的度数均为4（偶数），无奇数度顶点。•结论：图中存在欧拉回路，可从任意结点出发，一笔画完整图后最终回到起点。例题6.18：有向图一笔画判断图(a)：无欧拉路不满足有向图欧拉路的判定条件。

图中结点的度数不满足“仅有一个入度比出度大1的终点和一个出度比入度大1的起点”的规则。图(b)：存在欧拉路满足有向图欧拉路的条件。

图中存在且仅存在：一个起点（出度比入度大1）和一个终点（入度比出度大1），其余所有结点入度等于出度。图(c)：存在欧拉回路满足有向图欧拉回路的条件。

图中所有结点的入度严格等于出度，可以从任意点出发，一笔画完所有边并回到起始点。应用：中国邮递员问题问题描述邮递员从邮局出发，需要走遍其负责街区的每一条街道至少一次，最后回到邮局。如何规划路线才能使总路程最短？这一问题由我国数学家管梅谷教授于1962年首次提出并研究，因此在国际上被称为“中国邮递员问题”(ChinesePostmanProblem,CPP)。图论建模将街区地图抽象为一个带权无向图G=(V,E,w)：•街道的交叉路口→图的顶点集V•连接路口的街道→图的边集E•街道的长度→边的权重函数w(e)问题转化为：在图G中寻找一条经过每条边至少一次的最短回路（最优投递路线）。中国邮递员问题的解决方案01/理想情况：直接利用欧拉回路如果图本身就是欧拉图（即图中所有结点的度数均为偶数），此时图中天然存在一条经过每条边一次且仅一次的回路。这条欧拉回路即为邮递员需要的最短投递路线，无需重复经过任何道路。02/一般情况：构造最优解策略若图中有2k个奇数度结点（k>1），则需重复经过部分边：

1.将这2k个奇数度结点进行两两配对；

2.找出每对结点间的最短路径并重复行走；

3.重复后形成的新图是欧拉图，其欧拉回路即为原问题的最优解。图：邮递员问题中的图论路径与结点度数示意本章总结欧拉图(EulerianGraph)定义：在连通图中，存在一条经过所有边一次且仅一次的回路。若一个图存在欧拉回路，则称它为欧拉图。欧拉路(EulerianTrail)定义：在连通图中，存在一条经过所有边一次且仅一次的通路（非闭合）。它与欧拉图最大的区别在于起点与终点不重合。判定定理(KeyCriteria)•无向图：欧拉路(0/2个奇度顶点)，欧拉图(0个奇度顶点)。•有向图：欧拉回