A-Level Mathematics: Graph Theory Key Points | A-Level 数学：图论考点精讲

📚 A-Level Mathematics: Graph Theory Key Points | A-Level 数学：图论考点精讲

Graph theory is a core topic in A-Level Decision Mathematics, providing the foundation for modelling networks, optimising routes, and solving real-world logistical problems. This revision guide walks you through every essential concept, algorithm, and exam tip you need to master graph theory. From vertices and edges to Eulerian trails, minimum spanning trees, and Dijkstra’s shortest path, we explain it all in plain language with clear examples.

图论是 A-Level 决策数学的核心内容，为网络建模、路径优化和现实物流问题提供理论基础。本复习指南带你逐一梳理必须掌握的图论概念、算法和考试技巧。从顶点、边到欧拉迹、最小生成树，再到迪杰斯特拉最短路径，我们用最通俗的语言和清晰的例子为你讲透每一个考点。

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

A graph is a mathematical structure consisting of a set of vertices (nodes) connected by edges (arcs). It is used to represent relationships or connections between objects. In A-Level Mathematics, graphs are typically undirected unless stated otherwise, meaning edges have no direction. For example, a graph could model a road network where towns are vertices and roads are edges.

图是由一组顶点（节点）和连接这些顶点的边（弧）组成的数学结构，用来表示对象之间的关系或连接。在 A-Level 数学中，除非特别说明，图通常是无向的，即边没有方向。例如，可以用图来模拟道路网络，城镇是顶点，道路是边。

A graph may be simple (no loops or multiple edges), but in decision problems we often work with weighted graphs, where each edge is assigned a numerical value representing cost, distance, or time. Loops and multiple edges are sometimes allowed depending on the context.

图可以是简单的（无环、无重边），但在决策问题中我们常处理加权图，其中每条边被赋予一个数值，代表成本、距离或时间。根据实际情况，有时允许出现环和重边。

2. Basic Terminology | 基本术语

To work with graphs, you must be confident with the key vocabulary. A vertex (plural: vertices) is a point in the graph. An edge connects two vertices. If an edge connects vertex A to vertex B, we say A and B are adjacent, and the edge is incident to both A and B. A path is a sequence of edges that connects a sequence of vertices without repeating vertices. A cycle is a closed path where the start and end vertex are the same, but no other vertex is repeated.

要处理图，必须掌握关键术语。顶点是图中的点。边连接两个顶点。如果一条边连接顶点 A 和 B，我们称 A 与 B 相邻，并称该边与 A 和 B 关联。路径是一系列边的序列，连接一系列顶点且不重复经过顶点。回路是一个闭合的路径，起点和终点相同，且途中不重复经过其他顶点。

A connected graph is one where there is a path between every pair of vertices. If a graph is not connected, it splits into several components. A loop is an edge that starts and ends at the same vertex, and multiple edges are two or more edges connecting the same pair of vertices.

连通图是指任意两个顶点之间都存在路径的图。如果图不连通，则会分成若干个连通分量。环是起点和终点在同一顶点的边；重边是连接同一对顶点的两条或更多条边。

3. Types of Graphs | 图的类型

In A-Level Decision Maths, you will encounter several different types of graphs. The most common is a simple graph, which has no loops or multiple edges. A weighted graph has numbers on its edges, called weights. A directed graph, or digraph, has edges with direction arrows, representing one-way routes. A bipartite graph has its vertices split into two sets, and edges only connect vertices from one set to the other; this is useful for modelling matching problems.

在 A-Level 决策数学中，你会遇到多种不同类型的图。最常见的是简单图，没有环和重边。加权图的边上标有数字，称为权。有向图（又称 digraph）的边带有方向箭头，表示单向路径。二分图将顶点分成两个集合，边只连接两个集合之间的顶点；这在匹配问题中十分有用。

A complete graph, denoted Kₙ, is a simple graph in which every pair of vertices is connected by exactly one edge. For instance, K₃ is a triangle, K₄ has 4 vertices with all 6 possible edges drawn. The number of edges in a complete graph on n vertices is n(n – 1)/2.

