📚 Closed Paths in Graph Theory: Cycles, Circuits, and Eulerian & Hamiltonian Paths | 图论中的封闭路径：环、回路与欧拉及哈密顿路径
In graph theory, a closed path is a fundamental concept that appears when studying networks, routes, and connectivity. A closed path is a walk that starts and ends at the same vertex, with no repeated edges, and it forms the basis for understanding cycles, circuits, and famous problems like the Seven Bridges of Königsberg. This article explores the definitions, properties, and applications of closed paths, focusing on Eulerian and Hamiltonian circuits, which are essential topics in the IB Mathematics: Applications and Interpretation HL syllabus.
在图论中，封闭路径是研究网络、路线和连通性时出现的核心概念。封闭路径是指起点和终点在同一个顶点的路径，其中边不重复，它构成了理解环、回路以及诸如柯尼斯堡七桥问题等著名问题的基础。本文探讨封闭路径的定义、性质及应用，重点关注欧拉回路和哈密顿回路，这些是IB数学：应用与解释高级课程的重要主题。
1. Basic Definitions: Walks, Trails, Paths, and Closed Paths | 基本定义：走法、迹、路径与封闭路径
A walk in a graph is a sequence of vertices and edges, where each edge connects its preceding and succeeding vertices. A trail is a walk with no repeated edges. A path is a trail with no repeated vertices. A closed walk (or closed trail) is a walk that starts and ends at the same vertex. When a closed trail has no repeated vertices except for the start/end vertex, it is called a cycle. If the closed trail allows repeated vertices but not repeated edges, it is simply a circuit.
图中的走法是由顶点和边组成的序列，其中每条边连接其前后顶点。迹是没有重复边的走法。路径是没有重复顶点的迹。封闭走法（或封闭迹）是起点和终点相同的走法。当封闭迹除起点/终点外无重复顶点时，称为环。如果封闭迹允许重复顶点但不允许重复边，则简称为回路。
2. Distinguishing Cycles, Circuits, and Closed Walks | 区分环、回路与封闭走法
It is crucial to distinguish between these terms: a cycle has no repeated vertices (except the start/end), while a circuit may revisit vertices but cannot reuse edges. A closed walk is the most general, allowing both repeated edges and vertices. For example, in a square with vertices A, B, C, D and edges AB, BC, CD, DA, the sequence A-B-C-D-A is both a cycle and a circuit. Traversing A-B-C-B-A is a closed walk but not a trail because the edge AB is repeated.
区分这些术语至关重要：环无重复顶点（起点/终点除外），而回路可以重新访问顶点但不能重复使用边。封闭走法最为广义，允许重复边和顶点。例如，在一个正方形中，顶点为A、B、C、D，边为AB、BC、CD、DA，序列A-B-C-D-A既是一个环也是一个回路。而遍历A-B-C-B-A是一个封闭走法，但不是迹，因为边AB被重复使用了。
3. Eulerian Trails and Circuits: Historical Origin | 欧拉迹与欧拉回路：历史起源
Leonhard Euler solved the Seven Bridges of Königsberg problem in 1736, laying the foundation of graph theory. The problem asked whether one could walk through the city crossing each of its seven bridges exactly once and return to the starting point. Euler proved it was impossible by modelling the landmasses as vertices and bridges as edges, and introducing the concept of vertex degree. An Eulerian circuit is a closed trail that uses every edge of a graph exactly once.
莱昂哈德·欧拉于1736年解决了柯尼斯堡七桥问题，奠定了图论的基础。该问题询问能否在城中步行，恰好每座桥只走一次并回到起点。欧拉通过将陆地建模为顶点、桥梁建模为边，并引入顶点度的概念，证明了这是不可能的。欧拉回路是恰好使用图中每条边各一次的封闭迹。
4. Conditions for Eulerian Circuits | 欧拉回路存在的条件
A connected graph has an Eulerian circuit if and only if every vertex has an even degree. This is because each time the path enters a vertex via one edge, it must leave via a different edge, consuming two edges per visit. If all degrees are even, one can find a closed trail covering all edges. If exactly two vertices have odd degree, an Eulerian trail exists but it is not closed. In IB Mathematics, students learn to apply this theorem to determine whether a network is Eulerian.
一个连通图具有欧拉回路当且仅当每个顶点的度均为偶数。这是因为路径每次通过一条边进入一个顶点时，必须通过另一条边离开，每次访问消耗两条边。若所有度均为偶数，便可找到覆盖所有边的封闭迹。如果恰好有两个顶点的度数为奇数，则存在欧拉迹，但不是封闭的。在IB数学中，学生学会应用这一定理来判断一个网络是否为欧拉图。
5. Finding Eulerian Circuits: Fleury's Algorithm and Hierholzer's Algorithm | 寻找欧拉回路：Fleury算法与Hierholzer算法
Fleury's algorithm provides a step-by-step method for constructing an Eulerian circuit. Starting at any vertex, one traverses edges, always choosing a non-bridge edge if possible, until all edges are used. Hierholzer's algorithm is more efficient: it finds a closed trail, then integrates other cycles until the complete circuit is formed. In IB exams, students may be asked to trace an Eulerian circuit manually on small graphs.
Fleury算法提供了逐步构造欧拉回路的方法：从任意顶点开始遍历边，尽可能选择非桥的边，直到所有边都被使用。Hierholzer算法更高效：先找到一个封闭迹，再整合其他环，直到形成完整的回路。在IB考试中，学生可能被要求在小图上手动追踪一条欧拉回路。
6. Hamiltonian Paths and Cycles: A Different Challenge | 哈密顿路径与环：另一种挑战
A Hamiltonian path visits every vertex exactly once, and a Hamiltonian cycle is a Hamiltonian path that returns to the starting vertex, forming a closed loop. Unlike Eulerian circuits, no simple necessary and sufficient condition for Hamiltonian cycles is known. Determining whether a graph is Hamiltonian is an NP-complete problem. In IB courses, the focus is on recognizing Hamiltonian cycles in complete graphs or graphs with sufficient edges, often related to the Travelling Salesman Problem.
哈密顿路径恰好访问每个顶点一次，哈密顿环是返回起点的哈密顿路径，形成一个封闭环。与欧拉回路不同，哈密顿环没有简单的充要条件。判断一个图是否为哈密顿图是一个NP完全问题。在IB课程中，重点是在完全图或具有足够边的图中识别哈密顿环，通常与旅行商问题相关。
7. The Travelling Salesman Problem (TSP) and Closed Paths | 旅行商问题与封闭路径
The Travelling Salesman Problem asks for the shortest possible closed route that visits each vertex exactly once and returns to the start. This is precisely a minimum-weight Hamiltonian cycle. While finding the optimal solution for large graphs is computationally hard, IB students explore heuristic methods such as the nearest neighbour algorithm, the upper bound (MST-based) algorithm, and the lower bound calculation. These are all attempts to construct or approximate a best closed path.
旅行商问题要求找到访问每个顶点恰好一次并返回起点的最短封闭路线。这正是一个最小权重的哈密顿环。虽然对于大图寻找最优解在计算上很困难，但IB学生探索启发式方法，如最近邻算法、基于最小生成树的上界算法和下界计算。这些都是试图构造或近似最佳封闭路径的方法。
8. Closed Paths in Directed Graphs | 有向图中的封闭路径
In directed graphs (digraphs), the concept of closed paths extends to directed cycles and circuits. An Eulerian circuit in a digraph requires that each vertex has equal in-degree and out-degree, and the graph is strongly connected. Hamiltonian cycles in digraphs are used to model tournaments, scheduling, and network routing. IB Mathematics: Applications and Interpretation may include directed networks in the context of project management or flow problems.
在有向图中，封闭路径的概念扩展到有向环和回路。有向图中的欧拉回路要求每个顶点的入度等于出度，且图是强连通的。有向哈密顿环用于建模锦标赛、调度和网络路由。IB数学：应用与解释可能在项目管理或流问题的背景下包含有向网络。
9. Practical Applications of Closed Paths | 封闭路径的实际应用
Closed paths are used extensively in real-world scenarios: Eulerian circuits help design mail delivery routes, garbage collection, and street sweeping where every street must be covered exactly once. Hamiltonian cycles underpin logistics, DNA sequencing, and circuit board drilling. Understanding these concepts enables students to model and solve optimization problems in transportation, telecommunications, and biology.
封闭路径在现实场景中广泛应用：欧拉回路帮助设计邮政递送路线、垃圾收集和街道清扫方案，其中每条街道必须恰好经过一次。哈密顿环支撑着物流、DNA测序和电路板钻孔。理解这些概念使学生能够在交通、电信和生物学中对优化问题进行建模和求解。
10. Closed Paths in Weighted Graphs and Minimum Cost Circuits | 加权图中的封闭路径与最小成本回路
When edges have weights (distances, times, costs), finding a closed path that minimizes total weight becomes a crucial optimization problem. The Chinese Postman Problem seeks the shortest closed walk covering all edges, which reduces to finding an Eulerian circuit after adding minimum-weight edge duplications for odd-degree vertices. This is a natural extension of Eulerian concepts in weighted networks and is explored in higher-level IB investigations.
当边具有权重（距离、时间、成本）时，寻找总权重最小的封闭路径便成为一个关键的优化问题。中国邮递员问题寻找覆盖所有边的最短封闭走法，这归结为在为奇度顶点添加最小权重边复制后寻找欧拉回路。这是加权网络中欧拉概念的自然延伸，在IB高级课程探究中有所涉及。
11. Summary of Key Theorems and Comparison | 关键定理总结与对比
| Concept | Eulerian Circuit | Hamiltonian Cycle |
|---|---|---|
| Definition | Closed trail using every edge exactly once | Closed path visiting every vertex exactly once |
| Condition | All vertices have even degree | No known simple condition |
| Complexity | Polynomial time | NP-complete |
| Typical Application | Route inspection, garbage collection | TSP, scheduling |
This table highlights the fundamental differences between the two main types of closed paths studied in IB Mathematics. Recognizing these differences is essential for selecting appropriate algorithms and understanding the limitations of each model.
上表突出了IB数学中研究的两种主要封闭路径类型之间的基本区别。认识到这些差异对于选择合适的算法以及理解每种模型的局限性至关重要。
12. Practice and Further Exploration | 练习与深入探索
To master closed paths, students should practice identifying Eulerian circuits in small networks, verifying the degree condition, and tracing circuits using Fleury’s algorithm. For Hamiltonian cycles, they can experiment with complete graphs Kn, noting that the number of distinct Hamiltonian cycles in an undirected Kn is (n−1)!/2. IB exam-style questions often combine these ideas with minimum spanning trees and shortest path algorithms, encouraging a holistic understanding of graph optimization.
要掌握封闭路径，学生应练习在小网络中识别欧拉回路，验证度数条件，并使用Fleury算法追踪回路。对于哈密顿环，可以尝试完全图Kn，注意无向Kn中不同的哈密顿环数为(n−1)!/2。IB考试风格的题目常将这些思想与最小生成树和最短路径算法相结合，鼓励对图优化的全面理解。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图