📚 A-Level AQA Mathematics: Graph Theory Key Points | A-Level AQA 数学：图论 考点精讲
Graph theory is a core topic in AQA A-Level Decision Mathematics, offering powerful tools to model and solve real‑world problems involving networks, routes, and relationships. Understanding the key definitions, theorems, and algorithms is essential for success in the exam. This revision guide walks you through every essential concept, from fundamental terminology to algorithms like Kruskal’s and Prim’s, with clear explanations and worked examples.
图论是 AQA A-Level 决策数学的核心主题，它为建模和解决涉及网络、路径和关系的实际问题提供了强大的工具。理解关键定义、定理和算法对于考试成功至关重要。本复习指南将带你梳理从基础术语到 Kruskal 算法和 Prim 算法等每一个重要概念，并配有清晰的解释和示例。
1. Basic Terminology | 基本术语
A graph consists of vertices (nodes) connected by edges (arcs). If the edges have a direction they are called directed edges; otherwise the graph is undirected. A simple graph has no loops and no multiple edges between the same pair of vertices. The order of a graph is the number of vertices, and the size is the number of edges.
图由顶点（节点）和连接顶点的边（弧）组成。如果边有方向，则称为有向边；否则图为无向图。简单图没有环，且同一对顶点之间没有多条边。图的阶是顶点的数量，大小是边的数量。
- Vertex / node – a point in the graph. | 顶点 / 节点 – 图中的一个点。
- Edge / arc – a line joining two vertices. | 边 / 弧 – 连接两个顶点的线。
- Loop – an edge that starts and ends at the same vertex. | 环 – 起点和终点在同一个顶点的边。
- Multiple edges – two or more edges connecting the same vertices. | 多重边 – 连接相同顶点的两条或更多边。
2. Handshaking Lemma | 握手引理
The degree of a vertex is the number of edges incident to it, with loops counted twice. The handshaking lemma states that the sum of the degrees of all vertices in a graph is exactly twice the number of edges. In symbols: Σ deg(v) = 2E. This result implies that any graph must have an even number of vertices with odd degree.
顶点的度是与该顶点相关联的边的数量，环计为 2。握手引理指出，图中所有顶点的度数之和恰好是边数的两倍。用符号表示为：Σ deg(v) = 2E。这一结果意味着任何图的奇度顶点个数必为偶数。
- Useful for checking if a degree sequence can form a graph. | 可用于检验一个度序列是否能构成图。
- A direct consequence: you cannot have a graph with an odd number of vertices of odd degree. | 直接推论：不可能存在含有奇数个奇度顶点的图。
3. Types of Graphs | 图的类型
AQA exams frequently test the properties of different graph types. A complete graph Kn has n vertices with every pair connected by exactly one edge. A cycle graph Cn is a single cycle of n vertices. A tree is a connected graph with no cycles. A forest is a collection of trees. A bipartite graph is one whose vertex set can be split into two disjoint sets so that every edge joins a vertex in one set to a vertex in the other.
AQA 考试经常考查不同类型图的性质。完全图 Kn 有 n 个顶点，每对顶点之间恰好有一条边相连。环图 Cn 是由 n 个顶点组成的单一回路。树是连通且无环的图。森林是树的集合。二分图是指顶点集可以划分为两个不相交的集合，使得每条边都连接一个集合中的顶点与另一个集合中的顶点。
| Graph type 图类型 | Edges 边数 | Key property 关键性质 |
|---|---|---|
| Complete Kn | n(n−1)/2 | Every vertex degree = n−1 |
| Tree on n vertices | n−1 | Connected, acyclic |
| Cycle Cn | n | Every vertex degree = 2 |
4. Paths and Circuits | 路径与回路
A walk is a sequence of vertices where consecutive vertices are adjacent. A trail is a walk with no repeated edges. A path is a walk with no repeated vertices (hence no repeated edges). A circuit is a closed trail (starts and ends at the same vertex) with no repeated edges. A cycle is a closed path with no repeated vertices except the start/end.
走法是一个顶点序列，其中连续顶点相邻。迹是没有重复边的走法。路径是没有重复顶点的走法（因此也没有重复边）。回路是起点和终点相同且没有重复边的闭迹。圈是除了起点和终点外没有重复顶点的闭路径。
- A walk that visits every vertex exactly once is a Hamiltonian path; if it returns to the start it is a Hamiltonian cycle. | 恰好经过每个顶点一次的走法称为哈密顿路径；如果它回到起点则是哈密顿圈。
- A trail that uses every edge exactly once is an Eulerian trail; if it is closed it is an Eulerian circuit. | 恰好经过每条边一次的迹称为欧拉迹；如果它是闭合的则称为欧拉回路。
5. Trees and Spanning Trees | 树与生成树
A tree with n vertices has exactly n−1 edges and is minimally connected: removing any edge disconnects it. A spanning tree of a connected graph is a subgraph that is a tree and includes all the vertices of the original graph. Every connected graph has at least one spanning tree, and for a weighted graph we often look for a minimum spanning tree (MST).
具有 n 个顶点的树恰好有 n−1 条边，并且是极小连通的：删除任何一条边都会使其不连通。连通图的生成树是一个包含原图所有顶点的树状子图。每个连通图至少有一棵生成树，而对于赋权图，我们通常要寻找最小生成树（MST）。
- A spanning tree can be found by deleting edges from cycles until no cycles remain. | 生成树可通过从图中删除回路的边直到无回路为止来获得。
- Two famous algorithms for MST are Kruskal’s algorithm and Prim’s algorithm. | 两个著名的最小生成树算法是 Kruskal 算法和 Prim 算法。
6. Minimum Spanning Trees | 最小生成树
A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. Kruskal’s algorithm sorts all edges by weight and adds the shortest edge that does not form a cycle, repeating until n−1 edges are added. Prim’s algorithm starts at any vertex and repeatedly adds the cheapest edge connecting the current tree to a vertex not yet in the tree.
最小生成树（MST）是总边权重尽可能小的生成树。Kruskal 算法将所有边按权重排序，依次添加不形成回路的最短边，直到加入 n−1 条边。Prim 算法从任意顶点开始，反复添加连接当前树与尚未加入树的顶点的最便宜边。
| Algorithm 算法 | Approach 方法 | Data structure 常用数据结构 |
|---|---|---|
| Kruskal | Consider edges in increasing weight order | 按权重递增顺序考虑边 | Union–find (disjoint sets) |
| Prim | Grow tree from a starting vertex | 从起始顶点生长树 | Priority queue |
You must be able to apply both algorithms on a given network and trace the order in which edges are selected. In an exam, you often need to show the tree clearly and state its total weight.
你必须能够在给定的网络上应用这两种算法，并追踪边的选择顺序。在考试中，你通常需要清楚地画出这棵树并说明其总权重。
7. Eulerian and Hamiltonian Graphs | 欧拉图与哈密顿图
An Eulerian graph is a connected graph that contains an Eulerian circuit, i.e. a closed trail using every edge exactly once. A connected graph is Eulerian if and only if every vertex has even degree. If exactly two vertices have odd degree, the graph has an Eulerian trail but not a circuit (semi‑Eulerian).
欧拉图是包含欧拉回路的连通图，即恰好经过每条边一次且回到起点的闭迹。连通图是欧拉图的充要条件是每个顶点的度数均为偶数。如果恰好有两个顶点的度数为奇数，则该图具有欧拉迹但不具有欧拉回路（半欧拉图）。
A Hamiltonian graph contains a Hamiltonian cycle, a cycle visiting every vertex exactly once. Unlike Eulerian graphs, there is no simple necessary and sufficient condition for a graph to be Hamiltonian. You may be asked to find a Hamiltonian cycle by trial and improvement or to prove that a graph is not Hamiltonian by considering vertex degrees or cut‑sets.
哈密顿图包含哈密顿圈，即恰好经过每个顶点一次并返回起点的圈。与欧拉图不同，哈密顿图没有简洁的充要条件。你可能会被要求通过试错法找到一个哈密顿圈，或通过顶点度数与割集证明某图不是哈密顿图。
- Dirac’s theorem (sufficient condition): If a simple graph with n ≥ 3 vertices has every vertex degree ≥ n/2, it is Hamiltonian. | 狄拉克定理（充分条件）：如果一个具有 n ≥ 3 个顶点的简单图的每个顶点度数 ≥ n/2，则该图是哈密顿图。
- Ore’s theorem: If for every pair of non‑adjacent vertices the sum of their degrees is at least n, the graph is Hamiltonian. | 奥勒定理：如果每一对不相邻顶点的度数之和至少为 n，则该图为哈密顿图。
8. Adjacency Matrices | 邻接矩阵
An adjacency matrix represents a graph with n vertices using an n × n square matrix, where the entry aij is the number of edges directly connecting vertex i to vertex j. For an undirected graph the matrix is symmetric. The powers of the adjacency matrix give information about walks: the (i, j) entry of Ak is the number of walks of length k from vertex i to vertex j.
邻接矩阵用一个 n×n 的方阵表示具有 n 个顶点的图，其中 aij 元素是直接连接顶点 i 和顶点 j 的边的数量。对于无向图，矩阵是对称的。邻接矩阵的幂提供了有关走法的信息：Ak 的第 (i, j) 项是从顶点 i 到顶点 j 且长度为 k 的走法数量。
- To find the number of paths of length exactly k, you may need to use a modified matrix (e.g., using 0–1 entries) and subtract shorter cycles depending on the question. | 要找到恰好长度为 k 的路径数量，你可能需要使用修改后的矩阵（例如 0–1 项）并根据题目要求减去较短的圈。
- For weighted graphs, a weight matrix can be used, where aij holds the weight of the edge. | 对于赋权图，可以使用权重矩阵，其中 aij 存放边的权重。
9. Graph Colouring | 图着色
Vertex colouring assigns a colour to each vertex so that adjacent vertices have different colours. The chromatic number χ(G) is the minimum number of colours needed. A graph that can be coloured with k colours is k‑colourable. The four colour theorem says that any planar graph can be coloured with at most four colours, which is helpful for map‑colouring problems.
顶点着色为每个顶点分配一种颜色，使得相邻顶点颜色不同。色数 χ(G) 是所需颜色的最小数量。可以用 k 种颜色着色的图称为 k‑可着色。四色定理指出，任何平面图最多可用四种颜色着色，这对地图着色问题很有帮助。
You should be able to find an upper bound for χ(G) using the greedy algorithm or by observing that χ(G) ≤ Δ+1, where Δ is the maximum degree. Lower bounds can be found by identifying complete subgraphs (a clique of size r forces χ(G) ≥ r) or odd cycles (χ(G) ≥ 3).
你应该能够使用贪心算法求出 χ(G) 的上界，或根据 χ(G) ≤ Δ+1（其中 Δ 为最大度）得到上界。下界可以通过找到完全子图（大小为 r 的团迫使 χ(G) ≥ r）或奇环（χ(G) ≥ 3）来确定。
- For bipartite graphs, χ(G) = 2. | 对于二分图，χ(G) = 2。
- Exam questions often ask you to determine whether a graph is 2‑, 3‑, or 4‑colourable and to justify your answer. | 考试题目常要求判断一个图是 2‑可着色、3‑可着色还是 4‑可着色，并给出理由。
10. Bipartite Graphs and Matchings | 二分图与匹配
A bipartite graph is one whose vertices can be partitioned into two sets X and Y so that every edge joins a vertex in X to a vertex in Y. A common application is matching problems (e.g., assigning workers to tasks). A matching is a set of edges with no shared vertices. A maximum matching uses the greatest possible number of edges, and a complete matching (perfect matching) covers every vertex in the smaller part.
二分图是顶点可划分为两个集合 X 和 Y 的图，每条边都连接 X 中的一个顶点和 Y 中的一个顶点。常见的应用是匹配问题（例如将工人分配给任务）。匹配是一组没有公共顶点的边。最大匹配使用了尽可能多的边，完全匹配（完美匹配）覆盖了较小部分中的所有顶点。
The alternating path algorithm (based on augmenting paths) is used to find a maximum matching or improve an initial matching. An alternating path starts at an unmatched vertex and alternates between edges not in the matching and edges in the matching. If it ends at another unmatched vertex, it is an augmenting path, and flipping its edge status increases the matching size by 1.
交替路径算法（基于增广路径）用于寻找最大匹配或改进初始匹配。交替路径从一个未匹配的顶点开始，在匹配外和匹配内的边之间交替。如果它结束于另一个未匹配的顶点，则为一条增广路径，翻转其边的状态会使匹配的大小增加 1。
- Step 1: Find an initial matching (greedy is fine). | 第 1 步：找到一个初始匹配（贪心即可）。
- Step 2: Look for an augmenting path from an unmatched X‑vertex. If found, augment the matching. Repeat until no augmenting path exists. | 第 2 步：从未匹配的 X‑顶点寻找增广路径。若找到，则增广匹配。重复直到不存在增广路径。
- Necessary and sufficient condition (Hall’s marriage theorem): A complete matching from X to Y exists iff for every subset S of X, |N(S)| ≥ |S|, where N(S) is the neighbour set of S in Y. | 充要条件（霍尔的婚姻定理）：从 X 到 Y 的完全匹配存在的充要条件是，对于 X 的任意子集 S，有 |N(S)| ≥ |S|，其中 N(S) 是 S 在 Y 中的邻居集合。
11. Planar Graphs and Euler’s Formula | 平面图与欧拉公式
A graph is planar if it can be drawn in the plane without any edges crossing. The drawing partitions the plane into regions (faces). Euler’s formula for a connected planar graph is V − E + F = 2, where V is vertices, E is edges, and F is faces (including the outer infinite face). This formula is fundamental for proving certain graphs are non‑planar by contradiction.
如果一个图可以在平面上画出且没有任何边相交，则它是平面图。画法将平面分成若干区域（面）。连通平面图的欧拉公式为 V − E + F = 2，其中 V 为顶点数，E 为边数，F 为面数（包括外部无穷面）。该公式是通过反证法证明某些图非平面图的基础。
Two classical non‑planar graphs are K5 (complete graph on 5 vertices) and K3,3 (complete bipartite graph with 3 vertices in each part). Any non‑planar graph must contain a subgraph that is a subdivision of K5 or K3,3 (Kuratowski’s theorem).
两个经典的非平面图是 K5（5 个顶点的完全图）和 K3,3（每部分 3 个顶点的完全二分图）。任何非平面图必定包含一个 K5 或 K3,3 的细分作为子图（库拉托夫斯基定理）。
- Using Euler’s formula, you can prove that for a simple connected planar graph with V ≥ 3, we have E ≤ 3V − 6. | 利用欧拉公式可以证明：对于 V ≥ 3 的简单连通平面图，有 E ≤ 3V − 6。
- For bipartite planar graphs with V ≥ 3, E ≤ 2V − 4. | 对于 V ≥ 3 的二分平面图，有 E ≤ 2V − 4。
12. Exam Tips and Common Pitfalls | 考试技巧与常见失分点
Many marks are lost through misreading ‘walk’, ‘trail’, ‘path’, ‘circuit’, and ‘cycle’. Memorise the definitions precisely. When applying Kruskal’s or Prim’s algorithm, write down the order of edge selection clearly; in Prim’s, always state your starting vertex. For graph colouring, do not just name a number – sketch the colouring or give a logical justification of the lower bound.
许多分数因混淆 “走法”、“迹”、“路径”、“回路” 和 “圈” 而丢失。务必精确记忆定义。在应用 Kruskal 或 Prim 算法时，清晰地写下边选择的顺序；对于 Prim 算法，一定要说明起始顶点。对于图着色，不要只给出一个数字——应草绘着色方案或给出下界的逻辑理由。
When using the handshaking lemma, always count loops as 2 and be careful with graphs that have multiple edges. In bipartite matching questions, you must show your alternating paths step by step; just stating the final matching may not earn full marks. Finally, always check whether a graph is simple or may contain loops/multiple edges, because the formulas for maximum edges differ.
使用握手引理时，始终将环计为 2，并注意有重边的图。在二分图匹配问题中，你必须逐步展示交替路径；仅给出最终匹配可能无法得到全部分数。最后，始终检查图是简单图还是可能包含环/重边，因为最大边数的公式不同。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导