完全图，记作 Kₙ，是任意两个顶点之间都恰好有一条边的简单图。例如 K₃ 是一个三角形，K₄ 有 4 个顶点，所有 6 条可能的边都存在。一个包含 n 个顶点的完全图的边数为 n(n – 1)/2。

4. Degree of a Vertex | 顶点的度

The degree (or valency) of a vertex is the number of edges incident to it. A loop contributes 2 to the degree. For a graph to be drawn by hand without lifting the pen and without retracing edges, the degrees of vertices determine the existence of Eulerian trails or circuits. The sum of the degrees of all vertices in any undirected graph is twice the number of edges – this is the Handshaking Lemma.

顶点的度（或价）是与该顶点关联的边的条数。一个环对度的贡献为 2。能否一笔画出图（不抬笔、不重复边）取决于顶点的度数，这决定了欧拉迹或欧拉回路的存在性。在任何无向图中，所有顶点的度数之和等于边数的两倍——这就是握手引理。

An odd vertex is one with an odd degree, and an even vertex has an even degree. The Handshaking Lemma implies that the number of odd-degree vertices in any graph is always even. This fact is essential when checking whether a graph is Eulerian or semi-Eulerian.

奇顶点是指度数为奇数的顶点，偶顶点是度数为偶数的顶点。握手引理表明，任何图中奇度顶点的数量总是偶数。这一事实在判断图是否为欧拉图或半欧拉图时至关重要。

5. Eulerian and Semi-Eulerian Graphs | 欧拉图与半欧拉图

An Eulerian circuit (or Eulerian trail) is a closed trail that traverses every edge exactly once. A connected graph is Eulerian if and only if every vertex has an even degree. To find an Eulerian circuit, you can start at any vertex and proceed by removing edges as you go, never crossing a bridge (an edge whose removal disconnects the graph) unless necessary. This is related to the Chinese postman problem, where the goal is to find the shortest closed walk covering every edge at least once.

欧拉回路（或欧拉迹）是一条恰好遍历每条边一次且回到起点的闭合迹。一个连通图是欧拉图的充要条件是每个顶点的度数均为偶数。寻找欧拉回路时，可以从任意顶点出发，边走边删除走过的边，除非万不得已，不要经过桥（去掉后会使图不连通的边）。这与中国邮递员问题密切相关，目标是在覆盖每条边至少一次的前提下找到最短闭合步行。

A graph is semi-Eulerian if exactly two vertices have odd degree; such a graph has an Eulerian trail that starts at one odd vertex and ends at the other, covering every edge exactly once but not closing the loop. If a graph has more than two odd vertices, it is neither Eulerian nor semi-Eulerian, and the Chinese postman algorithm must be applied to find an optimal traversal that repeats edges.

如果一个图中恰好有两个奇顶点，则它是半欧拉图；这样的图存在一条欧拉迹，从其中一个奇顶点出发，到另一个奇顶点结束，恰好遍历每条边一次但不闭合。如果一个图含有两个以上的奇顶点，则它既不是欧拉图也不是半欧拉图，此时必须应用中国邮递员算法，通过重复某些边来找到最优遍历方案。

6. Hamiltonian Graphs | 哈密顿图

A Hamiltonian cycle is a cycle that visits every vertex exactly once and returns to the start. A graph that contains a Hamiltonian cycle is called Hamiltonian. Unlike the Eulerian case, there is no simple necessary and sufficient condition for a graph to be Hamiltonian, making it a classic NP-complete problem. For small graphs, you can often find a Hamiltonian cycle by inspection, but systematic methods like nearest neighbour or branch-and-bound are needed for larger instances in the travelling salesman problem.

哈密顿回路是恰好经过每个顶点一次并回到起点的回路。包含哈密顿回路的图称为哈密顿图。与欧拉的情况不同，判断图是否为哈密顿图没有简单的充要条件，这使其成为经典的 NP 完全问题。对于小图，通常可以通过观察找到哈密顿回路，但在旅行商问题等较大实例中，就需要最近邻法、分支定界等系统方法。

A Hamiltonian path is a path that visits every vertex exactly once but does not return to the start. Many exam questions ask you to determine whether a given graph is Hamiltonian, or to find a Hamiltonian cycle of minimum total weight, which directly leads to the travelling salesman problem.

