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

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

Graph theory is a cornerstone of Edexcel A-Level Decision Mathematics, providing powerful models for networks such as transport systems, utility networks, and scheduling problems. It equips students with algorithmic thinking and the ability to find optimal solutions in real-world contexts. This revision guide distills the key graph theory concepts and algorithms you must master: from basic terminology to Kruskal, Prim, Dijkstra, the Chinese Postman Problem, and bounds for the Travelling Salesman Problem.

图论是 Edexcel A-Level 决策数学的核心内容，它为交通网络、公用设施网络和调度问题等提供了强大的建模工具。掌握图论能培养你的算法思维，帮助你求解现实中的最优问题。这份考点精讲浓缩了你必须掌握的图论关键概念和算法：从基本术语到克鲁斯卡尔算法、普里姆算法、迪杰斯特拉算法、中国邮递员问题，以及旅行商问题的上下界。

1. Basic Terminology | 基本术语

A graph G consists of a set of vertices (nodes) and a set of edges (arcs) that connect pairs of vertices. Vertices can represent locations, while edges represent routes, pipes, or relationships.

图 G 由一组顶点（节点）和一组连接这些顶点的边（弧）构成。顶点可代表地点，边则代表路线、管道或关系。

The degree of a vertex is the number of edges incident to it. In a simple graph, each edge contributes 1 to the degree of both its endpoints. The sum of the degrees of all vertices is always twice the number of edges (Handshaking Lemma).

顶点的度是指与该顶点相连的边的条数。在简单图中，每条边为其两个端点各贡献 1 度。所有顶点的度数之和总是边数的两倍（握手引理）。

A walk is a sequence of edges in which consecutive edges share a vertex. A trail is a walk with no repeated edges. A path is a trail with no repeated vertices. A cycle is a closed path where the starting and ending vertex are the same.

通路是一系列边，其中相邻的边共享一个顶点。迹是一条没有重复边的通路。路径是一条没有重复顶点的迹。回路是一条起点和终点相同的闭合路径。

A graph is connected if there is a path between every pair of vertices. Otherwise it is disconnected, with several components.

如果一个图中的任意两个顶点之间都存在一条路径，则这个图是连通的。否则就是非连通图，会分为多个连通分量。

2. Types of Graphs | 图的类型

A simple graph has no loops and no multiple edges between the same pair of vertices. A multigraph may have multiple edges connecting the same pair of vertices. A loop is an edge that starts and ends at the same vertex.

简单图没有环，也没有连接同一对顶点的重边。多重图允许在相同顶点对之间存在多条边。环是一条起点和终点为同一顶点的边。

A directed graph (digraph) has edges with a direction, indicated by arrows. In a digraph, each edge has an initial vertex and a terminal vertex. The out-degree and in-degree of a vertex count the number of edges leaving and entering it respectively.

有向图（有向网络）的边具有方向，用箭头表示。在有向图中，每条边有一个起点和一个终点。顶点的出度和入度分别统计离开和进入该顶点的边的数量。

A weighted graph assigns a numerical weight (often distance, cost or time) to each edge. This is the most common type in decision algorithms. A complete graph is a simple graph in which every pair of distinct vertices is connected by an edge, denoted K_n for n vertices.

加权图给每条边赋予一个数值权重（通常是距离、成本或时间）。这是决策算法中最常用的类型。完全图是一个简单图，其中每一对不同的顶点都有一条边相连，记作 K_n（n 个顶点）。

A tree is a connected graph with no cycles. A spanning tree of a connected graph is a subgraph that includes all the vertices and is a tree. A minimum spanning tree (MST) has the smallest possible total weight.

树是一个无回路的连通图。一个连通图的生成树是包含了所有顶点、且本身是一棵树的子图。最小生成树是具有最小总权重的生成树。

3. Matrix Representation | 矩阵表示

Graphs can be represented using matrices, which are very convenient for algorithmic processing. An adjacency matrix records which vertices are directly connected. For a graph with n vertices, the entry in row i, column j is 1 if vertices i and j are adjacent, and 0 otherwise. For a weighted graph, the entry can be the weight instead.

图可以用矩阵表示，这在算法处理时非常方便。邻接矩阵记录了哪些顶点直接相连。对一个有 n 个顶点的图，如果顶点 i 和 j 相邻，则第 i 行第 j 列的元素为 1，否则为 0。对于加权图，可以用权重代替 1。

