📚 Graph Theory Exam Essentials for A-Level CCEA Maths | A-Level CCEA 数学：图论 考点精讲
Graph theory forms a fundamental part of the CCEA A-Level Mathematics specification, bridging pure mathematical reasoning with real-world network problems. In this revision guide, we revisit the core definitions, classical theorems, and essential algorithms that candidates must master – from the Handshaking Lemma to Dijkstra's algorithm and the Travelling Salesman Problem.
图论是 CCEA A-Level 数学的重要组成部分，连接了纯数学推理与现实世界中的网络问题。在这篇复习指南中，我们将重新梳理考生必须掌握的核心定义、经典定理和基本算法——从握手引理到 Dijkstra 算法以及旅行商问题。
1. Graphs, Vertices and Edges | 图、顶点和边
tices (or nodes) and E is a set of edges connecting pairs of vertices. Each edge can be represented as an unordered pair {u, v} for an undirected graph, or as an ordered pair (u, v) for a directed graph (digraph).
图 G 被定义为有序对 G = (V, E)，其中 V 是一个有限的顶点（节点）集合，E 是连接顶点对的边集合。在无向图中，每条边可以表示为无序对 {u, v}；在有向图中，则表示为有序对 (u, v)。
The order of a graph is the number of vertices, |V|, and the size is the number of edges, |E|. A simple graph has no loops (edges connecting a vertex to itself) and no multiple edges between the same pair of vertices.
图的阶是指顶点的个数 |V|，大小是指边的条数 |E|。简单图不包含环（连接一个顶点自身的边），也不含同一对顶点之间的多重边。
2. Degree, Valency and the Handshaking Lemma | 度、价和握手引理
The degree (or valency) of a vertex v, denoted deg(v), is the number of edges incident with it – with loops counted twice. In a directed graph, we distinguish between the in-degree and out-degree of a vertex.
顶点 v 的度（或价）记作 deg(v)，表示与其关联的边的条数，环被计算两次。在有向图中，我们区分顶点的入度和出度。
A cornerstone result is the Handshaking Lemma: the sum of the degrees of all vertices equals twice the number of edges. It is expressed as:
一个基础性结论是握手引理：所有顶点度数之和等于边数的两倍。其数学表达式为：
∑v∈V deg(v) = 2|E|
An immediate corollary is that in any graph, the number of vertices with odd degree must be even. This property is frequently used when checking whether a graph possesses an Eulerian circuit or when solving the Chinese Postman Problem.
该引理的一个直接推论是：在任何图中，奇度顶点的个数必为偶数。这一性质在判断图是否具有欧拉回路或求解中国邮递员问题时经常用到。
3. Types of Graphs | 图的类型
A graph is called connected if there is a path between every pair of vertices. A complete graph Kn has n vertices with every pair joined by exactly one edge, giving n(n−1)/2 edges. A regular graph is one where every vertex has the same degree.
若图中任意两个顶点之间都存在一条路径，则称该图是连通的。完全图 Kn 有 n 个顶点，每对不同顶点之间恰好有一条边相连，总边数为 n(n−1)/2。正则图是指每个顶点的度数都相同的图。
A bipartite graph is a graph whose vertex set can be partitioned into two disjoint sets X and Y such that every edge connects a vertex in X to a vertex in Y. If a bipartite graph contains all possible edges between X and Y, it is a complete bipartite graph, denoted Km,n (where m = |X|, n = |Y|).
二分图是一种特殊的图，其顶点集合可以被划分成两个不相交的集合 X 和 Y，使得每条边都从 X 中的一个顶点连接到 Y 中的一个顶点。如果二分图包含了 X 和 Y 之间所有可能的边，则称为完全二分图，记作 Km,n（其中 m = |X|，n = |Y|）。
Trees are connected graphs with no cycles. A rooted tree has a designated root, from which all edges radiate. These structures appear frequently in network design and decision trees.
树是无环的连通图。一棵有根树指定一个根顶点，所有边从根向外辐射。这些结构经常出现在网络设计和决策树中。
4. Representing Graphs with Matrices | 用矩阵表示图
The adjacency matrix of a graph with n vertices is an n×n matrix A, where Aij and vertex j, and 0 otherwise. For weighted graphs, the entries store the weight of the edge instead of 1.
具有 n 个顶点的图的邻接矩阵是一个 n×n 矩阵 A，其中若顶点 i 与顶点 j 之间有边相连，则 Aij = 1，否则为 0。对于带权图，矩阵元素存储的是边的权重而非 1。
The distance matrix records the length of the shortest path (or 'distance' These matrix representations allow algorithms to be implemented efficiently on a computer.
距离矩阵记录了每对顶点之间最短路径的长度（“距离”）；若不存在路径，则对应项记为 ∞。这些矩阵表示使得算法能够在计算机上高效地实现。
5. Trees and Spanning Trees | 树与生成树
A tree on n vertices satisfies exactly n − 1 edges, and removing any edge disconnects the tree. Adding a single edge creates a unique cycle. These properties make trees the minimally connected graphs.
具有 n 个顶点的树恰好含有 n − 1 条边，删除任何一条边都会使树不连通；添加一条边则会产生唯一的环。这些性质使得树成为极小连通图。
A spanning tree of a connected graph G is a subgraph that includes all vertices of G and is a tree. Every connected graph contains at least one spanning tree. When edges carry weights, we often seek a minimum spanning tree (MST) – a spanning tree with the smallest total edge weight.
连通图 G 的生成树是包含 G 中所有顶点的一个树子图。每个连通图至少含有一棵生成树。当边带有权重时，我们通常寻找一棵最小生成树 (MST)，即总边权最小的生成树。
6. Minimum Spanning Trees: Kruskal's Algorithm | 最小生成树：Kruskal 算法
Kruskal's algorithm builds an MST by considering edges in increasing order of weight. Initially, each vertex is its own component. For each edge, if it connects two different components, the edge is added to the forest and the components are merged. The process stops after n − 1 edges have been selected.
Kruskal 算法通过按权重递增的顺序考虑边来构建 MST。最初，每个顶点自成一个连通分量。对于每条边，如果它连接两个不同的分量，就将该边加入森林并合并这两个分量。当选够 n − 1 条边后过程停止。
A typical exam question will provide a table of edges and ask you to list them in order, rejecting any that would form a cycle. A convenient way to check for cycles is to use a disjoint-set (union-find) data structure or simply draw the growing forest.
典型的试题会给出一个边表，要求按次序列出边，并拒绝那些会形成环的边。检查环的一个便捷方法是使用并查集结构，或者直接画出逐步生长的森林。
Example steps:
| Step | Edge | Weight | Action |
|---|---|---|---|
| 1 | AB | 4 | Add |
| 2 | CD | 5 | Add |
| 3 | BC | 6 | Add |
| 4 | AC | 7 | Reject (cycle) |
步骤示例：
| 步骤 | 边 | 权重 | 操作 |
|---|---|---|---|
| 1 | AB | 4 | 加入 |
| 2 | CD | 5 | 加入 |
| 3 | BC | 6 | 加入 |
| 4 | AC | 7 | 拒绝（构成环） |
7. Minimum Spanning Trees: Prim's Algorithm | 最小生成树：Prim 算法
Prim's algorithm grows an MST from an arbitrary starting vertex. At each iteration, it adds the least-weight edge that connects a vertex already in the tree to a vertex not yet in the tree. This is repeated until all vertices are included.
Prim 算法从任意一个起始顶点开始生长 MST。在每一次迭代中，它添加一条连接树内顶点与树外顶点的最小权重边。重复该过程直到所有顶点都被包含进来。
The algorithm can be executed using a priority queue or by maintaining a table of minimum connecting weights. Both Prim and Kruskal produce a minimum spanning tree, but Prim's is often easier to apply by hand on small, dense graphs.
该算法可以使用优先队列或通过维护最小连接权重表来执行。Prim 和 Kruskal 都能生成最小生成树，但在小型稠密图上手动操作时，Prim 算法通常更容易实施。
When recording your working, always state which edge you are adding and update the set of connected vertices. If multiple edges have the same minimum weight, any one can be chosen – this can lead to different but equally optimal MSTs.
在书写解题过程时，务必说明你正在添加哪条边，并更新已连接顶点的集合。如果有多条边具有相同的最小权重，可以任选一条——这可能导致不同但同等最优的 MST。
8. Shortest Path: Dijkstra's Algorithm | 最短路径：Dijkstra 算法
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It works by permanently labelling the vertex with the smallest tentative distance, then updating the labels of its neighbours.
Dijkstra 算法可在边权非负的带权图中求出从源点到所有其他顶点的最短路径。它通过永久标号具有最小临时距离的顶点，然后更新其邻居的标号来运作。
The standard notation uses a table with columns for vertex, order of labelling, final distance and working values. At each stage, you choose the unlabelled vertex with the smallest current working value and give it a permanent label.
标准的标记方式使用一个表格，包含顶点、标号次序、最终距离和临时值等列。每一步，选择当前临时值最小的未标号顶点，赋予其永久标号。
A key point for CCEA exams is that you must show all working values clearly, typically by listing intermediate distances crossed out. The algorithm stops when the destination vertex receives a permanent label, or when all vertices are labelled.
CCEA 考试的一个关键是必须清晰展示所有临时值，通常列出被划掉的中间距离。当目标顶点获得永久标号或所有顶点都被标号时，算法终止。
9. Eulerian Graphs and the Chinese Postman Problem | 欧拉图与中国邮递员问题
An Eulerian trail is a walk that traverses every edge of a graph exactly once. If the trail 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 Chinese Postman Problem asks: given a connected weighted graph, find the shortest closed walk that traverses every edge at least once and returns to the start. If the graph is Eulerian, the optimal route is simply an Eulerian circuit. Otherwise, we must duplicate certain edges to make all vertex degrees even. The problem reduces to pairing the odd-degree vertices in a way that minimises the total length of the added paths.
中国邮递员问题要求：给定一个连通的带权图，找出遍历每条边至少一次并返回起点的最短闭合行走路线。如果该图是欧拉图，则最优路线就是欧拉回路。否则，我们必须复制某些边使得所有顶点的度数变为偶数。该问题归结为以总增加路径长度最小的方式将奇度顶点配对。
When shaping an answer, list the odd vertices, find all pairings with their associated shortest-path distances, and select the combination with the smallest total. The final route length equals the sum of all original edge weights plus the total length of the duplicated edges.
在组织答案时，列出所有奇度顶点，找出所有可能的配对及其对应的最短路径距离，并选择总距离最小的组合。最终路线长度等于原图所有权重之和加上所复制边的总长度。
10. Hamiltonian Graphs and the Travelling Salesman Problem | 哈密顿图与旅行商问题
A Hamiltonian cycle (or circuit) visits every vertex of a graph exactly once before returning to the start. Unlike Eulerian circuits, there is no simple necessary and sufficient condition for a graph to be Hamiltonian – questions usually ask you to find a Hamiltonian cycle by inspection or to explain why one does not exist.
哈密顿回路（或环游）访问图中的每个顶点恰好一次并返回起点。与欧拉回路不同，判断一个图是否具有哈密顿回路没有简单而充要的条件——考题通常要求通过观察找出一个哈密顿回路，或者解释它不存在的原因。
The Travelling Salesman Problem (TSP) seeks a minimum-weight Hamiltonian cycle in a complete weighted graph. Since TSP is NP-hard, A-Level candidates are expected to find upper and lower bounds for
Published by TutorHao | A-Level Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图