📚 A-Level WJEC Mathematics: Graph Theory Revision Guide | 图论考点精讲
Graph theory forms the backbone of decision mathematics in the WJEC A-Level specification. It equips you with the tools to model relationships, optimise routes and solve classic problems like finding the shortest path between two points or the cheapest way to connect a network. This guide breaks down every key concept, algorithm and exam technique you need to master.
图论是 WJEC A-Level 决策数学的核心支柱。它提供的工具能帮助你模拟关系、优化路径，并解决诸如寻找两点间最短路径或用最低成本连接网络等经典问题。这份指南将逐一拆解你需要掌握的每个关键概念、算法和应试技巧。
1. Basic Graph Terminology | 图的基本术语
A graph G consists of a set of vertices V (also called nodes) and a set of edges E that connect pairs of vertices. The order of a graph is the number of vertices |V|, and the size is the number of edges |E|. A loop is an edge that starts and ends at the same vertex.
图 G 由顶点集合 V（也称节点）和连接顶点对的边集合 E 组成。图的阶是顶点数 |V|，大小是边数 |E|。自环是一条起点和终点为同一顶点的边。
The degree of a vertex is the number of edges incident to it, with each loop counting as 2. The handshaking lemma states that the sum of all vertex degrees equals twice the number of edges. This holds because each edge contributes 2 to the total degree count.
顶点的度是与该顶点关联的边数，每个自环计为 2。握手引理指出，所有顶点度数之和等于边数的两倍。这是因为每条边为总度数贡献 2。
∑ d(v) = 2|E|
A graph is called simple if it has no loops and no multiple edges between the same pair of vertices. A subgraph is formed by selecting a subset of the original vertices and edges.
如果一个图没有自环且同一顶点对之间没有多条边，则称为简单图。子图通过选择原始顶点和边的子集构成。
2. Types of Graphs | 图的类型
Graphs in WJEC Decision Maths appear in several forms. A simple graph, as defined above, is the most common. A complete graph on n vertices, denoted Kₙ, has every vertex connected to every other vertex exactly once. In Kₙ, the number of edges is n(n−1)/2.
WJEC 决策数学中出现的图有多种形式。简单图如上定义，最为常见。n 个顶点的完全图记作 Kₙ，其中每个顶点都与其余每个顶点恰好连接一次。Kₙ 的边数为 n(n−1)/2。
A bipartite graph has its vertex set split into two disjoint sets X and Y such that every edge goes between X and Y — there are no edges within X or within Y. A complete bipartite graph Km,n has all possible edges between a set of size m and a set of size n, giving m × n edges.
二部图的顶点集被划分为两个互不相交的集合 X 和 Y，每条边都连接 X 与 Y 之间——X 内部或 Y 内部没有边。完全二部图 Km,n 在大小为 m 和大小为 n 的两个集合之间包含所有可能的边，边数为 m × n。
Weighted graphs assign a numerical value (weight) to each edge, representing cost, distance or time. Directed graphs, or digraphs, have edges with a direction, shown by arrows. A mixed graph contains both directed and undirected edges.
加权图为每条边赋予一个数值（权重），表示成本、距离或时间。有向图（或称有向图）的边带有方向，用箭头表示。混合图同时包含有向边和无向边。
3. Representing Graphs using Matrices | 用矩阵表示图
es are directly connected. For a graph with n vertices, A is an n × n matrix where the entry aij equals 1 if vertex i is joined to vertex j, and 0 otherwise. For a simple graph the matrix is symmetric.
考试中两种矩阵表示至关重要：邻接矩阵和距离矩阵。邻接矩阵 A 记录哪些顶点直接相连。对于有 n 个顶点的图，A 是 n × n 矩阵，若顶点 i 与顶点 j 相连则元素 aij 等于 1，否则为 0。对于简单图该矩阵是对称的。
o direct connection exists. The diagonal entries are typically 0. This matrix is the foundation for Dijkstra's shortest path algorithm.
距离矩阵给出每条直接边的权重，当不存在直接连接时元素用 ∞（或一个非常大的数）代替。对角线元素通常为 0。这个矩阵是 Dijkstra 最短路径算法的基础。
4. Trees and Spanning Trees | 树与生成树
A tree is a connected graph that contains no cycles. For a tree with n vertices, there are exactly n−1 edges. Adding any extra edge would create a cycle, while removing any edge would disconnect the graph. In decision problems, trees often represent the minimum structure needed to connect a set of points without redundancy.
树是无环的连通图。一棵有 n 个顶点的树恰好有 n−1 条边。增加任何一条额外的边都会产生一个圈，而移除任何一条边都会使图不再连通。在决策问题中，树通常表示连接一组点所需的最少结构且没有冗余。
A spanning tree of a graph G is a subgraph that includes all the vertices of G and is itself a tree. Every connected graph has at least one spanning tree. In a weighted graph, the minimum spanning tree (MST) is the spanning tree with the smallest possible total edge weight.
图 G 的生成树是包含 G 的所有顶点且自身是一棵树的子图。每个连通图至少有一棵生成树。在加权图中，最小生成树（MST）是总边权重尽可能小的生成树。
5. Minimum Spanning Trees: Kruskal's Algorithm | 最小生成树：Kruskal 算法
Kruskal's algorithm builds an MST by repeatedly adding the cheapest remaining edge that does not form a cycle. Start with an empty edge list, sort all edges in ascending order of weight, and step through them. Add an edge if its two endpoints are not already connected by edges already chosen. Stop when n−1 edges are selected.
Kruskal 算法通过反复添加不会形成圈的最便宜剩余边来构建 MST。从空的边列表开始，将所有边按权重升序排列，然后逐一检查。如果某条边的两个端点尚未被已选边连接，则添加该边。当选出 n−1 条边时停止。
This approach is efficient because you only need to keep track of which vertices are linked. In an exam, clearly list edges in order of weight and show the growing forest. Use a connectivity table or simply draw partial graphs to justify each addition.
这种方法很高效，因为只需跟踪哪些顶点已相连。在考试中，明确按权重顺序列出边，并展示不断成长的森林。可以使用连通表或直接绘制部分图来说明每次添加的理由。
6. Minimum Spanning Trees: Prim's Algorithm | 最小生成树：Prim 算法
Prim's algorithm grows an MST from a starting vertex. Choose any vertex as the initial tree, and repeatedly add the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree. Continue until all vertices are included. Prim is especially convenient when the graph is dense or when you are given a distance matrix.
Prim 算法从一个起始顶点出发逐步生长 MST。选择任意顶点作为初始树，并反复添加连接树内顶点与树外顶点的最便宜边。持续进行直到所有顶点都被包含。当图较稠密或给定距离矩阵时，Prim 尤为方便。
Using a distance matrix, you can set up a table with rows for each vertex and columns for 'selected', 'reachable minimum weight' and 'previous vertex'. At each step, select the unreached vertex with the smallest entry, update the distances to its neighbours, and record the edge that achieved that minimum.
使用距离矩阵时，可以建立一个表格，包括每个顶点的行以及列标示“已选”、“可达最小权重”和“前驱顶点”。每一步选出未达顶点中条目最小的那个，更新至其邻居的距离，并记录实现该最小值的边。
7. Shortest Path Problems: Dijkstra's Algorithm | 最短路径问题：Dijkstra 算法
Dijkstra' rom a source vertex S to all other vertices in a weighted graph without negative edges. It works by assigning each vertex a working value — tices are visited in order of increasing working value; at each step, the values of its unvisited neighbours are updated if a shorter path is found via the current vertex.
Dijkstra 算法在无边权为负的加权图中寻找从源点 S 到所有其他顶点的最短路径。它为每个顶点赋予一个临时值——初始时 S 为 0，其他为 ∞。顶点按照临时值递增的顺序被访问；每一步，若通过当前顶点找到更短路径，则更新其未访问邻居的临时值。
In an exam, show your working by creating a table that tracks the shortest distance and the route from S to each vertex. Box in the permanent values as vertices become fully labelled. The final columns give both the shortest distance and the preceding vertex, enabling you to trace back the optimal route.
在考试中，通过创建一个表格来展示解题过程，该表格追踪从 S 到每个顶点的最短距离和路径。当顶点获得永久标号时，将其值框起来。最后的列既给出最短距离也给出前驱顶点，使你能够回溯最优路线。
8. Eulerian Graphs and the Route Inspection Problem | 欧拉图与中国邮递员问题
An Eulerian trail is a route that traverses every edge of a graph exactly once. If the trail starts and ends at the same vertex, it is an Eulerian circuit. A connected graph has an Eulerian circuit if and only if every vertex has an even degree. It has an Eulerian trail (but no circuit) if exactly two vertices have odd degree; the trail must start at one odd vertex and end at the other.
欧拉路径是一条恰好遍历图中每条边一次的路线。若该路径起点与终点重合，则称为欧拉回路。一个连通图存在欧拉回路当且仅当每个顶点度数均为偶数。若恰有两个顶点度数为奇数，则存在欧拉路径（但无回路）；该路径必须以一个奇度顶点为起点，以另一个为终点。
The Route Inspection Problem (Chinese Postman Problem) asks for the shortest closed walk that covers every edge at least once. If the original graph is Eulerian, the optimal route is simply an Eulerian circuit with total weight equal to the sum of all edge weights. If odd-degree vertices exist, you need to find the cheapest pairing of these vertices and duplicate the edges on those paths, effectively adding extra edges to make the graph Eulerian.
中国邮递员问题要求找出一条覆盖每条边至少一次的最短闭合行走。若原图是欧拉图，最优路线就是一条欧拉回路，总权重等于所有边权之和。若存在奇度顶点，则需要找出这些顶点的最便宜配对并在那些路径上复制边，即通过添加额外边使图成为欧拉图。
To solve it: list the odd vertices, find minimum weight paths between every pair (using Dijkstra or repeated application), then select the pairing with the smallest total added weight. Add these pairing edges as duplicates and then find an Eulerian circuit on the augmented graph.
解决方法：列出奇度顶点，找出每对之间的最短路径（用 Dijkstra 或反复应用），然后选择总添加权重最小的配对。将这些配对边作为重复边加入，再在增广图上寻找欧拉回路。
9. Hamiltonian Graphs and the Travelling Salesman Problem | 哈密顿图与旅行商问题
A Hamiltonian cycle (or circuit) visits every vertex exactly once and returns to the start. Unlike Eulerian circuits, there is no simple necessary-and-sufficient condition for a graph to have a Hamiltonian cycle, making these problems much harder computationally. In the Travelling Salesman Problem (TSP), we seek the minimum-weight Hamiltonian cycle in a weighted complete graph.
哈密顿圈（或回路）恰好访问每个顶点一次并返回起点。与欧拉回路不同，判断图是否存在哈密顿圈没有简单的充要条件，因此这类问题的计算难度要大得多。在旅行商问题（TSP）中，我们需要在加权完全图中寻找最小权哈密顿圈。
For practical sized problems in WJEC, you are often required to find an upper bound using heuristic methods and a lower bound by deleting a vertex and finding the MST of the remaining graph. The optimal tour weight lies between the lower bound and the upper bound.
对于 WJEC 中实际问题规模，通常要求使用启发式方法找到上界，并通过删除一个顶点并求剩余图的 MST 来求下界。最优巡回路权重介于该下界与上界之间。
10. Heuristic Methods for TSP | 旅行商问题的启发式算法
The nearest neighbour algorithm builds a tour by starting at any vertex and repeatedly going to the closest unvisited vertex, finally returning to the start. This gives a valid upper bound but not necessarily the optimum. The result depends on the starting vertex; you may be asked to apply it from a specified vertex and state the tour found.
最近邻算法通过从任意顶点出发并反复前往最近的未访问顶点，最终返回起点来构建巡回路。这给出了一个有效的上界但不一定是最优的。结果依赖于起始顶点；你可能需要从指定顶点出发并给出找到的巡回路。
To find a lower bound, delete a vertex (say A) and all edges incident to it. Compute the MST of the remaining graph using Kruskal or Prim. Then add the two shortest edges from A to any other vertices. This total is a lower bound for the optimal tour. A practical approach is to compute several such lower bounds by deleting different vertices and take the highest, because the optimal tour weight must be at least as large as each bound.
为求下界，删除一个顶点（例如 A）及所有与其关联的边。用 Kruskal 或 Prim 求剩余图的 MST，然后加上从 A 到其他顶点的两条最短边。这个总和是最优巡回路的一个下界。实用方法是删除不同顶点计算多个下界并取最大值，因为最优巡回路权重必须至少与每个下界一样大。
Other heuristics like the farthest insertion method can provide better bounds, but nearest neighbour and the vertex-deletion lower bound are the standard tools tested at A-Level. Remember to state clearly that an optimal solution lies between your lower and upper bounds.
其他启发式算法如最远插入法可以提供更好的界，但最近邻和顶点删除下界是 A-Level 中测试的标准工具。记得明确指出最优解介于所求下界与上界之间。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图