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

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

Graph theory forms a central pillar of Edexcel Decision Mathematics, equipping students with powerful tools to model networks, optimise routes, and analyse connectivity. In this revision guide, we distil the fundamental concepts, standard algorithms, and typical exam techniques you need for success. From handshaking lemma to travelling salesman bounds, each section is presented in a clear, paired English–Chinese format to reinforce understanding.

图论是Edexcel决策数学的核心支柱，为学生提供了建模网络、优化路径和分析连通性的强大工具。在这篇复习指南中，我们提炼了取得成功所需的基本概念、标准算法和典型考试技巧。从握手引理到旅行商问题界限，每个部分都以清晰的中英对照形式呈现，以加深理解。

1. Basic Graph Terminology | 图论基本术语

A graph G consists of a set of vertices V (nodes) and a set of edges E (connections). Edges can be undirected or directed (digraph). A simple graph has no loops and no multiple edges between the same pair of vertices. A network is a weighted graph where each edge carries a numerical value such as distance, time or cost. The order of a graph is |V| and the size is |E|.

图 G 由一组顶点 V（节点）和一组边 E（连线）组成。边可以是无向的或有向的（有向图）。简单图没有自环，且同一对顶点之间没有多重边。网络是带权值的图，每条边赋有一个数值，如距离、时间或费用。图的阶为 |V|，大小为 |E|。

A walk is a sequence of edges; a trail uses no repeated edges; a path uses no repeated vertices. A cycle (circuit) is a closed path that starts and ends at the same vertex. A graph is connected if a path exists between every pair of vertices.

路径是边的序列；迹不重复边；路径不重复顶点。回路（环）是起点和终点重合的封闭路径。若任意两顶点间都存在路径，则图是连通的。

2. Handshaking Lemma and Degree | 握手引理与度数

The degree of a vertex, deg(v), is the number of edges incident to it, with loops counted twice. The handshaking lemma states that the sum of all vertex degrees equals twice the number of edges: Σdeg(v) = 2|E|. This result implies that the number of vertices with odd degree is always even.

顶点的度数 deg(v) 是与该顶点关联的边数（自环计两次）。握手引理指出，所有顶点度数之和等于边数的两倍：Σdeg(v) = 2|E|。由此可得，具有奇度数的顶点个数总是偶数。

A degree sequence lists the degrees in non‑increasing order. To check whether a sequence can correspond to a simple graph, apply the Erdős–Gallai theorem or the quicker ‘pairing check’ using the handshaking lemma and the fact that no vertex degree can exceed n−1.

度序列按非增序列出度数。要检验一个序列是否能对应某个简单图，可运用 Erdős–Gallai 定理或更快捷的“配对检验”，依据握手引理及任一顶点度数不超过 n−1 的事实。

3. Special Graphs: Trees, Complete and Bipartite | 特殊图：树、完全图和二分图

A tree is a connected graph with no cycles. A tree on n vertices always has exactly n−1 edges, and any spanning tree of a connected graph uses a subset of edges that connects all vertices without cycles. A forest is a disjoint union of trees.

树是无回路的连通图。有 n 个顶点的树一定恰有 n−1 条边；连通图的任何生成树都是连接所有顶点且无回路的边子集。森林是树的非连通并集。

The complete graph Kₙ has n vertices and every pair of distinct vertices is joined by exactly one edge, giving n(n−1)/2 edges. A bipartite graph partitions vertices into two disjoint sets such that every edge joins a vertex of one set to a vertex of the other; it contains no odd cycles. The complete bipartite graph Kₘ,ₙ has all possible edges between the two sets.

完全图 Kₙ 有 n 个顶点，且每对不同顶点之间恰有一条边，边数为 n(n−1)/2。二分图将顶点分为两个不相交的集合，每条边都连接一个集合的顶点与另一集合的顶点；它不含奇回路。完全二分图 Kₘ,ₙ 包含两集合之间所有可能的边。

4. Representing Graphs: Adjacency and Distance Matrices | 图的表示：邻接矩阵与距离矩阵

An adjacency matrix A for a graph with n vertices is an n × n matrix where the entry aᵢⱼ equals the number of edges between vertex i and j. For simple undirected graphs, A is symmetric and the diagonal entries are 0. For a weighted network, we often replace 1 with weight values to create a weight matrix.

