📚 Graph Theory: Key Concepts for IB & OCR Maths | IB OCR 数学：图论 考点精讲
Graph theory is a fascinating branch of discrete mathematics that features prominently in the IB Mathematics: Applications and Interpretation (AI) course, as well as in OCR Decision Mathematics modules. It provides a powerful language for modelling networks, from transport systems to friendship connections, and equips students with algorithmic thinking skills. This article breaks down the essential concepts, theorems and problem‑solving strategies you must master for your exams. We will walk through definitions, classic problems like the Chinese Postman and Travelling Salesman, and step‑by‑step algorithms such as Kruskal’s and Prim’s, all with clear bilingual explanations.
图论是离散数学中一个迷人的分支，在 IB 数学“应用与解释”(AI) 课程以及 OCR 决策数学模块中都占有重要地位。它为交通系统、朋友关系等网络建模提供了强大的语言，并帮助学生培养算法思维能力。本文将分解你必须掌握的考试核心概念、定理与解题策略。我们将逐一讲解定义、中国邮递员问题、旅行商问题等经典内容，以及 Kruskal 和 Prim 等算法的逐步操作，全部配以清晰的中英双语解释。
1. What is a Graph? | 什么是图？
A graph is a collection of vertices (or nodes) connected by edges. In exam contexts, a graph models relationships – for example, cities linked by roads, computers connected by cables, or people linked by friendships. Formally, a graph G = (V, E) consists of a set V of vertices and a set E of edges, where each edge is an unordered pair of vertices (in an undirected graph). Graphs can be drawn as dots with lines, but the geometric positions are irrelevant; only the connections matter.
图是由顶点（或称节点）通过边连接而成的集合。在考试情境中，图用于对关系进行建模——例如，由道路连接的城市、由线缆连接的计算机，或者由友谊联系起来的人。严格地说，一个图 G = (V, E) 由一个顶点集 V 和一个边集 E 组成，每条边都是顶点的无序对（无向图中）。图可以画成点与线，但几何位置无关紧要；只有连接关系才重要。
A graph may be simple (no loops, no multiple edges between the same pair of vertices). If multiple edges are allowed it is called a multigraph. A loop is an edge that starts and ends at the same vertex. In most IB and OCR problems, we work with simple, undirected graphs unless stated otherwise. Directed graphs (digraphs) have edges with a direction, shown as arrows; they appear in some topics like critical path analysis, but the core graph‑theory syllabus focuses on undirected graphs.
图可以是简单图（无环，无同对顶点间的多重边）。如果允许多重边，则称为多重图。环是起点和终点为同一顶点的边。在大多数 IB 和 OCR 问题中，除非特殊说明，否则我们处理的是简单无向图。有向图（digraph）的边带有方向，用箭头表示；它们出现在关键路径分析等主题中，但图论核心教学大纲主要关注无向图。
2. Basic Terminology | 基本术语
Imagine a graph representing a small airline network: vertices are airports, edges are direct flights. The order of a graph is the number of vertices. The size is the number of edges. Two vertices joined by an edge are called adjacent. An edge and a vertex are incident if the vertex is one of the edge’s endpoints. The degree of a vertex is the number of edges incident to it (a loop contributes 2). You will often need to list the degree of each vertex and spot the maximum or minimum degree.
设想一个代表小型航空网络的图：顶点是机场，边是直飞航线。图的阶是顶点的数目。大小是边的数目。由一条边连接的两个顶点称为邻接。如果顶点是某条边的端点，则该边与顶点关联。顶点的度是与它关联的边数（环算作 2）。你经常需要列出每个顶点的度，并找出最大度或最小度。
A walk is a sequence of vertices where each consecutive pair is adjacent. A trail is a walk with no repeated edges. A path is a walk with no repeated vertices (and therefore no repeated edges). A circuit is a closed trail (starts and ends at the same vertex). A cycle is a closed path with at least three vertices. These precise definitions are crucial for understanding Eulerian and Hamiltonian concepts.
途径是一个顶点序列，其中每一对连续的顶点都相邻。迹是没有重复边的途径。路径是没有重复顶点的途径（因此也不会有重复边）。回路是闭合的迹（起点与终点相同）。圈是至少包含三个顶点的闭合路径。这些精确定义对于理解欧拉和哈密顿概念至关重要。
A graph is connected if there is a path between every pair of vertices. If it is not connected, the connected pieces are called components. A graph with no cycles is called a forest; a connected forest is a tree. Trees have exactly |V| − 1 edges. These ideas underpin minimum spanning trees.
如果图中每一对顶点之间都存在一条路径，则称该图是连通的。若不连通，则连通的各个部分称为分量。没有圈的图称为森林；连通的森林即树。树恰好具有 |V| − 1 条边。这些思想是最小生成树的基础。
3. Handshaking Lemma and Degree Sequences | 握手引理与度序列
The Handshaking Lemma states that the sum of the degrees of all vertices in any undirected graph is exactly twice the number of edges: Σ deg(v) = 2|E|. This immediately implies that the sum of degrees is always even, and that any graph must have an even number of odd‑degree vertices. This simple fact is often used to check whether a given degree sequence can form a graph.
握手引理指出：在任何无向图中，所有顶点的度之和恰好是边数的两倍：Σ deg(v) = 2|E|。这立即表明度之和总是偶数，并且任何图中必定有偶数个奇度顶点。这个简单的事实常常用来检验一个给定的度序列是否可以构成一个图。
For example, the sequence (3, 3, 2, 1, 1) sums to 10, an even number. However, the number of odd entries is four (3, 3, 1, 1), which is even, so it passes the first test. To determine whether a sequence is graphic (i.e., there exists a simple graph with that degree sequence), we can apply the Havel–Hakimi algorithm, which is examinable in some syllabuses. OCR Decision might ask you to draw a graph with a given degree sequence or explain why none exists.
例如，序列 (3, 3, 2, 1, 1) 的和为 10，是偶数。奇数项的个数为四 (3, 3, 1, 1)，也是偶数，因此通过了第一项检验。要判断一个序列是否可图的（即存在一个具有该度序列的简单图），我们可以使用 Havel–Hakimi 算法，这在某些大纲中是考点。OCR 决策数学可能要求你画出一个具有给定度序列的图，或解释为何不存在。
- English: Test sequence (3,3,2,1,1): remove 3, subtract 1 from the next three highest: (2,1,0,1) → reorder (2,1,1,0). Remove 2, subtract 1 from next two: (0,0,0). Success – graphic.
- 中文：检验序列 (3,3,2,1,1)：去掉 3，从接下来的三个最高数中减 1：(2,1,0,1) → 重排为 (2,1,1,0)。去掉 2，从接下来的两个数中减 1：(0,0,0)。成功——是可图的。
4. Eulerian Graphs and Fleury’s Algorithm | 欧拉图与弗勒里算法
An Eulerian trail is a trail that uses every edge of a graph exactly once. If it starts and ends at the same vertex, it is an Eulerian circuit (or tour). A connected graph has an Eulerian circuit if and only if every vertex has even degree. It has an Eulerian trail but not a circuit if exactly two vertices have odd degree; the trail must start at one odd vertex and end at the other. These conditions are both necessary and sufficient. This is one of the most frequently tested theorems.
欧拉迹是一条恰好使用图中每条边一次的迹。如果它的起点和终点相同，则称为欧拉回路（或欧拉环游）。一个连通图具有欧拉回路当且仅当每个顶点的度均为偶数。若恰好有两个奇度顶点，则存在欧拉迹（但无欧拉回路）；该迹必须从一个奇度顶点开始，到另一个奇度顶点结束。这些条件既是必要的也是充分的。这是考试中最常考的定理之一。
To actually find an Eulerian trail, we use Fleury’s algorithm (also called the “bridge‑avoiding” algorithm). Starting from the appropriate vertex, we travel along an edge and then delete it, but we must never cross a bridge (an edge whose removal disconnects the remaining graph) unless there is no alternative. This algorithm is required knowledge for OCR Decision 1 and appears in IB AI investigations.
为了实际找到一条欧拉迹，我们使用弗勒里算法（也称为“避桥”算法）。从适当的顶点出发，沿着一条边移动并删除该边，但除非别无选择，否则绝不能跨越桥（即删除后会使剩余图不连通的边）。此算法是 OCR 决策数学 1 要求的内容，也出现在 IB AI 的探究中。
Example: A simple connected graph with vertices A (deg 2), B (deg 4), C (deg 2), D (deg 2) – all even – has an Eulerian circuit. A possible circuit is A–B–C–B–D–B–A. If exactly two vertices, say A and D, were odd, the trail would start at A and end at D.
示例：一个简单的连通图，顶点 A（度 2）、B（度 4）、C（度 2）、D（度 2）——全是偶数——具有欧拉回路。一条可能的回路是 A–B–C–B–D–B–A。如果恰好有两个奇度顶点，比如 A 和 D，则欧拉迹将从 A 开始，到 D 结束。
5. Hamiltonian Graphs | 哈密顿图
A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle (or circuit) does the same and returns to the start. Unlike Eulerian graphs, there is no simple necessary and sufficient condition for Hamiltonicity – it is an NP‑complete problem in general. However, IB and OCR exams test some sufficient conditions, such as Dirac’s theorem: if a simple graph with n ≥ 3 vertices has every vertex of degree at least n/2, then the graph is Hamiltonian. Ore’s theorem generalises this: if for every pair of non‑adjacent vertices the sum of their degrees is at least n, then the graph is Hamiltonian.
哈密顿路径恰好访问每个顶点一次；哈密顿圈（或回路）同样访问每个顶点一次并返回起点。与欧拉图不同，哈密顿性没有简单的充要条件——一般而言这是一个 NP 完全问题。不过，IB 和 OCR 考试会测试一些充分条件，例如狄拉克定理：如果一个具有 n ≥ 3 个顶点的简单图中每个顶点的度至少为 n/2，则该图是哈密顿的。奥尔定理是更一般的结论：如果每一对不相邻的顶点的度之和至少为 n，则该图是哈密顿的。
Exams often ask you to find a Hamiltonian cycle in a given graph (often a complete or nearly complete graph, or one representing a small network) by trial and improvement, or to confirm that Dirac’s theorem holds. The Travelling Salesman Problem is essentially the problem of finding a minimum‑weight Hamiltonian cycle in a weighted complete graph, which we will address later.
考试中经常要求你在给定图（通常是完全图或近似完全图，或是代表小型网络的图）中通过尝试与改进找到哈密顿圈，或者验证狄拉克定理成立。旅行商问题本质上就是在加权完全图中寻找最小权哈密顿圈的问题，我们稍后会讨论。
6. Trees and Properties | 树及其性质
A tree is a connected acyclic graph. Key properties: a tree with n vertices has exactly n − 1 edges; adding any new edge creates exactly one cycle; removing any edge disconnects the tree; and there is a unique simple path between any two vertices. A spanning tree of a connected graph is a subgraph that is a tree and includes all vertices. Every connected graph has at least one spanning tree. The number of spanning trees in a complete graph Kn is given by Cayley’s formula: nn−2. This is a beautiful combinatorial result that occasionally appears in extension questions.
树是连通且无圈的图。关键性质：具有 n 个顶点的树恰好有 n − 1 条边；添加任意一条新边会恰好创建一个圈；删除任意一条边会使树不连通；任意两个顶点之间存在唯一的简单路径。一个连通图的生成树是一个包含所有顶点的树子图。每个连通图都至少有一棵生成树。完全图 Kn 中生成树的数目由凯莱公式给出：nn−2。这是一个优美的组合结果，偶尔在扩展题中出现。
In the context of network design, a spanning tree represents a minimally connected network – for instance, the cheapest way to connect all cities with roads where no redundancy is required. The search for a minimum spanning tree (MST) in a weighted graph is therefore a fundamental optimisation problem.
在网络设计的语境中，生成树代表一个最小连通网络——例如，用道路连接所有城市且无需冗余的最廉价方式。因此，在加权图中寻找最小生成树（MST）是一个基本的优化问题。
7. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树：Kruskal 算法
Kruskal’s algorithm builds a minimum spanning tree by repeatedly adding the edge of smallest weight that does not form a cycle. The steps are: (1) List all edges in increasing order of weight. (2) Start with an empty set of edges. (3) For each edge (in that order), add it to the tree if it connects two different components of the forest built so far. (4) Stop when all vertices are connected (n − 1 edges have been added). This is a classic greedy algorithm.
Kruskal 算法通过反复加入不构成圈的最小权边来构建最小生成树。步骤如下：（1）按权值递增顺序列出所有边。（2）从空的边集开始。（3）依次检查每条边，若它连接了当前森林中的两个不同分量，则将其加入树中。（4）当所有顶点均已连通（已添加 n − 1 条边）时停止。这是一个经典的贪心算法。
Examiners often provide a table of edges with weights and ask you to state the order of selection and the total weight. A matrix or a drawn network may also be given. Make sure you can detect cycles visually or by listing the current components. If two edges have the same weight, either may be chosen; however, this may lead to different (but equally minimal) spanning trees.
考官通常会给出带权值的边表格，要求你写出选取顺序和总权值。也可能给出矩阵或网络图。要确保你能够通过观察或列出当前分量来检测圈。如果两条边权值相同，可以任选其一；但这可能导致不同的（但等价最小的）生成树。
Example: Edges sorted: AB(2), CD(2), BC(3), AC(4), BD(5). Choose AB, then CD, then BC (connects components without cycle); total weight 2+2+3=7. AC would form a cycle, so skip.
示例：边按权排序：AB(2), CD(2), BC(3), AC(4), BD(5)。选取 AB，再选 CD，然后选 BC（分量合并，无圈）；总权 2+2+3=7。AC 会形成圈，故跳过。
8. Minimum Spanning Tree: Prim’s Algorithm | 最小生成树：Prim 算法
Prim’s algorithm grows a tree from an arbitrary starting vertex. (1) Choose any vertex to start; it becomes the current tree. (2) From all edges connecting a vertex in the tree to a vertex outside the tree, pick the one with the smallest weight. (3) Add that edge and its new vertex to the tree. (4) Repeat until all vertices are included. Like Kruskal’s, Prim’s algorithm is greedy and produces an MST. It is particularly efficient when the graph is dense and represented by a matrix.
Prim 算法从一个任选的起始顶点开始逐步生长出一棵树。（1）任选一个顶点作为起始，它构成当前树。（2）在所有连接树内顶点与树外顶点的边中，选取权值最小的一条。（3）将该边及其新顶点加入树中。（4）重复直至所有顶点均被包含。与 Kruskal 算法一样，Prim 算法也是贪心的，并能生成最小生成树。当图是稠密且用矩阵表示时，Prim 算法尤其高效。
In an exam, you might be given a distance table and asked to apply Prim’s algorithm, showing the order of edge selection and the total minimum weight. You can use either a graphical or tabular method (the latter sometimes called Prim’s algorithm on a matrix). Be careful to update the list of available edges each time a vertex is added.
在考试中，你可能会收到一个距离表，并被要求应用 Prim 算法，展示边选取顺序和最小总权。你可以使用图形法或表格法（后者有时称为矩阵上的 Prim 算法）。注意每次添加顶点后要更新可用边的列表。
Example: Start at vertex A. Matrix shows A‑B:4, A‑C:2, A‑D:5. Choose A‑C(2). Now tree = {A,C}. Edges from {A,C} to {B,D}: C‑B:3, A‑B:4, C‑D:6, A‑D:5. Select C‑B(3). Tree = {A,B,C}. Edges to D: B‑D:1, C‑D:6, A‑D:5. Select B‑D(1). MST total = 2+3+1 = 6.
示例：从顶点 A 开始。矩阵显示 A‑B:4, A‑C:2, A‑D:5。选取 A‑C(2)。现在树 = {A,C}。从 {A,C} 到 {B,D} 的边：C‑B:3, A‑B:4, C‑D:6, A‑D:5。选取 C‑B(3)。树 = {A,B,C}。到 D 的边：B‑D:1, C‑D:6, A‑D:5。选取 B‑D(1)。MST 总权 = 2+3+1 = 6。
9. Chinese Postman Problem | 中国邮递员问题
The Chinese Postman Problem (CPP) asks for a shortest closed walk that traverses every edge of a weighted graph at least once. This is essentially finding an optimal route for a postman who must walk along all streets (edges) and return to the start. If the graph is Eulerian (all even degrees), the optimal route is simply an Eulerian circuit, with total weight equal to the sum of all edge weights. If there are odd‑degree vertices, we must duplicate a set of edges (adding extra walks) to make the graph Eulerian with minimal extra cost.
中国邮递员问题 (CPP) 要求找出一个最短的闭合途径，使得加权图中的每条边至少被遍历一次。这本质上是为一位必须走遍所有街道（边）并返回起点的邮递员寻找最优路线。如果图是欧拉的（均为偶度），最优路线就是一条欧拉回路，总权等于所有边权之和。如果存在奇度顶点，我们必须复制一组边（添加额外行走）以使图成为欧拉图，且额外代价最小。
The standard solution for a graph with exactly two odd vertices (the usual exam case) is to find the shortest path between those two odd vertices, and then duplicate every edge on that path. The postman then walks the original edges plus the duplicated edges, forming an Eulerian trail. For four or more odd vertices, we pair them up to minimise total length of added paths – this is done by inspection or using a minimal matching approach, but exams typically restrict to two odd vertices.
对于恰好有两个奇度顶点的图（考试常见情形），标准解法是找出这两个奇度顶点之间的最短路径，然后复制该路径上的每条边。邮递员走遍原始边加上复制边，形成一条欧拉迹。对于四个或更多奇度顶点，需要将它们两两配对以最小化添加路径的总长度——可通过观察或最小匹配方法解决，但考试通常限定为两个奇度顶点。
Example: A weighted graph with odd vertices C and G. Shortest path C–G: C→D(4)→G(3) total 7. Duplicate edges CD and DG. Now all vertices are even. Find an Eulerian circuit in the augmented graph; total weight = original total (say 28) + duplicated 7 = 35. The postman’s route covers all edges and returns to start for a total distance of 35.
示例：一个加权图，奇度顶点为 C 和 G。最短路径 C–G：C→D(4)→G(3)，总长 7。复制边 CD 和 DG。现在所有顶点均为偶度。在增广图中找出一条欧拉回路；总权 = 原始总权（比如 28）+ 复制部分 7 = 35。邮递员路线覆盖所有边并返回起点，总距离为 35。
10. Travelling Salesman Problem (TSP) | 旅行商问题 (TSP)
The Travelling Salesman Problem aims to find the shortest Hamiltonian cycle (a tour visiting every vertex exactly once and returning to start) in a weighted complete graph. This is a classic NP‑hard problem; exact algorithms are computationally infeasible for large networks, so IB and OCR focus on heuristic methods for near‑optimal solutions: the upper bound and lower bound techniques.
旅行商问题旨在加权完全图中寻找最短的哈密顿圈（恰好访问每个顶点一次并返回起点的环游）。这是一个经典的 NP 难问题；对于大型网络，精确算法在计算上是不可行的，因此 IB 和 OCR 侧重于寻找近似最优解的启发式方法：上界和下界技术。
A quick upper bound can be found using the nearest neighbour algorithm: start at a chosen vertex, repeatedly go to the nearest unvisited vertex, then finally return to the start. This gives a feasible tour whose total length is not necessarily minimal, but often close. Another method to obtain an upper bound is to find a tour by inspection. The best upper bound found becomes the candidate optimum. To find a lower bound, we often delete a vertex and find a minimum spanning tree of the remaining graph, then add the two shortest edges from the deleted vertex to the tree. This provides a theoretical minimum that no tour can beat.
使用最近邻算法可以快速找到一个上界：从选定顶点出发，反复前往最近的未访问顶点，最后返回起点。这给出一个可行环游，其总长度不一定最小，但通常接近。另一种获得上界的方法是通过观察找出一条环游。找到的最佳上界即候选最优值。为了找出下界，我们常删除一个顶点，找出剩余图的最小生成树，然后将从被删顶点出发的两条最短边加到树上。这样提供的理论最小值是任何环游都无法低于的。
Exams often ask: “Use the nearest neighbour algorithm starting at A to find an upper bound for the TSP”, and “By deleting vertex E, find a lower bound”. The answer then states something like “The optimal tour lies between 42 (lower bound) and 45 (upper bound)”. If the bounds are equal, the tour is optimal. Otherwise, further investigation like looking for improvements (e.g., using shortcuts) may be required.
考试中常要求：“使用从 A 点出发的最近邻算法找出 TSP 的一个上界”，以及“通过删除顶点 E，找出一个下界”。然后答案会给出如“最优环游介于 42（下界）与 45（上界）之间”。如果上下界相等，则该环游是最优的。否则，可能需要进一步改进，如利用捷径等。
11. Algorithms and Exam Technique | 算法与应试技巧
Mastering graph theory for IB and OCR requires not just memorising theorems but also practising the step‑by‑step execution of algorithms. In the exam, you must show all your working clearly. For Kruskal, list edges in order, mark which ones are selected, and give a reason for rejection (e.g., “would form a cycle”). For Prim, state your starting vertex, list edges from the tree at each stage, and indicate the chosen edge with its weight. For Chinese Postman, identify odd vertices, find the shortest path, and calculate total extra cost. For TSP, show the sequence of vertices visited in an upper bound attempt and the MST used for a lower bound.
掌握 IB 和 OCR 的图论不仅需要记忆定理，还要练习算法的逐步执行。考试中你必须清晰地展示所有解题过程。对于 Kruskal 算法，按顺序列出边，标明哪些被选中，并给出拒绝理由（如“会形成圈”）。对于 Prim 算法，陈述起始顶点，在每个阶段列出树伸出的边，并指明所选边及其权值。对于中国邮递员问题，找出奇度顶点，找出最短路径，并计算额外总成本。对于 TSP，写出上界尝试中访问的顶点序列和下界使用的最小生成树。
Common pitfalls: forgetting that a Hamiltonian cycle must return to the start; confusing trails, paths, and circuits; misapplying the handshaking lemma (e.g., thinking the sum of degrees being even guarantees the existence of a graph with that sequence – it does not guarantee simplicity); and making arithmetic errors in weighting. Also, always check that your MST has exactly n−1 edges. Practice with past papers to become fluent in the notation and expectations.
常见错误：忘记哈密顿圈必须返回起点；混淆迹、路径和回路；误用握手引理（例如认为度之和为偶数就保证存在具有该度序列的图——这并不能保证简单性）；以及在加权时犯算术错误。此外，始终检查你的最小生成树是否恰好有 n−1 条边。通过做往年真题来熟悉符号规范与考查要求。
Finally, treat graph theory as a visual and logical puzzle. Drawing clear diagrams can save you from mistakes. Use a highlighter to mark edges that are selected or duplicated. And remember, the elegance of these problems – from Euler’s bridges to modern logistics – is why they have stayed at the heart of school mathematics.
最后，把图论当作视觉与逻辑的谜题。画清晰的图表可以让你避免错误。用荧光笔标记被选中或被复制的边。并请记住，这些问题——从欧拉的桥到现代物流——的优雅正是它们始终处于学校数学核心地位的原因。
12. Summary of Key Formulas and Facts | 关键公式与事实总结
| Concept / Formula | Statement |
|---|---|
| Handshaking Lemma | Σ deg(v) = 2|E| |
| Eulerian circuit condition | Connected & all vertices even degree |
| Eulerian trail condition | Connected & exactly two odd vertices |
| Dirac’s theorem (Hamiltonian) | n ≥ 3, every vertex deg ≥ n/2 ⇒ Hamiltonian |
| Ore’s theorem (Hamiltonian) | For all non‑adjacent pairs, deg(x)+deg(y) ≥ n ⇒ Hamiltonian |
| Tree edges count | A tree with n vertices has n − 1 edges |
| Cayley’s formula | Number of spanning trees of Kn is nn−2 |
| CPP extra cost | Shortest path between odd vertices; duplicate its edges |
| TSP lower bound (vertex deletion) | MST of remaining graph + two shortest edges from deleted vertex |
| TSP upper bound | Nearest neighbour algorithm or inspection |
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导