📚 Graph Theory Essentials for IB/AQA Mathematics | IB AQA 数学：图论 考点精讲
Graph theory provides a powerful language for modelling connections, from social networks to transport systems. In IB and AQA mathematics, mastering vertices, edges, trees, and algorithms like Prim’s and Dijkstra’s unlocks high-value problem-solving marks. This revision guide distils every core concept, algorithm, and common examination pitfall into a clear, bilingual walkthrough.
图论为建模各种连接（从社交网络到交通系统）提供了强大的语言工具。在 IB 和 AQA 数学中，掌握顶点、边、树以及 Prim、Dijkstra 等算法是获取高分的关键。本复习指南将每个核心概念、算法及常考易错点凝练成清晰的中英双语讲解。
1. Graphs and Basic Terminology | 图与基本术语
A graph consists of vertices (nodes) and edges (arcs) joining them. An edge may be undirected or directed. A loop is an edge that connects a vertex to itself, while multiple edges are two or more edges connecting the same pair of vertices. A graph with no loops or multiple edges is called a simple graph.
一张图由 顶点（节点）和连接它们的 边（弧）组成。边可以无向或有向。环是连接顶点与自身的边，而多重边是连接同一对顶点的两条或更多边。没有环和多重边的图称为 简单图。
A walk is a sequence of edges where the end of one edge is the start of the next. A path is a walk with no repeated vertices. A cycle (or circuit) is a closed path – it starts and ends at the same vertex, with no other repetitions.
途径 是一系列边，前一条边的终点是后一条边的起点。路径 是没有重复顶点的途径。回路（或闭途径）是一条闭合路径——起点与终点相同且其他顶点不重复。
2. Types of Graphs | 图的类型
A graph is connected if there is a path between every pair of vertices. Complete graphs Kn have every vertex directly connected to every other vertex. A bipartite graph can be split into two disjoint sets so that every edge runs between the sets; Km,n is a complete bipartite graph.
如果每对不同顶点之间都存在路径，则该图是连通图。完全图 Kn 中每个顶点都与其余所有顶点直接相连。二分图 可以分成两个不相交的顶点集，使得每条边都跨接两个集合；Km,n 是完全二分图。
A tree is a connected graph with no cycles. A forest is a graph whose connected components are trees. Directed graphs (digraphs) have edges with an arrow indicating direction; they are essential for modelling one-way streets or prerequisites.
树 是连通的无环图。森林 是每个连通分量均为树的图。有向图 的边带有表示方向的箭头，这种图对于建模单行道或先决条件至关重要。
3. Representing Graphs | 图的表示
Graphs can be represented by an adjacency matrix: a square matrix where entry aij is the number of edges from vertex i to vertex j. For an undirected simple graph, the matrix is symmetric and the diagonal entries are zero. An adjacency list simply lists each vertex together with its neighbours.
图可以用邻接矩阵表示：一个方阵，其中元素 aij 表示从顶点 i 到顶点 j 的边数。对于无向简单图，矩阵是对称的且对角线元素为零。邻接表 则直接列出每个顶点及其邻居。
In examination problems, you may be given an adjacency matrix and asked to draw the graph or determine the number of walks of a certain length. Remember that the number of walks of length k from vertex i to vertex j is the (i, j)-entry of Ak, where A is the adjacency matrix.
在考题中，可能会给出邻接矩阵要求画出图，或确定某个长度的途径数量。注意，从顶点 i 到顶点 j 的长度为 k 的途径数等于 Ak 中 (i, j) 位置的元素，其中 A 为邻接矩阵。
4. Degree and the Handshaking Lemma | 顶点的度与握手引理
The degree of a vertex is the number of edges incident to it (loops count twice). The handshaking lemma states that the sum of the degrees of all vertices equals twice the number of edges: Σ deg(v) = 2|E|. A corollary is that any graph must have an even number of vertices with odd degree.
顶点的度是与该顶点关联的边的数量（环算作两次）。握手引理指出：所有顶点的度数之和等于边数的两倍：Σ deg(v) = 2|E|。推论是任何图中度数为奇数的顶点必有偶数个。
This lemma is frequently tested in the form ‘explain why a certain graph cannot exist’ or ‘deduce the number of edges from given degrees’. Always check the parity condition for odd-degree vertices.
该引理的常见考法是“解释为什么某张图不可能存在”或“由已知度数推导边的数量”。务必验证奇数度顶点的奇偶性条件。
5. Trees and Spanning Trees | 树与生成树
A tree on n vertices has exactly n − 1 edges and is minimally connected: removing any edge disconnects the tree, and adding any edge creates exactly one cycle. Any connected graph contains a spanning tree − a subgraph that includes all vertices and is a tree.
有 n 个顶点的树恰好有 n − 1 条边，且是极小连通的：删除任一边树就不连通，添加任一边则恰好产生一个圈。任何连通图都包含一棵生成树——包含所有顶点且是树的子图。
To find a spanning tree quickly, perform a breadth-first or depth-first search. In exams, spanning trees are the foundation for minimum spanning tree and network design problems.
要快速找到一棵生成树，可进行广度优先或深度优先搜索。在考试中，生成树是最小生成树和网络设计问题的基础。
6. Minimum Spanning Trees – Prim’s and Kruskal’s Algorithms | 最小生成树：Prim 与 Kruskal 算法
A minimum spanning tree (MST) is a spanning tree with the smallest total edge weight. Two algorithms are required: Prim’s algorithm grows the tree from a start vertex by repeatedly adding the cheapest edge connecting a tracked vertex to an untracked one. Kruskal’s algorithm sorts all edges by weight and adds the next cheapest edge as long as it does not create a cycle.
最小生成树 (MST) 是总边权最小的生成树。需要掌握两种算法：Prim 算法 从起始顶点开始生长树，反复添加连接已选顶点与未选顶点的最便宜边。Kruskal 算法 将所有边按权重排序，依次添加最便宜边，前提是不形成圈。
Both algorithms always produce a minimum spanning tree. Prim’s is often implemented using a priority queue; Kruskal’s uses a disjoint-set data structure to detect cycles. In written exams, precise table or list recording is essential for full marks.
两种算法都能确保得到最小生成树。Prim 算法常用优先队列实现；Kruskal 算法利用不相交集数据结构检测圈。笔试中，清晰记录表格或列表是获得全分的关键。
7. 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 uses labels (distance from source, previous vertex) and updates them iteratively. The vertex with the smallest temporary distance is permanently labelled each step.
Dijkstra 算法可在具有非负边权的赋权图中找出从源点到所有其他顶点的最短路径。它使用（距源点距离，前一顶点）标签并迭代更新。每一步永久标号临时距离最小的顶点。
d[v] = min(d[v], d[u] + weight(u, v))
Working in a table with columns for vertex, distance, previous vertex, and status (temporary/permanent) is the safest exam technique. Once all vertices are permanently labelled, you can trace back from any destination to find the shortest route.
采用包含顶点、距离、前一顶点以及状态（临时/永久）列的表格操作是最稳妥的考试技巧。当所有顶点都拥有永久标号后，即可从任一目的地回溯到源点，找出最短路线。
8. Chinese Postman Problem | 中国邮递员问题
The Chinese Postman Problem aims to find a minimum-weight closed walk that traverses every edge at least once. For an Eulerian graph (all vertices even degree), an Eulerian circuit traverses each edge exactly once. If the graph is semi-Eulerian (exactly two odd-degree vertices), an Eulerian trail covers all edges; the problem reduces to finding the shortest path between the two odd vertices to repeat.
中国邮递员问题目标是找出一条权重最小的闭途径，经过每条边至少一次。对于欧拉图（所有顶点度数为偶），存在一条恰好经过每条边一次的欧拉回路。如果图是半欧拉图（恰好两个奇度顶点），可找到一条覆盖所有边的欧拉迹；问题归结为找出两个奇度顶点之间的最短路径用于重复行走。
The algorithm: (1) Identify all odd-degree vertices. (2) Find the minimum-weight perfect matching between them using the shortest path distances. (3) Duplicate the edges on the matching paths. The resulting multigraph is Eulerian, and the total weight is the sum of original edge weights plus the matching weight.
算法步骤：(1) 找出所有奇度顶点。(2) 利用最短路径距离在这些奇度顶点之间找出最小权重完美匹配。(3) 复制匹配路径上的边。所得多重图为欧拉图，总权重等于原来边的权重之和加匹配权重。
9. Travelling Salesperson Problem (TSP) | 旅行商问题
The classical TSP asks for a Hamiltonian cycle of minimum total weight, visiting every vertex exactly once and returning to the start. This is an NP-hard problem, so for exam purposes we use heuristic algorithms and lower bounds.
经典旅行商问题要求找到一个总权重最小的哈密顿圈，恰好访问每个顶点一次并返回起点。这是一个 NP 难问题，因此在考试中我们使用启发式算法和下界。
The nearest neighbour algorithm provides an upper bound by repeatedly going to the nearest unvisited vertex. The minimum spanning tree lower bound is obtained by deleting a vertex and finding the MST of the remaining graph, then adding the two shortest edges incident to the deleted vertex. A good tour lies between the lower bound and the best upper bound found.
最近邻算法 通过不断前往最近的未访问顶点给出上界。最小生成树下界 通过删除一个顶点，找到其余图的最小生成树，再加上与该被删顶点关联的最短两条边得出。优质回路介于下界与所找到的最佳上界之间。
For AQA and IB, you must be able to apply the nearest neighbour algorithm from different start vertices and compute the vertex-deletion lower bound systematically.
针对 AQA 和 IB，必须能够从不同起点应用最近邻算法，并有条理地计算删点下界。
10. Network Flows Fundamentals | 网络流基础
A flow network is a directed graph with a source S and a sink T. Each edge has a capacity and carries a flow not exceeding that capacity. Flow conservation holds at all intermediate vertices (inflow = outflow). The maximum flow equals the minimum cut capacity (Max-Flow Min-Cut theorem).
流网络 是一个带有源点 S 和汇点 T 的有向图。每条边有一个容量，且携带不超过容量的流。所有中间顶点满足流量守恒（流入量 = 流出量）。最大流的值等于最小割容量（最大流最小割定理）。
To find a maximum flow, use the labelling procedure (augmenting paths) or the Ford-Fulkerson algorithm. On an exam, show each augmentation step, record the flow on each edge, and identify a saturated cut to confirm optimality.
为找到最大流，可使用标号过程（增广路径）或 Ford-Fulkerson 算法。在考场上，须展示每次增广步骤，记录每条边上的流量，并识别一个饱和割来证实最优性。
11. Common Pitfalls and Examiner Tips | 常见陷阱与考官建议
Many candidates lose marks by confusing paths with walks, forgetting to state a start vertex in Prim’s algorithm, or mixing up the order of vertex labelling in Dijkstra’s. Always write down the algorithm steps in a clear, prescribed format. For KP (Kruskal’s and Prim’s), writing down the edges in order with accumulated weight avoids careless mistakes.
许多考生因混淆路径与途径、忘记在 Prim 算法中声明起始顶点、或在 Dijkstra 算法中搞错顶点标号顺序而失分。务必以清晰且规范的格式写下算法步骤。对于 Kruskal 和 Prim 算法，按顺序写出边并累积权重可避免粗心错误。
In Chinese Postman and TSP questions, drawing a small network from the table or matrix is crucial. Annotate odd vertices, temporary labels, and deleted vertices directly on the diagram to ensure logical flow and secure method marks.
在中国邮递员与旅行商问题中，根据表格或矩阵画出小网络至关重要。直接在图上标注奇点、临时标号以及被删除的顶点，以确保逻辑顺畅并获得方法分。
12. Preparation and Practice | 备考与练习
Mastering graph theory requires hands-on practice. Work through past-paper questions under timed conditions, paying attention to the specific command terms like ‘apply’, ‘determine’, or ‘explain why’. Cross-check your MST, shortest path, or maximal flow with a simple mental verification: the number of edges in a spanning tree equals V − 1, and each vertex (except S and T) must have balanced flow.
掌握图论需要动手练习。在限时条件下完成历年真题，并留意“应用”、“确定”或“解释为什么”等具体指令词。用简单的思维验证交叉检查最小生成树、最短路径或最大流：生成树的边数应等于 V − 1，且除 S 与 T 外每个顶点的流入等于流出。
Use this guide as a checklist: tick off each algorithm and concept once you can explain it in both English and Chinese to a peer. Repetition with bilingual notes deepens understanding and boosts confidence in an international examination setting.
将本指南用作检查清单：每当你能够用中英双语向同学解释某个算法或概念时，便打勾确认。双语笔记的反复练习能深化理解，并在国际考试环境中增强自信。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导