A distance matrix is a square matrix where each entry gives the weight of the edge directly connecting the two vertices. If no direct edge exists, the entry is marked with a dash or infinity. This matrix is the starting point for Prim’s algorithm applied to a distance matrix and for Dijkstra’s algorithm.

距离矩阵是一个方阵，其中每个元素给出了直接连接两个顶点的边的权重。如果没有直接的边，则该位置用 ‘–‘ 或无穷大标记。这个矩阵是应用于距离矩阵的普里姆算法和迪杰斯特拉算法的起点。

In Edexcel exam questions, you will often see a distance table rather than a drawing of the graph, and you must be comfortable applying algorithms directly from this table.

在 Edexcel 的考题中，你常常会看到一个距离表而不是图的图示，你必须能够熟练地直接从这个表格出发应用算法。

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

A tree on n vertices always has exactly n – 1 edges. If any edge is added to a tree, a cycle is created. If any edge is removed from a tree, the graph becomes disconnected. These properties are often used in examinations to check the correctness of a spanning tree found by an algorithm.

具有 n 个顶点的树恰好有 n – 1 条边。如果给树添加任何一条边，就会形成一个回路。如果从树中删去任何一条边，图就会变得不连通。这些性质在考试中常被用来检查某算法找到的生成树是否正确。

A connected graph has at least one spanning tree. In a network with many vertices, the number of different spanning trees can be huge. Algorithms like Kruskal’s and Prim’s always find one spanning tree with the minimum total weight — the minimum spanning tree (MST).

一个连通图至少有一棵生成树。在顶点数较多的网络中，不同生成树的数目可能是巨大的。克鲁斯卡尔算法和普里姆算法总能够找到一棵总权重最小的生成树 —— 最小生成树 (MST)。

When a table of distances is used in Prim’s algorithm, the matrix should first be reduced by deleting the row and column of the chosen start vertex, and then repeating the process of selecting the smallest available entry from the remaining columns and merging rows. This is formally known as Prim’s algorithm on a distance matrix.

当在普里姆算法中使用距离表时，首先应删去已选初始顶点的行和列，然后重复从剩余列中选取最小可用条目并合并行的过程。这在形式上被称为基于距离矩阵的普里姆算法。

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

Kruskal’s algorithm builds a minimum spanning tree by considering edges in increasing order of weight. It is greedy: it always picks the cheapest available edge that does not form a cycle.

克鲁斯卡尔算法通过按权重递增的顺序考察边来构造最小生成树。它是一种贪心算法：总是选取不会形成回路的最便宜可用边。

Steps: 1) List all edges in ascending order of weight. 2) Starting with an empty set of edges, add the shortest edge that connects two different components (i.e., does not create a cycle). 3) Stop when n – 1 edges have been added, where n is the number of vertices.

步骤：1) 将所有边按权重升序排列。2) 从空的边集开始，加入那条连接两个不同分量的最短边（即不产生回路）。3) 当加入了 n – 1 条边时停止，其中 n 是顶点数。

It is essential to draw the graph or component connections at each stage to avoid cycles. Kruskal’s algorithm does not require a starting vertex and can easily be applied by sorting the edge list. If two edges have the same weight, the order of choosing does not affect the total weight of the MST.

在每一步都应该画出图或分量的连接情况以避免出现回路。克鲁斯卡尔算法不需要指定起始顶点，并且通过给边列表排序就能方便地应用。如果两条边权重相同，选择次序不会影响最小生成树的总权重。

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

Prim’s algorithm builds a minimum spanning tree by growing a tree from an arbitrary start vertex. At each step, it adds the smallest weight edge that connects a vertex already in the tree to a vertex outside the tree.

普里姆算法通过从任意起始顶点开始逐步生长一棵树来构造最小生成树。在每一步中，它加入一条权重最小的边，该边连接树内顶点与树外顶点。

When using a graph network: 1) Choose any vertex to start the tree. 2) Consider all edges joining the current tree to vertices not yet in the tree. Select the one with the smallest weight. 3) Add that edge and the corresponding vertex to the tree. Repeat until all vertices are included.

在基于网络图时：1) 选择任意顶点作为树的起始。2) 考察当前树与尚未包含在树中的顶点相连的所有边，选择权重最小的那条。3) 将该边和相应的顶点加入树中。重复直到所有顶点都被包含。