n 个顶点的图的邻接矩阵 A 是一个 n × n 矩阵，其中元素 aᵢⱼ 等于顶点 i 与 j 之间的边数。对于简单无向图，A 是对称的且对角线元素为 0。对于加权网络，常用权重值取代 1 来生成权重矩阵。

A distance matrix D gives the shortest distance between every pair of vertices; entries may be set to ∞ where no path exists. Distance matrices are essential for applying Prim’s and Dijkstra’s algorithms in tabular form. Always state which matrix you are using and whether it is symmetric.

距离矩阵 D 给出每对顶点之间的最短距离；若无路径，则设为 ∞。距离矩阵对于以表格形式执行 Prim 算法和 Dijkstra 算法至关重要。始终要说明使用的是哪个矩阵以及它是否对称。

5. Minimum Spanning Trees: Kruskal’s Algorithm | 最小生成树：Kruskal 算法

A minimum spanning tree (MST) connects all vertices with the smallest total edge weight. Kruskal’s algorithm works as follows:

最小生成树（MST）以最小的总边权连接所有顶点。Kruskal 算法步骤如下：

List all edges in ascending order of weight.
Select the edge with the smallest weight that does not form a cycle.
Repeat until exactly n−1 edges have been chosen.

步骤如下：

按权重升序列出所有边。
选择权重最小且不构成回路的边。
重复直到恰好选出 n−1 条边。

Always draw the growing forest or use a union‑find table to track connectivity. Kruskal’s algorithm is useful when the graph is sparse or when edges are presented in a list.

始终画出不断增长的森林或使用并查集表来追踪连通性。当图为稀疏图或边以列表形式给出时，Kruskal 算法很有用。

6. Minimum Spanning Trees: Prim’s Algorithm | 最小生成树：Prim 算法

Prim’s algorithm builds the MST from a start vertex, growing a connected tree. Using a distance matrix or a network diagram:

Prim 算法从一个起始顶点开始构建最小生成树，通过扩展连通树。利用距离矩阵或网络图：

From the starting vertex, choose the edge of least weight that connects a vertex already in the tree to a vertex not yet in the tree.
Add that vertex and edge. Repeat until all vertices are included.
When using a matrix, after selecting a vertex, delete its row and mark its column for future scanning.

步骤如下：

从起始顶点出发，选择权重最小的边，该边连接已在树中的顶点与未在树中的顶点。
将该顶点及边加入。重复直到所有顶点都包含在内。
使用矩阵时，选定顶点后，删除其所在行并将其列标记，以供后续扫描。

Prim’s algorithm is efficient for dense networks and matrix representation. Both Prim and Kruskal always yield the same total weight, though the tree may differ if edges have equal weights.

Prim 算法对稠密网络和矩阵表示效率较高。Prim 和 Kruskal 总能得到相同的总权重，但若存在等权重边，生成的树可能不同。

7. Shortest Path: Dijkstra’s Algorithm | 最短路径：Dijkstra 算法

Dijkstra’s algorithm finds the shortest path from a given source vertex to every other vertex in a network with non‑negative weights. It uses a working‑box method, assigning temporary and permanent labels.

Dijkstra 算法在权重非负的网络中求从指定源点到其他所有顶点的最短路径。它使用工作框方法，赋予临时和永久标签。

The procedure:

Label the start vertex with permanent label 0 and all others with temporary label ∞.
From the most recently made permanent vertex, update temporary labels of its unvisited neighbours as: current temporary = min(old temporary, permanent + weight).
Make the smallest temporary label permanent, and repeat until all vertices are permanent.
Trace back from the target vertex to find the path.

步骤：

给起始顶点赋予永久标签 0，其他顶点赋予临时标签 ∞。
从最新成为永久的顶点出发，更新其未访问邻居的临时标签：当前临时值 = min（旧临时值，永久值 + 权重）。
使最小的临时标签成为永久，重复直至所有顶点均为永久。
从目标顶点逆向回溯以找出路径。

Always present your working as a neat table showing each vertex, the order in which labels are made permanent, the permanent value and the final path. The final permanent values give shortest distances, but do not forget to state the path explicitly.

务必以整洁的表格展示过程，列出每个顶点、标签永久化的顺序、永久值及最终路径。最终永久值即为最短距离，但不要忘记明确写出路径。

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

