Paths and Circuits in Graphs | 图中的路径与回路

📚 Paths and Circuits in Graphs | 图中的路径与回路

Graph theory is a fundamental branch of discrete mathematics that models pairwise relationships between objects. In this article, we explore paths, trails, circuits, and cycles—the building blocks of graph analysis—and examine their significance in the IB Mathematics curriculum.

图论是离散数学的一个重要分支，用于建模对象之间的成对关系。本文将深入探讨路径、迹、回路与循环——图分析的基石，并阐明它们在IB数学课程中的重要意义。

1. Core Definitions: Vertices and Edges | 核心定义：顶点与边

A graph G = (V, E) consists of a set of vertices (also called nodes) V and a set of edges E. Each edge connects a pair of vertices, representing a relationship between them. In an undirected graph, edges have no direction; in a directed graph, each edge has a specific orientation.

图 G = (V, E) 由顶点集 V 和边集 E 构成。每条边连接一对顶点，表示它们之间的关系。在无向图中，边没有方向；在有向图中，每条边具有特定的方向。

The degree of a vertex, denoted deg(v), is the number of edges incident to the vertex. A vertex with degree 0 is isolated. The handshake lemma states that the sum of all vertex degrees equals twice the number of edges:

顶点 v 的度数记为 deg(v)，是与该顶点关联的边的数目。度数为 0 的顶点称为孤立点。握手引理指出：所有顶点度数之和等于边数的两倍：

Σ deg(v) = 2|E|

This simple identity is surprisingly powerful: it implies that the number of odd-degree vertices in any graph is always even.

这一简洁恒等式威力巨大：它蕴含了任意图中奇度顶点的个数必为偶数这一结论。

2. Walks: The Most General Movement | 行走：最一般的移动方式

A walk in a graph is a sequence of vertices and edges, where each edge connects consecutive vertices. In a walk, vertices and edges may be repeated without restriction. A walk of length n contains n edges.

图中的行走是顶点与边的交替序列，其中每条边连接相邻的两个顶点。行走对顶点和边的重复没有任何限制。长度为 n 的行走包含 n 条边。

For example, in a graph with vertices A–B–C–D, the sequence A→B→C→B→D is a valid walk because edge BC is traversed twice. Walks represent the least constrained form of movement through a graph and serve as the foundation for more specific structures.

例如，在顶点序列为 A–B–C–D 的图中，序列 A→B→C→B→D 是一个合法的行走，因为边 BC 被经过了两次。行走是图中最不受约束的移动形式，是更特定结构的基础。

Walk 行走: vertices and edges may repeat | 顶点和边均可重复
Length 长度: number of edges traversed | 经过的边数
Open/Closed 开/闭: closed if start and end vertices coincide | 起点与终点相同则为闭行走

3. Trails: No Repeated Edges | 迹：边不重复

A trail is a walk in which no edge is repeated. Vertices, however, may be revisited. This distinction is crucial: a trail allows vertex repetition but forbids edge repetition.

迹是边不重复的行走。顶点可以被重复访问，但边不能重复经过。这一区分至关重要：迹允许顶点重复，但禁止边重复。

Consider a graph shaped as two triangles sharing a vertex. You can traverse one triangle, return to the shared vertex, and then traverse the second triangle. This is a trail—no edge is reused—but the shared vertex appears twice in the sequence.

考虑一个由两个共享顶点的三角形组成的图。你可以绕第一个三角形一圈，回到共享顶点，再绕第二个三角形一圈。这是一个迹——没有边被重复使用——但共享顶点在序列中出现两次。

The concept of a trail becomes especially important when discussing Euler circuits, as we shall see later.

迹的概念在后续讨论欧拉回路时尤为重要。

4. Paths: No Repeated Vertices | 路径：顶点不重复

A path is a trail in which no vertex is repeated. Since no vertex is repeated, no edge can be repeated either. Thus, every path is a trail, but not every trail is a path.

路径是顶点不重复的迹。由于顶点不重复，边自然也不会重复。因此，每条路径都是迹，但并非每条迹都是路径。

The length of a path is the number of edges it contains. A path with n vertices has length n − 1. For example, the sequence A→B→C→D in a simple graph is a path of length 3. If we add the edge DA, then A→B→C→D→A forms a cycle—a closed path where the only repeated vertex is the starting/ending vertex.

路径的长度是其包含的边数。含 n 个顶点的路径长度为 n − 1。例如，在简单图中 A→B→C→D 是长度为 3 的路径。若添加边 DA，则 A→B→C→D→A 构成一个循环——一种闭合路径，唯一的重复顶点是起点（也是终点）。

Paths are fundamental in shortest-path problems, such as finding the quickest route in a transportation network, where repetition of any location is clearly undesirable.

路径在最短路径问题中至关重要，例如在交通网络中寻找最快路线时，任何地点的重复显然是不可取的。