哈密顿路径是恰好经过每个顶点一次但不回到起点的路径。许多考题会让你判断给定图是否为哈密顿图，或者找出最小总权重的哈密顿回路，这直接引出了旅行商问题。

7. Trees and Spanning Trees | 树与生成树

A tree is a connected graph with no cycles. In a tree, there is exactly one path between any two vertices. A tree with n vertices always has exactly n – 1 edges. A spanning tree of a connected graph is a subgraph that is a tree and includes all the vertices of the original graph. Every connected graph has at least one spanning tree.

树是没有回路的连通图。在树中，任意两个顶点之间恰好有一条路径。有 n 个顶点的树恰好有 n – 1 条边。连通图的生成树是一个包含原图所有顶点的树状子图。每个连通图都至少有一棵生成树。

A minimum spanning tree (MST) is a spanning tree of a weighted graph with the smallest possible total edge weight. Two algorithms are used to find the MST: Kruskal’s algorithm and Prim’s algorithm. Both are guaranteed to produce an optimal solution. MSTs have applications in designing efficient networks, such as telephone lines or pipelines.

最小生成树 (MST) 是加权图中总边权最小的生成树。有两种算法可用来寻找 MST：克鲁斯卡尔算法和普里姆算法。两者都能保证产生最优解。MST 在设计电话线、管道等高效网络中有广泛应用。

8. Kruskal’s Algorithm | 克鲁斯卡尔算法

Kruskal’s algorithm builds a minimum spanning tree by considering edges in order of increasing weight. It starts with a list of all edges sorted by weight. The algorithm selects the next smallest edge that does not form a cycle with the already selected edges. Continue until n – 1 edges have been selected, where n is the number of vertices.

克鲁斯卡尔算法通过按权重递增顺序考虑边来构建最小生成树。它首先列出所有边并按权重排序。算法选择下一条与已选边不形成回路的最小权边。重复此过程，直到选定了 n – 1 条边，其中 n 为顶点数。

• Step 1: List all edges in ascending order of weight.
• Step 2: Choose the edge with the smallest weight. Add it to the tree.
• Step 3: From the remaining edges, choose the next smallest edge that does not create a cycle. Add it.
• Step 4: Repeat Step 3 until you have (number of vertices – 1) edges.

• 第一步：列出所有边并按权重升序排列。
• 第二步：选择权重最小的边，加入树中。
• 第三步：从剩余边中选择下一条不产生回路的最小权重边，加入树中。
• 第四步：重复第三步，直到获得（顶点数 – 1）条边。

To check for cycles, you can use a simple visual method or label vertices as sets. If two vertices of the candidate edge already belong to the same component, adding that edge would form a cycle. Kruskal’s algorithm is particularly convenient for sparse graphs because you can process the sorted list quickly.

检查回路可以使用简单的可视化方法或将顶点分组建模。如果候选边的两个顶点已经属于同一个连通分支，加入该边就会形成回路。克鲁斯卡尔算法特别适合稀疏图，因为你可以快速处理排序好的列表。

9. Prim’s Algorithm | 普里姆算法

Prim’s algorithm grows the minimum spanning tree from a starting vertex. It uses a greedy approach: at each step, add the smallest-weight edge connecting a vertex already in the tree to a vertex not yet in the tree. The initial vertex can be chosen arbitrarily. Continue until all vertices are included.

普里姆算法从某个起始顶点开始逐步生成最小生成树。它采用贪心策略：每一步加入连接已在树中的顶点与尚未在树中的顶点之间的最小权重边。起始顶点可任意选择。持续操作直到所有顶点都包含在树中。

• Step 1: Choose any starting vertex. Mark it as ‘in the tree’.
• Step 2: Find the edge of smallest weight that connects a vertex in the tree to a vertex not yet in the tree. Add this edge and the new vertex to the tree.
• Step 3: Repeat Step 2 until all vertices are connected.
• If there are multiple edges with the same smallest weight, any may be chosen – the minimum total weight will be the same.

