4 Paths and Cycles | 路径与圈

📚 4 Paths and Cycles | 路径与圈

Graph theory provides a powerful language for describing connections and networks. Among its most fundamental concepts are paths and cycles, which underpin everything from route planning to electrical circuit analysis. In IB Mathematics, understanding the precise definitions of walks, trails, paths, and cycles — and being able to distinguish between Eulerian and Hamiltonian versions — is essential for both exam success and deeper mathematical reasoning.

图论为描述连接和网络提供了一种强大的语言。路径和圈是其中最基础的概念，支撑着从路线规划到电路分析的方方面面。在 IB 数学中，准确理解行走、迹、路径和圈的定义，并能够区分欧拉版本与汉密尔顿版本，对于考试成功和更深入的数学推理都至关重要。

1. What is a Graph? | 什么是图？

A graph G is an ordered pair (V, E) consisting of a set V of vertices (nodes) and a set E of edges, where each edge connects two vertices. In the IB syllabus, graphs are typically simple — no loops and no multiple edges between the same pair of vertices. The degree of a vertex v, denoted deg(v), is the number of edges incident to it.

图 G 是由顶点集 V 和边集 E 构成的有序对 (V, E)，每条边连接两个顶点。在 IB 大纲中，图通常指简单图——没有环，也没有重复边。顶点 v 的度数 deg(v) 是指与该顶点相连的边的数目。

All the concepts of paths and cycles can be visualised on graphs. Consider a complete graph on 5 vertices, K₅, where every pair of distinct vertices is joined by exactly one edge. This graph is rich in paths and cycles and frequently appears in IB problems.

所有关于路径和圈的概念都可以在图上直观展现。以 5 个顶点的完全图 K₅ 为例，每一对不同顶点之间恰有一条边相连。这样的图中路径和圈十分丰富，经常出现在 IB 考题中。

2. Walks, Trails, Paths, Cycles — Key Definitions | 行走、迹、路径、圈的定义

Precise terminology is critical. A walk is an alternating sequence of vertices and edges, starting and ending at vertices. A trail is a walk in which all edges are distinct. A path is a walk in which all vertices (and therefore all edges) are distinct. A circuit is a closed trail (start = end, no repeated edges). A cycle is a closed path with length at least 3, where the only repeated vertex is the start/end.

精确的术语至关重要。行走是顶点和边交替出现的序列，起点和终点都是顶点。迹是边不重复的行走。路径是顶点（因而边也）不重复的行走。回路是起点与终点重合且边不重复的封闭迹。圈是长度为 3 及以上的封闭路径，只有起点和终点相同这一个重复顶点。

In many IB mark schemes, confusion between ‘path’ and ‘trail’ or between ‘circuit’ and ‘cycle’ leads to lost marks. Always note: a cycle is a closed path, so no internal vertex repeats; a circuit is a closed trail, so edges are distinct but vertices may repeat.

在 IB 的评分标准中，“路径”和“迹”或“回路”和“圈”的混淆往往会导致丢分。请始终记住：圈是封闭路径，内部顶点不重复；回路是封闭迹，边不重复但顶点可以重复。

Walk – sequence of vertices and edges	行走 – 顶点和边的序列
Trail – no edge repeated	迹 – 边不重复
Path – no vertex repeated	路径 – 顶点不重复
Circuit (closed trail) – starts and ends at same vertex, no edge repeated	回路（闭迹） – 起点终点相同，边不重复
Cycle (closed path) – length ≥ 3, only start/end vertex repeated	圈（闭路径） – 长度 ≥3，仅起点终点重复

3. Paths in Detail | 路径详解

A path of length k is a sequence of k+1 distinct vertices v₀, v₁, …, vₖ such that consecutive vertices are adjacent. The length is the number of edges. A shortest path between two vertices minimises this length; if no path exists, the graph is disconnected.

长度为 k 的路径是由 k+1 个互不相同的顶点 v₀, v₁, …, vₖ 组成的序列，其中相邻顶点邻接。长度就是边的数目。两个顶点之间最短路径使该长度最小；若没有路径，则图是不连通的。

In a tree (a connected acyclic graph), there is exactly one unique path between any two distinct vertices. This property is often used in IB problems to prove that a tree with n vertices has exactly n − 1 edges.