Using a distance matrix: 1) Cross out the row corresponding to the start vertex. Look down the column for that vertex and select the smallest weight. 2) Cross out the row of the newly added vertex, and then look down the columns for all vertices in the tree, select the smallest weight among the remaining entries. 3) Continue, merging rows as needed, until all vertices are in the tree. Record the order of selection and the edges.

基于距离矩阵时：1) 划掉起始顶点所在行，在该列的剩余数值中选取最小值。2) 划掉新加入顶点的行，然后查看树内所有顶点的列，在剩余条目中选择最小值。3) 继续执行，必要时合并行，直到所有顶点都被包含。记录边的选择顺序。

Algorithm	Approach	Starting Vertex	Cycle Checking
Kruskal	Sort edges, pick smallest non-cycle edge	Not required	Must explicitly avoid cycles
Prim (graph)	Grow tree from start, add nearest vertex	Any vertex	Automatically acyclic
Prim (matrix)	Cross out rows, select smallest column entry	Any vertex	Automatically acyclic

Both algorithms always produce an MST with the same total weight, but the edges chosen might differ if there are multiple edges with identical weights.

两种算法总能产生总权重相同的最小生成树，但如果有多条权重相同的边，所选出的边可能有所不同。

7. Dijkstra’s Algorithm for Shortest Path | 迪杰斯特拉最短路径算法

Dijkstra’s algorithm finds the shortest path from a designated start vertex to every other vertex in a weighted graph with non-negative edge weights. It uses permanent and temporary labels.

迪杰斯特拉算法用于在边权重非负的加权图中，找出从指定的起始顶点到所有其他顶点的最短路径。它使用永久性标号和临时性标号。

Box notation: Each vertex is represented with a box containing its final distance from start (permanent label), the working value (temporary), and a back-pointer. The algorithm proceeds by making the smallest temporary label permanent, then updating the working values of its neighbours.

盒子标注法：每个顶点用一个盒子表示，包含它距离起点的最终距离（永久标号）、当前工作值（临时标号）和回溯指针。算法通过将最小的临时标号设为永久标号，然后更新其邻居的工作值来进行。

Standard steps: 1) Label the start vertex with permanent 0 and give all other vertices temporary infinity ∞ (or a dash). 2) For the vertex just made permanent, consider all its neighbours with temporary labels. Compute the new distance = permanent distance + weight of edge. If this is less than the current working value, update the working value and the back-pointer. 3) Choose the vertex with the smallest temporary working value and make it permanent. Repeat until all vertices are permanently labelled, or until the target vertex is made permanent.

标准步骤：1) 给起始顶点标上永久标号 0，其他所有顶点标临时标号 ∞（或 ‘–‘）。2) 对于刚刚变为永久标号的顶点，考察它所有带有临时标号的邻居。计算新距离 = 永久距离 + 边的权重。如果该值小于当前工作值，则更新工作值和回溯指针。3) 选取临时工作值最小的顶点并将其变为永久标号。重复直到所有顶点都获得永久标号，或者目标顶点成为永久标号。

Dijkstra’s algorithm outputs both the length of the shortest path and the route by tracing back-pointers. It is crucial to write all working values clearly in examination to gain full marks.

迪杰斯特拉算法既输出最短路径的长度，也通过回溯指针给出具体路径。在考试中清晰地写出所有工作值是获得满分的关键。

8. Route Inspection (Chinese Postman Problem) | 路径检查（中国邮递员问题）

The Route Inspection Problem asks for the shortest closed walk that traverses every edge at least once. The solution involves Eulerian graphs. A graph is Eulerian if it contains a closed trail using every edge exactly once. This is possible if and only if all vertices have even degree.

路径检查问题（中国邮递员问题）要求找出一条遍历每条边至少一次的最短闭合回路。其解与欧拉图有关。如果一个图包含一条恰好使用每条边一次的闭合迹，则该图是欧拉图。当且仅当所有顶点的度都是偶数时，才有可能做到这一点。

If the original graph has vertices with odd degree, it is not Eulerian. To make it Eulerian, the shortest extra walks along existing paths between pairs of odd vertices must be added as duplicate edges. The extra distance is minimized by considering all possible pairings of odd vertices and selecting the pairing with the smallest total additional length. Use Dijkstra to find shortest paths between odd vertices if necessary.