• 第一步：任选一个起始顶点，将其标记为“在树中”。
• 第二步：找出连接树中顶点与树外顶点的权重最小的边，将该边和新顶点加入树中。
• 第三步：重复第二步，直到所有顶点都被连接。
• 若有多条相同最小权重的边，任选一条均可——最终的最小总权不变。

Prim’s algorithm is often demonstrated using a table or a matrix for dense graphs, where you update the minimum distance to the tree for each remaining vertex. Both Kruskal and Prim always produce a minimum spanning tree, but exam questions may require you to show steps clearly, especially the order of joining edges.

普里姆算法常用于稠密图，通过表格或矩阵展示，更新每个剩余顶点到树的最短距离。克鲁斯卡尔和普里姆算法都总能生成最小生成树，但考题可能要求你清晰展示每一步，特别是加入边的顺序。

10. Dijkstra’s Algorithm (Shortest Path) | 迪杰斯特拉算法（最短路径）

Dijkstra’s algorithm finds the shortest path from a start vertex to all other vertices in a weighted graph with non-negative edge weights. It works by iteratively assigning permanent labels to vertices. At each stage, the vertex with the smallest temporary label is made permanent, and the labels of its neighbours are updated if a shorter path is found through it.

迪杰斯特拉算法可在具有非负边权的加权图中找到从起始顶点到所有其他顶点的最短路径。它通过迭代地给顶点标上永久标签来工作。在每一步，具有最小临时标签的顶点被设为永久，并用它更新邻居的标签，如果通过该顶点能获得更短路径的话。

The standard implementation uses a table or a priority queue. In the table approach, each vertex is given a working value (distance from start), and a completed label once finalised. The order of becoming permanent is also recorded, which reconstructs the path. This algorithm is crucial for problems like navigation, logistics, and network routing.

标准实现使用表格或优先队列。在表格方式中，每个顶点都有一个工作值（与起点的距离），一旦最终确定就成为永久标签。同时记录变为永久的顺序，以便重建路径。该算法对于导航、物流和网络路由等问题至关重要。

Vertex	Order of labelling	Final value
A	1	0
B	2	5
C	3	7

When reconstructing the shortest path from A to C, trace back from C to A using the order of permanence and the edges used in the updates. Always indicate your working values in the exam to gain full marks.

在重建从 A 到 C 的最短路径时，根据永久标签的顺序和更新时使用的边从 C 回溯到 A。考试时务必列出工作值以获取满分。

11. The Travelling Salesman Problem (TSP) | 旅行商问题

The travelling salesman problem seeks to find a Hamiltonian cycle of minimum total weight, visiting every vertex exactly once and returning to the start. This is a classic NP-hard problem, meaning that for large graphs, exact optimal solutions are impractical. In A-Level, you work with small complete graphs and apply both heuristic algorithms and exact methods.

旅行商问题旨在找到一条总权最小的哈密顿回路，恰好经过每个顶点一次并返回起点。这是经典的 NP 难问题，意味着对于大规模图，精确最优解难以实际求得。在 A-Level 中，你处理的是小规模完全图，并应用启发式算法和精确方法。

Two common heuristics that provide upper bounds are the nearest neighbour algorithm and the minimum spanning tree heuristic. For a lower bound, we use the concept of removing a vertex and finding the MST of the remaining graph, then adding the two smallest edges incident to the removed vertex. The optimal tour weight lies between the best lower bound and the smallest upper bound found.

提供上界的两种常用启发式算法是最近邻算法和最小生成树启发式。对于下界，我们使用移除一个顶点、找出剩余图的最小生成树，再加上与被移除顶点关联的两条最小边。最优回路的总权重介于最佳下界与最小上界之间。

The classical TSP requires the triangle inequality to be satisfied (direct edge is not longer than any indirect path via other vertices). Exam questions often ask you to find an upper bound by nearest neighbour and a lower bound by a vertex deletion method, then interpret the interval for the optimal solution.

经典 TSP 要求满足三角不等式（直连边不長于经过其他顶点的任何间接路径）。考试题常要求你用最近邻法求上界，用删点法求下界，然后解读最优解的区间。

Published by TutorHao | Mathematics Revision Series | aleveler.com

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