在树（连通无圈图）中，任何两个不同顶点之间都有且仅有一条唯一的路径。这一性质常被 IB 考题用来证明具有 n 个顶点的树恰好有 n − 1 条边。

Path example: v₁ → v₂ → v₃ → v₄

To describe a path, we only need the vertex sequence because edges are implied. In IB exam answers, writing ‘P: A – B – C – D’ is acceptable and concise. Always verify that no vertex is repeated.

描述路径时，只需要列出顶点序列，因为边已经隐含其中。在 IB 考试中，写出“P: A – B – C – D”是可接受的简明答案。务必检查顶点没有重复。

4. Cycles in Detail | 圈详解

A cycle Cₙ is a closed path of length n (n ≥ 3). The smallest cycle is a triangle C₃. Graphs without any cycles are called acyclic; trees are connected acyclic graphs. The presence or absence of cycles dictates whether Eulerian or Hamiltonian tours are possible.

圈 Cₙ 是一个长度为 n（n ≥ 3）的封闭路径。最小的圈是三角形 C₃。没有任何圈的图称为无圈图；树就是连通的无圈图。圈的存在与否决定了欧拉或汉密尔顿环游是否可能。

The girth of a graph is the length of its shortest cycle; the circumference is the length of its longest cycle. In bipartite graphs, all cycles have even length — a classic IB proof uses the fact that an odd cycle would require an odd number of steps to return to the starting partite set, which is impossible.

图的围长是最短圈的长度，周长是最长圈的长度。在二分图中，所有圈的长度都是偶数——一个经典的 IB 证明利用这样一个事实：奇圈需要奇数步才能回到起始的部集，这不可能。

Cycle C₄: v₁ → v₂ → v₃ → v₄ → v₁

In directed graphs, cycles are defined analogously but must follow the direction of arcs. This is crucial in IB Applications and Interpretation where directed networks model flows and tournaments.

在无向图中，圈类似定义，但必须沿弧的方向前进。这在 IB“应用与解释”课程中至关重要，因为有向网络常用于建模流和竞赛。

5. Eulerian Paths and Circuits | 欧拉路径与回路

An Eulerian trail (or path) uses every edge of a connected graph exactly once. An Eulerian circuit (or cycle) is a closed Eulerian trail. These concepts originate from the famous Königsberg bridge problem.

欧拉迹（或路径）恰好经过连通图中的每条边一次。欧拉回路（或圈）是封闭的欧拉迹。这些概念源于著名的柯尼斯堡七桥问题。

A connected graph has an Eulerian circuit if and only if every vertex has even degree. It has an Eulerian trail but no Eulerian circuit if and only if exactly two vertices have odd degree; in that case, the trail starts at one odd-degree vertex and ends at the other.

一个连通图有欧拉回路当且仅当所有顶点的度数均为偶数。它有欧拉迹但没有欧拉回路当且仅当恰好有两个顶点的度数为奇数；此时，迹从其中一个奇度顶点开始，到另一个奇度顶点结束。

If a graph has more than two vertices of odd degree, it has neither an Eulerian trail nor an Eulerian circuit. IB exam questions frequently ask students to determine if a given street network can be traversed by a postman without retracing steps.

如果一个图中奇度顶点的个数超过 2，那么它既没有欧拉迹也没有欧拉回路。IB 试题经常要求学生判断一个给定的街道网络能否被邮递员不重复路线地遍历。

Fleury’s algorithm and Hierholzer’s algorithm can construct Eulerian trails, but IB exams usually require only the reasoning based on vertex degrees.

Fleury 算法和 Hierholzer 算法可以构造欧拉迹，但 IB 考试通常只需要基于顶点度数的论证。

6. Hamiltonian Paths and Cycles | 汉密尔顿路径与圈

A Hamiltonian path visits every vertex of a graph exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that returns to its starting vertex, thereby visiting all vertices without repetition except for the start/end. These are named after William Rowan Hamilton and his icosian game.

汉密尔顿路径恰好经过图中每个顶点一次。汉密尔顿圈（或汉密尔顿回路）是一条汉密尔顿路径，它回到起点，从而不重复地经过所有顶点，仅起点终点重合。它们以威廉·罗恩·汉密尔顿和他的二十面体游戏命名。

