📚 Graph Theory in A-Level CIE Mathematics: Key Concepts and Exam Focus | A-Level CIE 数学：图论考点精讲
Graph theory is a fascinating branch of discrete mathematics included in CIE A-Level Mathematics (Decision track). It equips students with powerful tools to model and solve real-world problems involving networks, routes, and connections. Understanding key concepts such as graphs, trees, spanning trees, shortest paths, and the Chinese postman problem is essential for achieving top marks in the examination.
图论是离散数学中一个引人入胜的分支，属于 CIE A-Level 数学（决策分卷）的考查内容。它为学生提供了强大的工具来建模并解决涉及网络、路径和连接的实际问题。掌握图、树、生成树、最短路径和中国邮递员问题等核心概念，是在考试中取得高分的关键。
1. Graphs and Terminology | 图与术语
A graph consists of vertices (nodes) and edges (arcs) that connect pairs of vertices. The degree of a vertex is the number of edges incident to it. A loop is an edge that starts and ends at the same vertex, while multiple edges between the same pair of vertices are called parallel edges.
图由顶点（节点）和连接顶点对的边（弧）组成。顶点的度是指与该顶点相连的边的数目。环是一条起点和终点为同一顶点的边，而同对顶点之间的多条边则称为平行边。
In a simple graph, there are no loops and no parallel edges. A graph can be directed (edges have a direction) or undirected (edges have no direction). Weighted graphs assign a numerical value, or weight, to each edge, often representing distance, time, or cost.
在简单图中，不存在环和平行边。图可以是有向的（边有方向）或无向的（边无方向）。加权图为每条边赋予一个数值（即权重），通常表示距离、时间或成本。
2. Types of Graphs | 图的类型
A connected graph is one in which there is a path between every pair of vertices. If a graph is not connected, it consists of several connected components. A complete graph, denoted Kₙ, is a simple graph in which every pair of distinct vertices is connected by a unique edge. For example, K₅ has 5 vertices and each vertex has degree 4.
连通图是指任意两个顶点之间都存在一条路径的图。如果图不连通，则它包含多个连通分量。完全图记作 Kₙ，是一种简单图，其中每对不同的顶点都由唯一的一条边相连。例如，K₅ 有 5 个顶点，每个顶点的度为 4。
A bipartite graph is one 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. A tree is a connected graph with no cycles, which we will explore in detail later.
二分图是指其顶点集可以划分为两个不相交的集合 X 和 Y，使得每条边都连接 X 中的一个顶点和 Y 中的一个顶点。树是一种无环的连通图，我们将在后面详细探讨。
3. Paths and Cycles | 路径与回路
A path is a sequence of vertices where each adjacent pair is connected by an edge, and no vertex is repeated. A cycle (or circuit) is a closed path in which the start and end vertices are the same, and no other vertex is visited more than once. The length of a path or cycle is the number of edges it contains.
路径是一个顶点序列，其中每一对相邻顶点都由一条边连接，且没有顶点重复出现。回路（或圈）是一条闭合路径，起点和终点相同，且其他顶点均不重复经过。路径或回路的长度是指它所包含的边的数目。
In a weighted graph, the total weight of a path is the sum of the weights of its edges. An Eulerian trail passes along every edge of a graph exactly once, and an Eulerian circuit is an Eulerian trail that starts and ends at the same vertex. A graph has an Eulerian circuit if and only if it is connected and every vertex has an even degree.
在加权图中，一条路径的总权重是其各边权重之和。欧拉迹是恰好经过图中每条边一次的轨迹，欧拉回路是起点和终点相同的欧拉迹。一个图存在欧拉回路当且仅当它是连通的且每个顶点的度均为偶数。
4. Trees and Spanning Trees | 树与生成树
A tree is a connected undirected graph with no cycles. For a tree with n vertices, there are exactly n – 1 edges. Removing any edge from a tree disconnects it, and adding any edge creates a cycle. Trees are fundamental in modelling hierarchical structures and efficient networks.
树是一种无环的连通无向图。对于有 n 个顶点的树，恰好有 n – 1 条边。从树中移除任意一条边都会使它不连通，而添加任意一条边则会形成一个圈。树在层次结构和高效网络建模中起着基础性作用。
A spanning tree of a connected graph G is a subgraph that includes all the vertices of G and is a tree. In a weighted graph, a minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. Finding the MST is a classic problem, with Kruskal’s and Prim’s algorithms being the two principal methods required in the CIE syllabus.
连通图 G 的生成树是包含 G 的所有顶点且本身为树的一个子图。在加权图中，最小生成树是指总边权尽可能小的一棵生成树。寻找最小生成树是一个经典问题，CIE 考纲要求掌握两种主要方法——Kruskal 算法和 Prim 算法。
5. Kruskal’s Algorithm | Kruskal 算法
Kruskal’s algorithm builds a minimum spanning tree by considering edges in increasing order of weight. Start by sorting all edges by weight. Then inspect each edge in turn: if adding the edge does not create a cycle, include it in the MST; otherwise, discard it. Stop when n – 1 edges have been selected (where n is the number of vertices).
Kruskal 算法通过按权重递增的顺序考虑边来构建最小生成树。首先将所有边按权重排序，然后依次检查每条边：如果加入该边不会形成圈，则将其纳入最小生成树；否则丢弃。当已选择 n – 1 条边（n 为顶点数）时停止。
Use a table or list to record selected edges and their cumulative weight. It is helpful to draw the partial tree to check for cycles. Kruskal’s algorithm is efficient for sparse graphs and is straightforward to apply by hand in exam problems.
可使用表格或列表记录已选边及其累计权重。绘制部分树的草图有助于检查是否形成圈。Kruskal 算法对于稀疏图效率较高，并且在考试题目中很容易手工操作。
6. Prim’s Algorithm | Prim 算法
Prim’s algorithm grows a minimum spanning tree from a starting vertex. Begin with any vertex, then repeatedly add the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree, without forming cycles. Continue until all vertices are included.
Prim 算法从某个起始顶点出发逐步生长出最小生成树。首先任选一个顶点，然后反复加入连接树内顶点与树外顶点的最便宜的边，且不得形成圈。持续此过程直至所有顶点都被包含。
Using a table with columns for ‘selected’ or ‘not selected’ and tracking the minimum distance to the current tree helps to avoid errors. Although the choice of starting vertex can affect the order of edge selection, the final minimum total weight is the same as with Kruskal’s algorithm.
使用表格标记“已选”或“未选”，并记录到当前树的最小距离，有助于避免错误。虽然起点的选择会影响边的选取顺序，但最终的最小总权重与 Kruskal 算法得到的结果相同。
7. Dijkstra’s Algorithm for Shortest Path | Dijkstra 最短路径算法
Dijkstra’s algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It works by iteratively selecting the unvisited vertex with the smallest tentative distance, updating the distances to its neighbors, and marking it as visited.
Dijkstra 算法用于在具有非负边权的加权图中，找出从单个源顶点到所有其他顶点的最短路径。它通过迭代选择具有最小暂定距离的未访问顶点，更新其邻居的距离，然后标记为已访问来完成。
In the exam, you are often required to construct a table showing the working values at each vertex (box notation) and to state the shortest path and its length. Ensure you carefully manage the working values and update them in the correct order. If there are multiple shortest paths, state one clearly.
在考试中，常要求构建一个表格，用框标记法显示每个顶点的工作值，并写明最短路径及其长度。务必仔细管理工作值并按正确顺序更新。若有多条最短路径，请清晰地标出其中一条。
8. Chinese Postman Problem | 中国邮递员问题
The Chinese postman problem (route inspection problem) asks for the shortest closed walk that traverses every edge of a weighted graph at least once. If the graph is Eulerian (all vertices even), the optimal route is simply an Eulerian circuit, and its length equals the sum of all edge weights.
中国邮递员问题（路径检查问题）要求找到遍历加权图中每条边至少一次的最短闭合行走。如果图是欧拉图（所有顶点度数为偶数），则最优路线即是一条欧拉回路，其长度等于所有边权之和。
When some vertices have odd degree, the graph must be made Eulerian by pairing up odd vertices and adding the shortest paths between them as duplicate edges. The problem reduces to finding a minimum weight perfect matching on the complete graph of odd vertices, then adding these duplicated edges to the original graph. Finally, find an Eulerian circuit on the modified graph.
当存在奇数度顶点时，必须通过将奇度顶点配对并添加它们之间的最短路径作为重复边，使图欧拉化。问题归结为在奇度顶点的完全图中找出最小权完美匹配，然后将这些重复边添加到原图中。最后，在修改后的图中寻找一条欧拉回路。
9. Tracing Eulerian Trails and Circuits | 欧拉迹与回路的追踪
To find an Eulerian trail or circuit after solving a Chinese postman problem, use Fleury’s algorithm: start at an appropriate vertex (odd for a trail, any for a circuit), and at each step, traverse an edge provided it is not a bridge of the remaining graph unless there is no alternative.
在解决中国邮递员问题后，要找出欧拉迹或回路，可以使用 Fleury 算法：从合适的顶点出发（迹从奇度顶点出发，回路可从任意顶点出发），每步在不构成剩余图的桥的前提下遍历一条边，除非别无选择。
Recording the sequence of vertices visited yields the required route. In exam questions, you may be asked to list the edges in the order they are traversed and to calculate the total weight of the route, which is the original total edge weight plus the added duplication weights.
记录所访问的顶点序列即可得到所需路线。考试题目可能要求按遍历顺序列出各边，并计算路径总权重，即原图边权总和加上添加的重复边权重。
10. Exam Technique and Common Pitfalls | 考试技巧与常见误区
When applying Kruskal’s algorithm, explicitly state that you are sorting edges by weight. Show a list or table, and indicate which edges are rejected and why (e.g., ‘would form a cycle’). For Prim, clearly label the order of edge selection and the working table. In Dijkstra’s algorithm, always double-check that you update box values in the correct order and never revisit a vertex once permanently labelled.
在应用 Kruskal 算法时，要明确说明是按权重排序边，展示列表或表格，并标明哪些边被拒绝及其原因（例如“会形成圈”）。对于 Prim 算法，清楚标记边的选择顺序和工作表。在 Dijkstra 算法中，务必反复核查是否按正确顺序更新了框值，且一旦永久标号就不再回访该顶点。
A common mistake is forgetting to check for cycles in Kruskal’s algorithm or miscalculating the minimum distance to the tree in Prim’s algorithm. In Chinese postman problems, students often miss odd-degree vertices or incorrectly identify the minimum matching. Practice with past papers to build confidence and speed.
常见错误包括在 Kruskal 算法中忘记检查是否成圈，或在 Prim 算法中误算到树的最小距离。在中国邮递员问题中，学生常遗漏奇度顶点，或错误识别最小匹配。通过练习历年真题来建立信心和速度。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导