如果原图中存在度数为奇数的顶点，那么它就不是欧拉图。为了使其变成欧拉图，需要将奇数度顶点两两配对，并沿着它们之间现有路径行走，添加重复边。通过考虑所有可能的奇数顶点配对方式，并选取总附加长度最小的配对，就能最小化额外距离。必要时使用迪杰斯特拉算法寻找奇数度顶点间的最短路径。

The total length of the optimal route is the total weight of all edges in the original graph plus the length of the minimum extra path duplication. In an exam, list the odd vertices, find all possible pairings, calculate the total extra distance for each, and choose the smallest. Then describe the route by specifying which edges are traversed twice.

最优路线的总长度等于原图所有边的总权重加上最小额外路径重复的长度。在考试中，列出所有奇数度顶点，找出所有可能的配对方式，计算每种方式的总额外距离，并选择最小的。然后通过指明哪些边被走了两次来描述整条路线。

9. Travelling Salesman Problem: Upper Bounds | 旅行商问题：上界

The Travelling Salesman Problem (TSP) seeks the shortest Hamiltonian cycle — a cycle that visits every vertex exactly once and returns to the start. Finding the exact optimum is difficult for large graphs, so we find upper and lower bounds.

旅行商问题 (TSP) 要求找出最短的哈密顿回路 —— 一条恰好访问每个顶点一次并返回起点的回路。对大规模的图而言，求精确最优解十分困难，因此我们转而寻找上界和下界。

An upper bound gives the length of a tour that is known to be possible. One simple method is the Nearest Neighbour algorithm: start at a chosen vertex, repeatedly go to the nearest unvisited vertex, and finally return to the start. This yields a valid tour whose length is an upper bound for the optimum.

上界给出了一个已知可行的行程长度。一种简单的方法是最近邻算法：从选定的顶点开始，不断去往最近的未访问顶点，最后返回起点。这样得到一条可行的旅程，其长度就是最优解的一个上界。

To find a good upper bound, you should apply the nearest neighbour algorithm from each possible starting vertex. The shortest of these obtained tours provides a better (smaller) upper bound. In Edexcel questions you normally state the tour and its length.

为了得到较好的上界，你应该从每一个可能的起始顶点出发运用最近邻算法。所得到的这些旅程中最短的那个就提供了一个更好（更小）的上界。在 Edexcel 考题中，你通常需要写出这条旅程及其长度。

Another method (not always examined) is to create a tour by doubling the edges of a minimum spanning tree, but nearest neighbour is the standard Edexcel technique for upper bounds.

另一种方法（并非必考）是通过将最小生成树的边加倍来构建旅程，但最近邻算法是 Edexcel 求解上界的标准技术。

10. Travelling Salesman Problem: Lower Bounds | 旅行商问题：下界

A lower bound provides a value that the optimum tour length cannot be less than. The most common method uses a minimum spanning tree after temporarily removing one vertex.

下界给出最优旅程长度不可能低于的一个数值。最常用的方法是暂时删除一个顶点后，利用最小生成树来求下界。

Procedure: 1) Choose a vertex to delete (often the one with highest sum of weights on incident edges). Remove it and all edges incident to it. 2) Find the minimum spanning tree (MST) of the remaining graph (using Kruskal or Prim). 3) Add the weights of the two shortest edges that connected the deleted vertex to the MST. This sum is a lower bound for the TSP.

步骤：1) 选择一个要删除的顶点（常选与其相连边的权重之和最大的那个）。删除该顶点及所有与其相连的边。2) 找出剩余图的最小生成树 (MST)（用克鲁斯卡尔或普里姆算法）。3) 加上被删除顶点与该 MST 相连的最短的两条边的权重。这个总和就是 TSP 的一个下界。

To get the best possible lower bound, you should repeat this process deleting each vertex in turn and take the maximum of the lower bounds obtained. The optimal tour length lies between this best lower bound and the smallest upper bound found earlier. The gap between them indicates the precision of your estimates.

为了得到可能的最优下界，你应该轮流删除每一个顶点重复上述过程，并取所得下界中的最大值。最优旅程长度就介于这个最佳下界与之前找到的最小上界之间。两者之间的差距反映了你的估计精度。

In examinations, clearly show your working for the MST after the vertex deletion, state which two edges are added, and present the final lower bound. The vertex deletion method is essential for establishing the range that contains the optimal solution.

在考试中，要清晰地展示删除顶点后求 MST 的过程，指明添加了哪两条边，并给出最终的下界。顶点删除法对于确定包含最优解的范围至关重要。

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

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

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