5. Circuits and Cycles: Closed Structures | 回路与循环：闭合结构

A circuit is a closed trail—a trail that starts and ends at the same vertex, with no repeated edges. A cycle is a closed path—a circuit with no repeated vertices except the start/end vertex.

回路是闭合的迹——起点和终点相同且边不重复的迹。循环是闭合的路径——除了起点（终点）外没有重复顶点的回路。

Structure 结构	Edges repeated? 边重复?	Vertices repeated? 顶点重复?	Closed? 闭合?
Walk 行走	Allowed 允许	Allowed 允许	Optional 可选
Trail 迹	Not allowed 不允许	Allowed 允许	Optional 可选
Path 路径	Not allowed 不允许	Not allowed 不允许	Optional 可选
Circuit 回路	Not allowed 不允许	Allowed 允许	Required 必需
Cycle 循环	Not allowed 不允许	Only start/end 仅起点/终点	Required 必需

A triangle ABC with edges AB, BC, CA forms a cycle of length 3. If you traverse the same triangle but go A→B→C→B→A, this is a circuit (closed trail) but not a cycle, because vertex B is repeated.

由边 AB、BC、CA 构成的三角形 ABC 是一个长度为 3 的循环。若按 A→B→C→B→A 行进，这是回路（闭迹）但非循环，因为顶点 B 被重复了。

6. Connected Graphs | 连通图

A graph is connected if there is a path between every pair of vertices. If any vertex is unreachable from another, the graph is disconnected, and its maximal connected subgraphs are called connected components.

如果任意两个顶点之间都存在路径，则称该图是连通的。若存在不可达的顶点对，则图为不连通的，其最大的连通子图称为连通分量。

Connectivity is a prerequisite for many theorems in graph theory. For instance, Euler’s theorem (discussed below) applies only to connected graphs. In a disconnected graph, one could not possibly traverse all edges in a single journey.

连通性是图论中许多定理的前提条件。例如，欧拉定理（下文讨论）仅适用于连通图。在不连通图中，不可能在单次行程中经过所有边。

Examining connectivity involves checking: Does every vertex have degree at least 1 in a graph with more than one vertex? Not necessarily—consider a graph with three vertices where only A–B is connected; vertex C is isolated, so the graph is disconnected.

检验连通性时需注意：在多于一个顶点的图中，是否每个顶点的度数至少为 1？不一定——考虑三个顶点的图只有 A–B 相连；顶点 C 为孤立点，因此图不连通。

7. Euler Trails and Euler Circuits | 欧拉迹与欧拉回路

An Euler trail is a trail that traverses every edge of a graph exactly once. An Euler circuit is a closed Euler trail—a circuit that visits every edge exactly once and returns to the starting vertex. Note that vertices may be visited multiple times in an Euler trail or circuit.

欧拉迹是经过图中每条边恰好一次的迹。欧拉回路是闭合的欧拉迹——每条边恰好经过一次并回到起点的回路。注意，欧拉迹或欧拉回路中的顶点可以被多次访问。

The famous Königsberg Bridge Problem motivated Euler’s investigation. The city had seven bridges connecting four land masses, and the question asked whether one could walk through the city crossing each bridge exactly once. Euler proved this impossible—giving birth to graph theory.

著名的柯尼斯堡七桥问题促成了欧拉的研究。该城有七座桥连接四块陆地，问题是一个人能否不重复地走遍每座桥。欧拉证明这是不可能的——由此诞生了图论。

To model this problem: represent each land mass as a vertex and each bridge as an edge. The resulting graph has four vertices with degrees 3, 3, 3, and 5—all odd. Euler demonstrated that the existence of an Euler trail depends on vertex degrees.

建模方法：将每块陆地视为顶点，每座桥视为边。所得图有四个顶点，度数分别为 3、3、3、5——均为奇数。欧拉证明了欧拉迹的存在性取决于顶点度数。

8. Euler’s Theorem: The Decisive Criterion | 欧拉定理：决定性判据

Euler’s theorem provides precise conditions for the existence of Euler trails and circuits:

欧拉定理给出了欧拉迹与欧拉回路存在的精确条件：

Euler’s Theorem 欧拉定理:

A connected graph has an Euler circuit if and only if every vertex has even degree. 连通图存在欧拉回路当且仅当每个顶点的度数均为偶数。
A connected graph has an Euler trail (but not a circuit) if and only if exactly two vertices have odd degree. 连通图存在欧拉迹（而非回路）当且仅当恰好有两个顶点的度数为奇数。

In the case of exactly two odd-degree vertices, the Euler trail must begin at one odd-degree vertex and end at the other. Let us verify this with a rectangle ABCD plus diagonal AC. Vertex degrees: A = 3, B = 2, C = 3, D = 2. Exactly two odd vertices (A and C), so an Euler trail exists, starting at A and ending at C (or vice versa). One such trail: A→B→C→A→D→C.

