📚 Eulerian Graphs | 欧拉图
In Edexcel Decision Mathematics, Eulerian graphs provide a powerful way to model routes that cover every edge of a network exactly once. This article explains the definitions, degree conditions, algorithms and exam-style applications you need.
在 Edexcel 决策数学中，欧拉图提供了一种强大的建模方法，用来描述恰好经过网络中每条边一次的路由。本文讲解定义、顶点度条件、算法以及考试风格的应用。
1. Graphs and trails | 图与路径
A graph G = (V, E) consists of vertices (nodes) and edges (arcs) joining pairs of vertices. A trail is a sequence of edges in which no edge is repeated; a circuit is a closed trail.
图 G = (V, E) 由顶点（节点）和连接顶点对的边（弧）组成。路径（trail）是指没有重复边的边序列；回路（circuit）是闭合的路径。
In A-Level questions, graphs may be simple, multiple or directed. For Eulerian graphs, the usual focus is on undirected connected graphs, but directed versions appear in Further Mathematics.
在 A-Level 试题中，图可以是简单图、多重图或有向图。对于欧拉图，通常关注无向连通图，但在进阶数学中也会出现有向版本。
2. Eulerian graph definition | 欧拉图的定义
A connected graph is Eulerian if it contains an Eulerian circuit: a closed trail that uses every edge exactly once. A graph with an Eulerian circuit is called an Eulerian graph.
如果连通图包含欧拉回路，则该图是欧拉图：欧拉回路是恰好使用每条边一次的闭合路径。含有欧拉回路的图称为欧拉图。
Equivalently, a graph is Eulerian if you can start at a vertex, travel along every edge exactly once, and return to the starting vertex without lifting your pen.
等价地说，如果可以从某个顶点出发，沿每条边恰好走一次，并回到起点，且不抬笔，那么该图就是欧拉图。
3. Eulerian trails and circuits | 欧拉路径与回路
An Eulerian trail uses every edge exactly once but does not need to end where it started. An Eulerian circuit is a closed Eulerian trail. Every Eulerian circuit is an Eulerian trail, but not conversely.
欧拉路径恰好使用每条边一次，但不要求终点与起点重合。欧拉回路是闭合的欧拉路径。每个欧拉回路都是欧拉路径，但反过来不一定成立。
For example, the graph with vertices A, B, C and edges AB, BC, CA, AD, DC has an Eulerian trail from B to D but no Eulerian circuit.
例如，顶点为 A、B、C，边为 AB、BC、CA、AD、DC 的图具有从 B 到 D 的欧拉路径，但没有欧拉回路。
4. Semi-Eulerian graphs | 半欧拉图
A connected graph is semi-Eulerian if it contains an Eulerian trail but no Eulerian circuit. This means you can cover every edge exactly once, but the start and end vertices must be different.
如果连通图包含欧拉路径但没有欧拉回路，则该图是半欧拉图。这意味着你可以恰好覆盖每条边一次，但起点和终点必须是不同的顶点。
The term “semi-Eulerian” is used in Edexcel D1. Make sure you do not call such a graph Eulerian unless a closed trail covering all edges exists.
“半欧拉图” 这一术语用于 Edexcel D1。请确保不要将这类图称为欧拉图，除非存在覆盖所有边的闭合路径。
5. Degree conditions | 顶点度条件
For a connected graph, Euler’s theorem gives a simple test. A connected graph is Eulerian if and only if every vertex has even degree.
对于连通图，欧拉定理给出一个简单判定。连通图是欧拉图当且仅当每个顶点的度数都是偶数。
A connected graph is semi-Eulerian if and only if exactly two vertices have odd degree. In that case, the Eulerian trail must start at one odd-degree vertex and end at the other.
连通图是半欧拉图当且仅当恰好有两个顶点的度数为奇数。此时，欧拉路径必须从一个奇度顶点开始，并在另一个奇度顶点结束。
If a graph has more than two odd-degree vertices, it is neither Eulerian nor semi-Eulerian. You would need to repeat some edges to cover the network.
如果图中超过两个奇度顶点，则它既不是欧拉图也不是半欧拉图。你需要重复某些边才能遍历整个网络。
| Degrees (connected graph) | 中文：度数（连通图） | Classification | 中文：分类 |
|---|---|---|---|
| All even | 全部为偶数 | Eulerian | 欧拉图 |
| Exactly two odd | 恰好两个奇数 | Semi-Eulerian | 半欧拉图 |
| More than two odd | 超过两个奇数 | Neither | 都不是 |
6. Connectedness and isolated vertices | 连通性与孤立顶点
The degree condition only works for connected graphs. A disconnected graph with all even degrees is not Eulerian because you cannot travel between components.
度条件只适用于连通图。一个所有顶点度数均为偶数但不连通的图不是欧拉图，因为你无法在不同连通分量之间通行。
Isolated vertices with degree 0 are even-degree vertices. If the rest of the graph is connected, isolated vertices may be ignored when checking Eulerian properties.
度数为 0 的孤立顶点属于偶度顶点。如果图的其余部分是连通的，在判断欧拉性质时可以忽略孤立顶点。
7. Fleury’s algorithm | Fleury 算法
Fleury’s algorithm constructs an Eulerian circuit or trail by never crossing a bridge unless there is no alternative. A bridge is an edge whose removal increases the number of connected components.
Fleury 算法通过除非别无选择，否则绝不经过桥的方式来构造欧拉回路或欧拉路径。桥是指删除后会增加连通分量数量的边。
Start at an appropriate vertex: any vertex for an Eulerian circuit, or one of the two odd-degree vertices for a semi-Eulerian trail. At each step, choose a non-bridge edge if possible.
从合适的顶点出发：对于欧拉回路可以从任意顶点出发；对于半欧拉路径则从一个奇度顶点出发。每一步尽可能选择非桥边。
This algorithm is often tested with small networks where you must explain why a particular edge cannot be used until later.
该算法常在小网络上考查，要求解释为什么某条边必须留到后面才能使用。
8. Hierholzer’s algorithm | Hierholzer 算法
Hierholzer’s algorithm builds an Eulerian circuit by merging edge-disjoint cycles. Start from any vertex, follow unused edges until returning to the start, forming a cycle.
Hierholzer 算法通过合并边不交的回路来构造欧拉回路。从任意顶点出发，沿着未使用的边走，直到返回起点，形成一个回路。
If unused edges remain, find a vertex on the current circuit with unused incident edges, then start a new cycle from that vertex and splice it into the original circuit.
如果仍有未使用的边，则在当前回路上找一个仍有未使用关联边的顶点，从该顶点开始新回路，并将其拼接到原回路中。
This algorithm is efficient for computer implementations, but exam questions usually ask for one valid Eulerian circuit rather than a specific algorithm.
该算法在计算机实现中很高效，但考试题目通常只要求给出一个有效的欧拉回路，而不要求指定算法。
9. Route inspection problem | 路线检查问题
The route inspection problem, sometimes called the Chinese postman problem, asks for the shortest route that covers every edge at least once and returns to the start.
路线检查问题，有时称为中国邮递员问题，要求找到至少覆盖每条边一次并返回起点的最短路线。
If the graph is Eulerian, the optimum route is simply an Eulerian circuit, and its length equals the sum of all edge weights.
如果图是欧拉图，最优路线就是欧拉回路，其长度等于所有边的权重之和。
If the graph is not Eulerian, you must add repeated edges between odd-degree vertices to make all degrees even. The aim is to minimise the total weight of the repeated edges.
如果图不是欧拉图，则必须在奇度顶点之间添加重复边，使所有度数变为偶数。目标是使重复边的总权重最小。
For Edexcel exams, you need to identify odd-degree vertices, consider pairings, and choose the minimum-weight pairing to determine the length
Published by TutorHao | A-Level Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply