📚 Eulerian Graphs | 欧拉图
Eulerian graphs are a fascinating topic in graph theory, named after the great mathematician Leonhard Euler. They arise from the famous Königsberg bridge problem and form a key part of the Edexcel A-Level Further Mathematics Decision module. Understanding Eulerian graphs helps solve practical routing problems where every connection must be traversed exactly once.
欧拉图是图论中一个引人入胜的话题，以伟大数学家莱昂哈德·欧拉命名。它们源于著名的哥尼斯堡七桥问题，是爱德思A-Level进阶数学决策模块的重要内容。理解欧拉图有助于解决必须恰好遍历每条连线一次的实际路径规划问题。
1. Graph Theory Basics | 图论基础
A graph consists of vertices (or nodes) and edges that connect them. The degree of a vertex is the number of edges incident to it. In decision mathematics, we often consider simple, undirected graphs. A trail is a sequence of edges where no edge is repeated; a circuit is a closed trail.
图由顶点（或节点）以及连接它们的边组成。顶点的度是指与其相连的边的数目。在决策数学中，我们通常考虑简单的无向图。迹是指边不重复的路径；回路则是闭合的迹。
A graph is connected if there is a path between every pair of vertices. Eulerian concepts require the graph to be connected, ignoring isolated vertices. Disconnected graphs cannot have a single trail covering all edges without jumping between components.
如果任意两个顶点之间都存在路径，则图是连通的。欧拉概念要求图必须是连通的，忽略孤立顶点。不连通的图无法用一条迹覆盖所有边而不在分量间跳跃。
2. What is an Eulerian Graph? | 什么是欧拉图？
An Eulerian graph is a connected graph that contains an Eulerian circuit. An Eulerian circuit (or Eulerian cycle) is a closed trail that includes every edge of the graph exactly once, starting and ending at the same vertex. If such a circuit exists, the graph is said to be Eulerian.
欧拉图是指包含欧拉回路的连通图。欧拉回路（或欧拉圈）是一条恰好包含图中每条边一次且起点与终点重合的闭迹。如果存在这样的回路，该图就被称为欧拉图。
Historically, Euler solved the Königsberg bridge problem in 1736, proving that no Eulerian circuit exists for the given configuration because more than two vertices had odd degree. This marked the birth of graph theory as a field of mathematics.
历史上，欧拉于1736年解决了哥尼斯堡七桥问题，证明了对于给定的配置不存在欧拉回路，因为超过两个顶点的度数为奇数。这标志着图论作为数学分支的诞生。
3. Eulerian Trail vs Eulerian Circuit | 欧拉路径与欧拉回路
Sometimes a graph may not have an Eulerian circuit but does have an Eulerian trail. An Eulerian trail (or Eulerian path) is a trail that uses every edge exactly once but does not necessarily end at the starting vertex. Such graphs are called semi-Eulerian.
有时一个图可能没有欧拉回路但拥有欧拉路径。欧拉路径（或欧拉迹）是一条恰好使用每条边一次但不必回到起始顶点的迹。这样的图称为半欧拉图。
The distinction is crucial: in an Eulerian circuit, the start and end vertices are identical; in an Eulerian trail, they can be different. The terms 'Eulerian graph' and 'semi-Eulerian graph' correspond to these two cases and have different degree conditions.
这个区别很关键：在欧拉回路中，起始和结束顶点相同；在欧拉路径中，它们可以不同。术语“欧拉图”和“半欧拉图”分别对应这两种情况，并且具有不同的度数条件。
4. Euler's Theorem: The Degree Condition | 欧拉定理：度数条件
Euler's theorem states: A connected graph is Eulerian if and only if every vertex has even degree. This powerful result provides a simple check. If all vertex degrees are even, an Eulerian circuit exists; conversely, if an Eulerian circuit exists, all degrees must be even.
欧拉定理指出：一个连通图是欧拉图当且仅当每个顶点的度数均为偶数。这个强大的结论提供了一种简单的检验方法。如果所有顶点度数为偶数，则存在欧拉回路；反之，如果存在欧拉回路，所有度数必为偶数。
Proof sketch: When traversing an Eulerian circuit, each time you enter a vertex you must leave it via a different edge, so the edges incident to any vertex can be paired up in 'enter-leave' pairs, implying its degree is even. The converse can be shown by construction or induction on the number of edges.
证明梗概：当遍历欧拉回路时，每次进入一个顶点都必须通过不同的边离开，因此与任何顶点关联的边可以按“进入-离开”成对出现，意味着度数为偶数。反之可以通过构造法或对边数归纳来证明。
5. Semi-Eulerian Graphs | 半欧拉图
A connected graph is semi-Eulerian if and only if it has exactly two vertices of odd degree. In that case, any Eulerian trail must start at one of the odd-degree vertices and end at the other. No Eulerian circuit exists because a circuit requires all even degrees.
一个连通图是半欧拉图当且仅当它恰好有两个奇数度顶点。在这种情况下，任何欧拉路径必须以其中一个奇度顶点为起点，另一个奇度顶点为终点。不存在欧拉回路，因为回路要求所有度数为偶数。
If a graph has more than two odd-degree vertices, it is neither Eulerian nor semi-Eulerian; it is impossible to traverse all edges exactly once in a single trail. For instance, any graph with four odd vertices can only be covered by at least two trails.
如果一个图中奇数度顶点超过两个，那么它既不是欧拉图也不是半欧拉图；不可能在一次迹中恰好遍历所有边。例如，任何拥有四个奇度顶点的图至少需要两条迹才能覆盖所有边。
6. Identifying Eulerian and Semi-Eulerian Graphs | 识别欧拉图与半欧拉图
To determine the Eulerian type of a graph, follow these steps: 1) Check if the graph is connected (ignore isolated vertices). 2) List the degree of each vertex. 3) Count the number of odd-degree vertices. If zero, it is Eulerian; if exactly two, it is semi-Eulerian; otherwise, it is non-Eulerian.
判断图的欧拉类型，按以下步骤操作：1) 检查图是否连通（忽略孤立顶点）。2) 列出每个顶点的度数。3) 统计奇度顶点的数目。若为零，则是欧拉图；若恰好为两个，则是半欧拉图；否则是非欧拉图。
Eulerian trail could start at B and end at C. If degrees were A=2, B=2, C=2, D=2, it would be Eulerian.
举例：考虑一个顶点为A、B、C、D的图。度数：A=2，B=3，C=3，D=2。有两个奇度顶点（B和C），所以该图是半欧拉图。欧拉路径可以从B开始，到C结束。如果度数均为A=2, B=2, C=2, D=2，那么该图是欧拉图。
7. Constructing Eulerian Circuits and Trails | 构造欧拉回路与路径
Once you know an Eulerian circuit or trail exists, how do you find one? A practical method is to start at an appropriate vertex (any vertex for Eulerian, an odd-degree vertex for semi-Eulerian) and proceed along unused edges, never traversing the same edge twice. If you get stuck before covering all edges, backtrack and choose an alternative edge.
一旦知道存在欧拉回路或路径，如何找到一条？一个实用的方法是：从一个合适的顶点出发（对于欧拉图可以是任意顶点，对于半欧拉图必须是一个奇度顶点），沿着未使用过的边前进，绝不重复经过同一条边。如果在覆盖所有边之前卡住，就回溯并选择另一条边。
Fleury's algorithm provides a systematic approach: at each step, choose an edge that is not a bridge in the remaining graph unless it is the only option. This avoids disconnecting the untraversed part. However, at A-Level, simple trial-and-error with backtracking is often sufficient and easier to perform by hand.
弗勒里算法提供了一种系统性方法：每一步选择一条在剩余图中不是桥的边，除非这是唯一选项。这可以避免割断尚未遍历的部分。不过在A-Level阶段，简单的试错加回溯通常就足够了，也更易于手动执行。
8. Applications of Eulerian Graphs | 欧拉图的应用
Eulerian graphs model many real-world routing problems. The Chinese Postman Problem seeks the shortest closed walk covering every street in a network; if the graph is Eulerian, the optimal route is an Eulerian circuit. Other applications include inspecting power lines, snow ploughing, street sweeping, and laying cables without retracing steps.
欧拉图可以模拟许多现实世界中的路径选择问题。中国邮递员问题寻求覆盖网络中每条街道的最短闭行走；如果图是欧拉图，最优路径就是欧拉回路。其他应用包括检查电线、铲雪、扫街和铺设电缆，避免重复步骤。
In DNA sequencing, Eulerian paths through de Bruijn graphs help reconstruct sequences from fragments. The concept also appears in circuit board testing where probes must cover all connections without repetition, and in museum layout planning for one-way visitor routes that cover every corridor exactly once.
在DNA测序中，通过德布鲁因图的欧拉路径有助于从片段重构序列。这一概念也出现在电路板测试中，此时探针必须覆盖所有连接而不重复，以及博物馆布局规划中让游客单向路线恰好覆盖每条走廊一次。
9. Worked Examples | 例题解析
=2. There are exactly two odd-degree vertices (P and R), so the graph is semi-Eulerian. One Eulerian trail is P-R-Q-P-S-R, which uses all five edges exactly once and starts at P, ends at R.
例1：判断一个顶点为P, Q, R, S且边为PQ, QR, RS, SP, PR的图的欧拉类型。度数：P=3，Q=2，R=3，S=2。恰好有两个奇度顶点（P和R），所以该图是半欧拉图。一条欧拉路径是P-R-Q-P-S-R，恰好使用所有五条边一次，从P开始，到R结束。
Example 2: The complete graph K₄ has four vertices each of degree 3 (odd). It has four odd-degree vertices, so it is neither Eulerian nor semi-Eulerian. No single trail covers all edges exactly once. However, the complete graph K₅ has five vertices each of degree 4 (even), so it is Eulerian; you can find an Eulerian circuit easily.
例2：完全图K₄有四个顶点，每个度数为3（奇数）。它有四个奇度顶点，所以既非欧拉图也非半欧拉图，没有单一的迹能恰好覆盖所有边。然而，完全图K₅有五个顶点每个度数为4（偶数），所以它是欧拉图；你可以轻易找到一条欧拉回路。
10. Common Pitfalls and Summary | 常见错误与总结
Pitfall 1: Forgetting to check connectivity. A graph with all even degrees but disconnected (e.g. two separate Eulerian components) is not Eulerian because no single trail can cover components without jumping. Always verify the graph is connected before applying degree conditions.
常见错误1：忘记检查连通性。一个所有度数均为偶数的图如果是不连通的（例如两个分离的欧拉分量），并不是欧拉图，因为无法在不跨越的情况下用一条迹覆盖多个分量。在应用度数条件前务必验证连通性。
Pitfall 2: Miscounting degrees, especially when graphs are given as diagrams. Remember that a loop contributes 2 to the degree of its vertex, and each edge connecting distinct vertices adds 1 to each. Double-check your count; a single mistake can misclassify the graph.
常见错误2：度数计算错误，尤其是给定图示时。记住环为对应的顶点贡献2度，连接不同顶点的每条边各为每个顶点贡献1度。仔细复核你的计数；一个错误就可能导致图的错误分类。
Summary: Eulerian graphs require all even-degree vertices in a connected graph; semi-Eulerian allows exactly two odd vertices. These concepts underpin efficient route planning and are tested frequently in Edexcel Decision Mathematics. Mastering degree checking and trail construction will boost your confidence in graph theory exam questions.
总结：欧拉图要求连通图中所有顶点度数为偶数；半欧拉图允许恰好两个奇度顶点。这些概念是高效路径规划的基础，在爱德思决策数学考试中经常出现。掌握度数检查和路径构造将增强你在图论考题中的信心。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图