在恰有两个奇度顶点的情况下，欧拉迹必须始于其中一个奇度顶点，终于另一个。用矩形 ABCD 加对角线 AC 验证：顶点度数 A = 3、B = 2、C = 3、D = 2，恰好两个奇度顶点 A 和 C，故欧拉迹存在，从 A 出发以 C 结束（或反之）。一条可行迹：A→B→C→A→D→C。

Why does this work? Each time a trail enters and leaves a vertex, it consumes two incident edges. Thus, all vertices must have even degree for the trail to return to its origin, except for the two endpoints of an open trail where one edge is “unmatched.”

为什么成立？每次经过一个顶点进入再离开，消耗两条关联边。因此，要使迹回到起点，所有顶点度数必须是偶数；而对于开迹的两个端点，各有一条边无法”配对”。

9. Hamiltonian Paths and Cycles | 哈密顿路径与循环

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle is a closed Hamiltonian path—it visits every vertex exactly once except the starting vertex, returning to it at the end.

哈密顿路径访问每个顶点恰好一次。哈密顿循环是闭合的哈密顿路径——除起点（终点）外每个顶点恰好访问一次，最后回到起点。

It is essential to contrast Euler and Hamiltonian structures. Euler concerns edges; Hamiltonian concerns vertices. An Euler circuit uses every edge once; a Hamiltonian cycle visits every vertex once. These are entirely different constraints.

必须区分欧拉结构与哈密顿结构。欧拉关注边；哈密顿关注顶点。欧拉回路每条边经过一次；哈密顿循环每个顶点访问一次。这是完全不同的约束条件。

While Euler’s theorem gives a simple degree-based criterion, finding a Hamiltonian cycle is far more complex. In fact, determining whether a general graph has a Hamiltonian cycle is an NP-complete problem—no efficient algorithm is known. The traveling salesman problem (TSP), which seeks the shortest Hamiltonian cycle in a weighted graph, is one of the most famous open challenges in computer science.

欧拉定理给出了基于度数的简洁判据，而寻找哈密顿循环则复杂得多。事实上，判断一般图是否存在哈密顿循环是 NP 完全问题——目前已知没有高效算法。旅行商问题（TSP）即在加权图中寻找最短哈密顿循环，是计算机科学中最著名的开放性挑战之一。

10. Sufficient Conditions for Hamiltonicity | 哈密顿性的充分条件

Although no simple necessary and sufficient condition exists, several sufficient conditions are known. Dirac’s theorem states: If a graph has n ≥ 3 vertices and every vertex has degree at least n/2, then the graph contains a Hamiltonian cycle.

尽管不存在简单的充要条件，但已有若干充分条件。狄拉克定理指出：若图有 n ≥ 3 个顶点且每个顶点的度数至少为 n/2，则该图包含哈密顿循环。

Ore’s theorem generalizes Dirac’s result: If for every pair of non-adjacent vertices u and v, deg(u) + deg(v) ≥ n, then the graph has a Hamiltonian cycle.

奥勒定理推广了狄拉克的结论：若对每一对不相邻的顶点 u 和 v，都有 deg(u) + deg(v) ≥ n，则该图存在哈密顿循环。

These theorems are useful in IB exam problems where the degree sequence is given and you are asked to justify the existence of a Hamiltonian cycle without listing it explicitly.

在 IB 考试中，给定度数列并要求论证哈密顿循环存在时，这些定理非常实用，无需显式列出循环。

Consider the following comparative example. A complete graph K₅ has 5 vertices, each of degree 4, which is ≥ 5/2 = 2.5. By Dirac’s theorem, K₅ contains a Hamiltonian cycle—indeed, it contains many. In contrast, a star graph with center connected to 4 leaves has n = 5 vertices but the leaves each have degree 1 < 2.5; Dirac's condition fails, and indeed no Hamiltonian cycle exists because the center cannot be revisited.

对比以下示例：完全图 K₅ 有 5 个顶点，每个度数为 4，满足 4 ≥ 5/2 = 2.5。由狄拉克定理，K₅ 含有哈密顿循环——事实上它含有很多个。对比星形图（中心连接 4 个叶子），n = 5 但每个叶子度数为 1 < 2.5；狄拉克条件不满足，且确实不存在哈密顿循环，因为中心无法被重复访问。

11. Applications in Real-World Contexts | 现实世界中的应用

Euler circuits model route design problems: snow plowing, mail delivery, garbage collection, and network inspection all require traversing each street (edge) at least once while minimizing deadheading. The Chinese Postman Problem, introduced by Mei-Ko Kwan, asks for the shortest closed route that traverses every edge at least once—an Euler-circuit variant on weighted graphs.