The route inspection problem requires finding a closed walk that traverses every edge at least once with minimum total length. If the graph is Eulerian (all vertices even degree), the optimal route is any Eulerian trail and its length equals the sum of all edge weights.

路线检查问题要求找出一条遍历每条边至少一次并返回起点的最短闭迹。若图是欧拉图（所有顶点度数为偶），则最优路线为任一欧拉迹，其长度等于所有边权重之和。

If there are odd‑degree vertices (the number is even by the handshaking lemma), you must duplicate edges to make all degrees even. The procedure is:

Identify all odd‑degree vertices.
Form all possible pairings of odd vertices and, for each pairing, find the shortest paths between the paired vertices; sum their lengths.
Choose the pairing that gives the smallest total added weight. Duplicate those paths.
The optimal route now has total weight = sum of original edges + duplicated lengths.

若存在奇度顶点（由握手引理知其个数为偶），则必须复制边以将所有度数变为偶数。步骤如下：

找出所有奇度顶点。
列出奇度顶点的所有可能配对，并对每种配对求出配对顶点间的最短路径长度之和。
选择总复制权重最小的配对。复制这些路径上的边。
最优路线的总权重 = 原边权和 + 复制的长度。

You may be asked to state a route or just the least total length. Clearly list duplicated edges and verify that after duplication every vertex has even degree.

考题可能要求写出具体路线或仅求最短总长度。清晰地列出复制的边，并验证复制后每个顶点度数均为偶数。

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

The travelling salesman problem (TSP) seeks a minimum‑weight Hamiltonian cycle (tour) visiting every vertex exactly once and returning to the start. Finding the exact optimum is hard, so we generate upper and lower bounds. The optimum lies between them.

旅行商问题（TSP）寻求一条最小权重的哈密顿回路（游览），恰好访问每个顶点一次并返回起点。求精确最优解较为困难，因此我们生成上界和下界。最优值介于二者之间。

To find an upper bound, use the nearest neighbour algorithm:

Start at any vertex.
Repeatedly move to the nearest unvisited vertex.
When all vertices are visited, return directly to the start.
The total weight of this tour gives one upper bound. Repeat from different start vertices and select the smallest value as the best upper bound.

为求上界，可使用最近邻算法：

从任一顶点出发。
反复移动到最近的未访问顶点。
访问完所有顶点后直接返回起点。
该游览的总权重即为一个上界。从不同起点重复此过程，选择最小值作为最佳上界。

Sometimes you can improve the bound by edge‑crossing removal or by using an alternative heuristic like the tour‑improvement algorithm. Always clearly state your tour and its weight.

有时可以通过消除交叉边或使用其他启发式方法（如游览改进算法）来优化上界。始终要明确写出你的游览顺序和权重。

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

A good lower bound for the TSP is obtained by using a method based on minimum spanning trees. The approach:

Delete one vertex (say A) and all edges incident to it.
Find a minimum spanning tree for the remaining network.
Add back the two shortest edges from the deleted vertex to this tree.
The total weight is a lower bound from removing A. Repeat this for each possible vertex and take the greatest of these lower bounds as the final lower bound.

TSP 的一个优质下界可以通过基于最小生成树的方法求得。步骤如下：

删去某个顶点（例如 A）以及与之关联的所有边。
求出剩余网络的最小生成树。
将删去顶点与该生成树相连的两条最短边加回。
该总权重即为删除 A 时得到的下界。对每个可能的顶点重复此操作，取所有下界中的最大值作为最终下界。

Always justify your choice of greatest lower bound. If the upper and lower bound are equal, you have found the optimal tour. In exams, you are often asked to write the optimal interval: Lower bound ≤ optimal ≤ Upper bound.

始终要论证为何选取最大下界。若上界与下界相等，则已找到最优游览。考试中常要求写出最优区间：下界 ≤ 最优值 ≤ 上界。

The MST method produces a valid lower bound because any optimal tour must contain a spanning tree on n−1 vertices when one vertex and its incident edges are removed, and it must reconnect that vertex with at least two edges – hence the construction.

MST 方法之所以产生有效下界，是因为移除一个顶点及其关联边后，任何最优游览必定包含剩余 n−1 个顶点的一个生成树，并且必须用至少两条边重新连接该顶点——由此得出构造。

Published by TutorHao | Mathematics Revision Series | aleveler.com

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

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