Unlike Eulerian circuits, there is no simple necessary and sufficient condition for the existence of a Hamiltonian cycle. However, two useful theorems are often cited in IB: Dirac’s theorem (if every vertex has degree ≥ n/2, a Hamiltonian cycle exists) and Ore’s theorem (if deg(u) + deg(v) ≥ n for all non-adjacent vertices u, v, a Hamiltonian cycle exists).

与欧拉回路不同，汉密尔顿圈没有简洁的充分必要条件。不过，IB 中常引用两个有用的定理：Dirac 定理（若每个顶点度数 ≥ n/2，则存在汉密尔顿圈）和 Ore 定理（若对所有不相邻的 u, v 有 deg(u) + deg(v) ≥ n，则存在汉密尔顿圈）。

A complete graph Kₙ for n ≥ 3 always contains Hamiltonian cycles, and the number of distinct Hamiltonian cycles in Kₙ is (n−1)!/2. This is a favourite IB HL problem on counting and symmetry.

完全图 Kₙ（n ≥ 3）总是包含汉密尔顿圈，且 Kₙ 中不同的汉密尔顿圈数目为 (n−1)!/2。这是 IB HL 关于计数和对称性的常见题目。

Determining whether a general graph has a Hamiltonian path is an NP-complete problem, so IB questions will typically give a structured graph or use theorems.

判断一般图是否存在汉密尔顿路径是一个 NP 完全问题，因此 IB 题目通常给出一个结构化的图或要求使用定理。

7. Comparing Eulerian and Hamiltonian Concepts | 欧拉与汉密尔顿的比较

The key difference lies in whether we traverse every edge or every vertex exactly once. Eulerian problems are concerned with edge covering, while Hamiltonian problems are about vertex covering. This distinction is fundamental and is frequently tested.

关键区别在于我们是遍历每条边还是遍历每个顶点恰好一次。欧拉问题关注边覆盖，汉密尔顿问题关注顶点覆盖。这一区别是根本的，经常在考试中出现。

Eulerian trail / circuit – uses each edge exactly once	欧拉迹/回路 – 每条边恰用一次
Vertex degrees determine existence	顶点度数决定存在性
Easy to check (even/odd degree count)	容易检验（计算奇偶度数）
Hamiltonian path / cycle – uses each vertex exactly once	汉密尔顿路径/圈 – 每个顶点恰用一次
No simple necessary and sufficient condition	无简单充要条件
Hard to check in general (NP-complete)	一般情况难以判断（NP 完全）

A graph can have an Eulerian circuit but no Hamiltonian cycle, or vice versa. For example, any tree with more than two vertices has no cycle at all, but may have an Eulerian trail if degrees allow.

一个图可以有欧拉回路而没有汉密尔顿圈，反之亦然。例如，任何多于两个顶点的树根本没有圈，但如果度数条件满足，可能有欧拉迹。

8. Worked Example | 例题讲解

Consider a simple graph G with vertices A, B, C, D, E and edges AB, BC, CD, DE, EA, AC, AD. Determine whether G has an Eulerian trail, an Eulerian circuit, a Hamiltonian path or a Hamiltonian cycle.

考虑一个简单图 G：顶点 A, B, C, D, E；边 AB, BC, CD, DE, EA, AC, AD。判断 G 是否有欧拉迹、欧拉回路、汉密尔顿路径或汉密尔顿圈。

First, list degrees: deg(A)=4 (edges AB, AC, AD, EA), deg(B)=2 (AB, BC), deg(C)=2 (BC, CD, AC? wait AC is one edge: edges BC and AC → actually C is connected to B, D, A? edges: BC, CD, AC so deg(C)=3), deg(D)=3 (CD, DE, AD), deg(E)=2 (DE, EA). Let’s check carefully: edges: AB, BC, CD, DE, EA, AC, AD. So A has AB, AC, AD, EA — 4; B: AB, BC — 2; C: BC, CD, AC — 3; D: CD, DE, AD — 3; E: DE, EA — 2. Odd-degree vertices: C and D (both degree 3). Exactly two odd degrees, so an Eulerian trail exists (starting at C and ending at D, or vice versa) but no Eulerian circuit.