欧拉回路为路线设计问题建模：扫雪、邮件投递、垃圾收集和网络巡检都需要遍历每条街道（边）至少一次并最小化空驶里程。管梅谷提出的中国邮递员问题要求找到遍历每条边至少一次的最短闭合路线——这是加权图上的欧拉回路变体。

Hamiltonian structures appear in scheduling and logistics: planning a delivery route that visits each customer exactly once, arranging a tour of scenic sites, or sequencing tasks where each job must be done once. The TSP has vast economic implications in manufacturing, circuit board drilling, and DNA sequencing.

哈密顿结构应用于调度与物流：规划恰好访问每个客户一次的配送路线、安排游览景点顺序、或排序每项必须完成一次的任务。TSP 在制造业、电路板钻孔和 DNA 测序中具有巨大的经济意义。

In network theory, finding paths between two vertices underlies routing protocols on the Internet. The concepts of trails and paths are also foundational to understanding tree structures, spanning trees, and shortest-path algorithms such as Dijkstra’s algorithm.

在网络理论中，寻找两顶点间的路径是互联网路由协议的基础。迹与路径的概念也是理解树结构、生成树以及 Dijkstra 等最短路径算法的基石。

12. Exam Strategies for IB Mathematics | IB 数学考试策略

In IB Mathematics Analysis & Approaches and Applications & Interpretation, graph theory questions often appear in Paper 2 or as part of the internal assessment. Key strategies include:

在 IB 数学分析与方法（AA）以及应用与解释（AI）中，图论题目常出现在试卷二或作为内部评估的一部分。关键策略包括：

Identify the type of problem 识别问题类型: Determine whether the question asks for an Euler trail, Euler circuit, Hamiltonian path, or Hamiltonian cycle before applying any theorem. 先判定题目要求的是欧拉迹、欧拉回路、哈密顿路径还是哈密顿循环，再应用相关定理。
Count degrees carefully 仔细计算度数: Sum of degrees must equal 2E. Use this to verify your counting. 度数之和必须等于 2E，可用此式验证计算正确性。
Use the handshake lemma 运用握手引理: The number of odd-degree vertices is always even. 奇度顶点个数永远为偶数。
For Euler problems, apply the theorem directly 欧拉问题直接套定理: List vertex degrees, identify odd-degree vertices, then conclude existence or non-existence. 列出各顶点度数，识别奇度顶点，然后判断是否存在。
For Hamiltonian problems, use Dirac or Ore conditions 哈密顿问题使用狄拉克或奥勒条件: These are sufficient but not necessary; failing them does not rule out a Hamiltonian cycle. 这些是充分但不必要条件；条件不满足并不排除哈密顿循环存在。
Practice tracing trails 练习追踪迹: When asked to find an Euler trail, start at an odd-degree vertex and avoid getting “stuck.” A helpful tip: save the edge that returns to your start point for last. 当要求找出欧拉迹时，从奇度顶点出发，避免”卡住”。实用技巧：把返回起点的边留到最后走。

Consider a typical exam question: “The following graph has vertices with degrees 2, 4, 4, 2, and 2. Does it have an Euler circuit?” Since all degrees are even and the graph is connected, an Euler circuit exists. A common mistake is to assume the graph is connected without verifying it—always check connectivity first.

典型考题示例：”下图顶点度数分别为 2、4、4、2、2。它是否存在欧拉回路？”由于所有度数均为偶数且图连通，欧拉回路存在。常见错误是未验证连通性就贸然下结论——务必先检查连通性。

13. Conclusion | 结语

The hierarchy walk → trail → path, and their closed counterparts circuit → cycle, forms a precise taxonomy of movement through a graph. Euler’s theorems provide elegant degree-based criteria for edge-traversal problems, while Hamiltonian problems remain a rich field of ongoing research. Mastery of these distinctions is essential for IB mathematics success and provides a foundation for computer science, operations research, and network engineering.

行走 → 迹 → 路径这一层级结构，与闭合对应物回路 → 循环一起，构成了图中移动方式的精确分类体系。欧拉定理为边遍历问题提供了优雅的度数判据，而哈密顿问题仍是活跃的研究领域。掌握这些概念的区别对 IB 数学取得好成绩至关重要，也为计算机科学、运筹学和网络工程奠定基础。

For further practice, try constructing graphs with 4 vertices having degrees 1, 2, 2, 1—is an Euler trail possible? What about a graph with degrees 2, 2, 2, 2, 2? As you solve these, you will internalize the theorems and gain fluency in graph-theoretic reasoning.

进一步练习：尝试构造 4 个顶点度数分别为 1、2、2、1 的图——欧拉迹是否可能？再尝试度数为 2、2、2、2、2 的图呢？在解题过程中，你将内化这些定理，并熟练运用图论推理。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Paths and Circuits in Graphs | 图中的路径与回路