视频字幕
1736年，数学家欧拉解决了著名的柯尼斯堡七桥问题。问题是：能否一次性走过所有七座桥，且每座桥只走一次？欧拉将这个实际问题抽象为图论模型：四块陆地作为顶点，七座桥作为边。通过这种抽象，复杂的地理问题转化为简洁的数学问题，这就是图论的威力。
连通图是图论中的基本概念。连通图指图中任意两个顶点之间都存在路径的图。与之相对的是非连通图，其中某些顶点之间无法到达。顶点的度数是指与该顶点相连的边的数目。例如这个连通图中，顶点4的度数是3，因为有3条边与它相连。连通性是讨论欧拉性质的重要前提条件。
欢迎来到图论课堂！今天我们要学习连通图的Euler性。这个经典问题起源于1736年柯尼斯堡七桥问题：市民们想知道是否能够一次性走过所有七座桥，且每座桥只走一次。数学家Euler通过图论方法完美解决了这个问题，从而诞生了图论这一数学分支。
在学习Euler性之前，我们需要了解图论的基础概念。图由顶点和边组成，顶点的度数是指与该顶点相连的边的数量。连通图是指任意两个顶点之间都存在路径的图。在这个例子中，顶点A连接了3条边，所以它的度数是3。
Euler路径是图论中的核心概念，指不重复地经过图中每条边恰好一次的路径。如果起点和终点相同，则称为Euler回路。这就是著名的一笔画问题。在第一个例子中，我们可以从A点出发，经过B、D、C，再回到A，最后到D，这样就遍历了所有边且每条边只经过一次。三角形是Euler回路的典型例子。
现在我们来学习判断图是否具有Euler性的重要定理。对于连通图，如果所有顶点的度数都是偶数，则存在Euler回路；如果恰好有两个奇度顶点，则存在Euler路径但不存在回路；如果奇度顶点的个数不等于0也不等于2，则既不存在Euler路径也不存在回路。这个定理的证明基于这样的观察：每当我们经过一个顶点时，都会消耗该顶点的两个度数。
Euler理论在实际生活中有广泛的应用，包括路径规划、邮递员问题、电路设计等。解决这类问题的一般步骤是：首先判断图是否连通，然后计算各顶点的度数，统计奇度顶点的个数，最后应用判定定理得出结论。回到最初的柯尼斯堡七桥问题，我们发现有四个奇度顶点，因此无法找到一笔画路径，这完美解释了为什么市民们无法完成这个挑战。
现在我们学习欧拉性的判定定理。对于连通图，存在欧拉回路当且仅当所有顶点的度数都是偶数。存在欧拉路径当且仅当恰好有零个或两个奇度顶点。如果奇度顶点的个数不等于零也不等于二，则不存在欧拉路径。这三个例子分别展示了这些情况：第一个图所有顶点度数为偶数，存在欧拉回路；第二个图有两个奇度顶点，存在欧拉路径；第三个图有四个奇度顶点，不存在欧拉路径。
现在我们来理解定理证明的核心思想。当我们沿着欧拉路径行走时，每经过一个中间顶点，都需要一条边进入和一条边离开，因此消耗该顶点的两个度数。这意味着所有中间顶点的度数必须是偶数。只有起点和终点是特殊的：起点只需要离开，终点只需要进入。因此，奇度顶点只能是起点或终点。回到柯尼斯堡七桥问题，由于有四个奇度顶点，超过了两个的限制，所以无解。