首先列出度数：deg(A)=4（边 AB, AC, AD, EA），deg(B)=2（AB, BC），deg(C)=3（BC, CD, AC），deg(D)=3（CD, DE, AD），deg(E)=2（DE, EA）。奇度顶点为 C 和 D，恰好两个，因此存在欧拉迹（例如从 C 到 D）但不存在欧拉回路。

For Hamiltonian: we need a cycle visiting all five vertices exactly once. Try A-B-C-D-E-A: A→B, B→C, C→D, D→E, E→A — all these edges exist, so A-B-C-D-E-A is a Hamiltonian cycle. Therefore, G is Hamiltonian. The graph also obviously has a Hamiltonian path (just omit the final edge).

对于汉密尔顿：我们需要一个恰好经过所有五个顶点的圈。尝试 A-B-C-D-E-A：所有边均存在，因此 A-B-C-D-E-A 是一个汉密尔顿圈。因此 G 是汉密尔顿图。显然也有汉密尔顿路径。

This example shows that a graph can have an Eulerian trail and a Hamiltonian cycle simultaneously — but the two properties are independent.

这个例子表明，一个图可以同时具有欧拉迹和汉密尔顿圈——但这两个性质是相互独立的。

9. Real-World Applications | 实际应用

Eulerian circuits model the classic ‘Chinese postman problem’: a postman wishes to traverse every street in a neighbourhood and return to the depot, minimising repeated edges. If the street graph has an Eulerian circuit, the optimal route is that circuit. Otherwise, an optimal strategy pairs odd-degree vertices to add minimal extra traversals.

欧拉回路模型化经典的“中国邮递员问题”：邮递员希望遍历街区的每条街道并返回邮局，同时最小化重复边。如果街道图有欧拉回路，最佳路线就是该回路。否则，最优策略是将奇度顶点配对以添加最少的额外遍历。

Hamiltonian cycles underpin the travelling salesman problem (TSP), where a salesperson must visit a number of cities exactly once and return to the start while minimising total distance. TSP is famously hard, but IB questions often ask for upper and lower bounds or use nearest-neighbour heuristics.

汉密尔顿圈支撑着旅行商问题（TSP），其中销售员必须恰好访问若干个城市一次并返回起点，同时最小化总路程。TSP 是著名的难题，但 IB 问题通常要求寻找上界、下界或使用最近邻启发式算法。

Paths and cycles also appear in scheduling, genome sequencing (Hamiltonian path in overlap graphs), and network routing. Understanding them equips students with tools far beyond the exam room.

路径和圈还出现在排课、基因组测序（重叠图中的汉密尔顿路径）和网络路由中。理解它们为学生提供了远远超越考场的工具。

10. Exam Tips and Summary | 考试技巧与总结

In IB exams, always start by writing down the vertex degrees for Eulerian problems. State clearly: ‘All vertices have even degree, therefore an Eulerian circuit exists.’ or ‘Exactly two vertices (X and Y) have odd degree, so an Eulerian trail exists from X to Y.’ Never claim a Hamiltonian cycle exists without checking a complete candidate nicely.

在 IB 考试中，面对欧拉问题总是先写下顶点度数。清晰地陈述：“所有顶点的度数均为偶数，因此存在欧拉回路。”或“恰好两个顶点（X 和 Y）度数为奇数，因此存在从 X 到 Y 的欧拉迹。”在没有确认一条完整的候选圈之前，不要说存在汉密尔顿圈。

When asked to find a Hamiltonian cycle, explicitly list the vertex sequence and verify each necessary edge is present. For ‘prove no Hamiltonian cycle exists’ questions, use parity arguments, cut-sets, or the fact that removing a Hamiltonian cycle leaves exactly two components, etc.

被要求寻找汉密尔顿圈时，明确列出顶点序列并验证每条所需边都存在。对于“证明不存在汉密尔顿圈”的问题，可使用奇偶性、割集论证，或利用移除汉密尔顿圈后留下恰好两个连通分支等事实。

Finally, remember that a path is a trail with no repeated vertices; a cycle is a closed path. Keep these definitions clean in your answer — IB examiners reward precision.

最后，记住路径是没有重复顶点的迹，圈是封闭路径。在答案中保持这些定义清晰——IB 阅卷官看重精确性。

Published by TutorHao | IB Mathematics Revision Series | aleveler.com

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

4 Paths and Cycles | 路径与圈