AS Mathematics: Graph Theory Key Points | AS 数学：图论考点精讲

📚 AS Mathematics: Graph Theory Key Points | AS 数学：图论考点精讲

Graph theory is a fundamental topic in AS-level Decision Mathematics. It provides a powerful language for modelling relationships and connections, from transport networks to scheduling problems. Mastering the core definitions, algorithms, and diagrammatic conventions will not only help you solve exam problems efficiently but also develop logical thinking applicable across STEM disciplines.

图论是 AS 决策数学中的基础内容，为描述交通网络、调度问题等关联关系提供了一套强大的语言。掌握核心定义、算法和图示规范，不仅能高效解答考题，更能培养贯穿理工科学习的逻辑思维能力。

1. What Is a Graph? | 什么是图？

A graph is a set of vertices (nodes) connected by edges (arcs). In decision mathematics, graphs model real-world situations where pairs of objects are related. A graph may be represented by a diagram or by its vertex and edge sets.

图是由边（弧）连接的一组顶点（节点）构成的。在决策数学中，图用来对现实世界中成对相关的事物进行建模。图可以用示意图表示，也可以用顶点集和边集描述。

A graph G = (V, E) consists of a vertex set V and an edge set E.
图 G = (V, E) 由顶点集 V 和边集 E 组成。
An edge connecting vertex u to v is often written as {u, v} for an undirected graph or (u, v) for a directed graph.
在无向图中连接顶点 u 和 v 的边常记作 {u, v}，在有向图中则记作 (u, v)。

Vertices are drawn as dots or labelled points; edges as lines or curves joining them. A simple graph has no loops and at most one edge between any pair of vertices.

顶点画成点或标号圆点，边用直线或曲线连接。简单图不含环，且任意两顶点间最多只有一条边。

2. Basic Terminology | 基本术语

The degree of a vertex is the number of edges incident to it, with loops counted twice. The sum of the degrees is always twice the number of edges.

顶点的度是指与之关联的边数（环算两次）。所有顶点度数之和等于边数的两倍。

Order of a graph = number of vertices; size = number of edges.
图的阶 = 顶点数；大小 = 边数。
Two vertices are adjacent if they are joined by an edge.
若两顶点之间有边相连，则称它们相邻。
A walk is a sequence of vertices and edges; a trail has no repeated edges; a path has no repeated vertices.
行走是顶点和边的交替序列；迹中没有重复的边；路径中没有重复的顶点。

A graph is connected if there is a path between every pair of vertices. A disconnected graph splits into components.

若任意两顶点之间都存在路径，则图是连通的；不连通的图会分成若干连通分支。

Handshaking lemma: In any graph, the number of odd-degree vertices is even.

握手引理： 任何图中，奇度顶点的个数是偶数。

3. Types of Graphs | 图的分类

Graphs come in several varieties, and exam questions often ask you to identify or choose the right type for a given context.

图有多种类型，考试常要求根据情境辨别或选择合适的图。

Directed graph (digraph): edges have a direction, drawn with arrows.
有向图： 边有方向，用箭头表示。
Weighted graph: each edge carries a numerical value (weight), representing cost, distance, time, etc.
加权图： 每条边带有一个数值（权），可代表费用、距离、时间等。
Complete graph Kₙ: every pair of distinct vertices is connected; it has ⁿ(n−1)/2 edges.
完全图 Kₙ： 每对不同顶点之间都有边；边数为 ⁿ(n−1)/2。
Bipartite graph: vertices can be split into two disjoint sets so that every edge connects a vertex from one set to the other.
二部图： 顶点可分成两个不相交的集合，每条边都连接不同集合的顶点。
Tree: a connected graph with no cycles; a forest is a disjoint union of trees.
树：无环的连通图；森林是树的非交并集。

4. Eulerian and Hamiltonian Paths | 欧拉路径与哈密顿路径

An Eulerian trail uses every edge exactly once. An Eulerian circuit (closed trail) starts and ends at the same vertex. 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 exactly when exactly two vertices have odd degree.

欧拉迹恰好经过每条边一次。欧拉回路（闭合迹）起点和终点相同。连通图存在欧拉回路当且仅当每个顶点的度均为偶数。恰有两个奇度顶点时，存在欧拉迹但无欧拉回路。

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle is a Hamiltonian path that returns to the start. There is no simple necessary-and-sufficient condition known, but complete graphs always contain Hamiltonian cycles.

哈密顿路径恰好经过每个顶点一次；哈密顿回路则是回到起点的哈密顿路径。目前没有已知的简单充要条件，但完全图一定含有哈密顿回路。

Typical exam problems: decide whether a given graph is Eulerian, semi-Eulerian, or Hamiltonian, and find the required trail or cycle.

典型考题：判断给定图是否为欧拉图、半欧拉图或哈密顿图，并找出相应的迹或回路。

5. Trees and Spanning Trees | 树与生成树

A tree is a minimally connected graph: it has exactly one path between any two vertices, no cycles, and for n vertices it has exactly n − 1 edges. Any connected graph contains at least one spanning tree — a subgraph that is a tree and includes all the vertices of the original graph.

树是最小连通图：任意两顶点间恰有一条路径，无环，且 n 个顶点的树恰有 n − 1 条边。任何连通图都至少包含一棵生成树——它是原图的子图，且是包含所有顶点的树。

A minimum spanning tree (MST) of a weighted graph is a spanning tree whose total edge weight is as small as possible. Two greedy algorithms — Kruskal’s and Prim’s — guarantee finding an MST.

加权图的最小生成树（MST）是总边权尽可能小的一棵生成树。两种贪心算法——克鲁斯卡尔算法和普里姆算法——都能保证找到最小生成树。

6. Kruskal’s Algorithm | 克鲁斯卡尔算法

Kruskal’s algorithm builds an MST by processing edges in increasing order of weight. It adds the next cheapest edge that does not create a cycle, until n − 1 edges are chosen.

克鲁斯卡尔算法按权重递增的顺序处理边，将不会形成环的最短边加入，直到选出 n − 1 条边为止。

Algorithm steps: 1. List all edges in ascending order of weight. 2. Start with an empty edge set for the MST. 3. For each edge in the list, if adding it does not form a cycle, include it. 4. Stop when the MST has n − 1 edges.

算法步骤：1. 将所有边按权重升序列出。2. 初始化 MST 的边集为空。3. 依次检查列表中的每条边，若加入后不会形成环，则将其纳入 MST。4. 当 MST 拥有 n − 1 条边时停止。

To test for cycles, you can draw the growing forest or use a trace table. Kruskal’s algorithm is particularly efficient for sparse graphs.

可以用逐步画出的森林或跟踪表来检测环。克鲁斯卡尔算法对稀疏图尤为高效。

7. Prim’s Algorithm | 普里姆算法

Prim’s algorithm grows an MST from a starting vertex by repeatedly adding the cheapest edge that connects a vertex already in the tree to one not yet in it. It works on a connected weighted graph.

普里姆算法从一个起始顶点出发，不断添加连接树内顶点与树外顶点的最短边，从而生长成最小生成树。它适用于连通加权图。

Algorithm steps: 1. Choose any starting vertex. 2. From the edges connecting the tree to vertices outside, select the one with the smallest weight (break ties arbitrarily). 3. Add that edge and the new vertex to the tree. 4. Repeat until all vertices are included.

算法步骤：1. 任选一个起始顶点。2. 从连接当前树与树外顶点的边中，选出权重最小的一条（若有权重相同则任选）。3. 将该边和新顶点加入树。4. 重复直到所有顶点都加入树中。

Using a table (or matrix form) helps keep track of the nearest distance from the tree to each remaining vertex. Prim’s algorithm is often applied to a distance matrix, making it convenient for dense graphs.

利用表格（或矩阵形式）有助于跟踪树到每个剩余顶点的最近距离。普里姆算法常用距离矩阵实现，适合稠密图。

8. Dijkstra’s Algorithm for Shortest Path | 迪杰斯特拉最短路径算法

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non‑negative weights. It builds a set of vertices whose final shortest distances have been determined.

迪杰斯特拉算法用于在非负权加权图中找出从源顶点到其他所有顶点的最短路径。它逐步构建一个已确定最终最短距离的顶点集。

Algorithm steps: 1. Label the start vertex with distance 0 and all others as ∞. 2. Mark all vertices as unvisited. 3. For the current vertex, consider its unvisited neighbours and update their tentative distances. 4. Mark the current vertex as visited and select the unvisited vertex with the smallest tentative distance as the new current. 5. Repeat until the destination is visited or all vertices are visited.

算法步骤：1. 将起点的距离标为 0，其余顶点标为 ∞。2. 将所有顶点标记为未访问。3. 针对当前顶点，考虑其未访问的邻居并更新它们的暂定距离。4. 将当前顶点标记为已访问，并选择暂定距离最小的未访问顶点作为新的当前顶点。5. 重复直到终点被访问或所有顶点都被访问。

At the end, the labels give the shortest distance; the path can be traced back using predecessor information. Exam questions often require laying out work in a box‑style trace table.

结束时，顶点标记即为最短距离；利用前驱信息可以回溯出最短路径。考试常要求用方格跟踪表呈现运算过程。

9. Matching in Bipartite Graphs | 二部图中的匹配

A matching in a bipartite graph is a set of edges with no shared vertices. A maximum matching is a matching of the largest possible size. In many AS problems, two sets — for example, workers and tasks — are connected by edges showing who can do which task.

二部图中的匹配是一组没有共享顶点的边。最大匹配是边数最多的匹配。很多 AS 问题中，两个集合（例如工人和任务）通过表示谁能完成某项任务的边相连。

An alternating path starts with an unmatched vertex and alternates between edges not in the matching and edges in the matching. An augmenting path is an alternating path that starts and ends at unmatched vertices. If an augmenting path exists, the matching can be improved by swapping the roles of the edges along the path.

交错路径从一个未匹配顶点出发，并在不属于匹配的边与属于匹配的边之间交替。增广路径是起点和终点均为未匹配顶点的交错路径。若存在增广路径，则可通过交换路径上边的匹配状态来扩大匹配。

To find a maximum matching, start with an initial matching and repeatedly search for augmenting paths. This is often done by visual inspection for small graphs.

求解最大匹配时，先从初始匹配开始，反复搜索增广路径。对于小规模图，可以通过直接观察完成。

10. Complete Matching and Hall’s Marriage Theorem | 完备匹配与霍尔婚配定理

A complete matching from set X to set Y (|X| ≤ |Y|) is a matching that covers every vertex in X. Hall’s theorem gives a necessary and sufficient condition: a complete matching exists if and only if for every subset S of X, the number of vertices in Y adjacent to at least one vertex in S is at least |S|.

从集合 X 到集合 Y 的完备匹配（|X| ≤ |Y|）是指覆盖了 X 中所有顶点的匹配。霍尔定理给出了充要条件：存在完备匹配当且仅当对于 X 的任意子集 S，Y 中至少与 S 中一个顶点相邻的顶点数不少于 |S|。

Hall’s marriage condition: |N(S)| ≥ |S| for all S ⊆ X, where N(S) is the neighbour set of S.

霍尔婚配条件： 对所有 S ⊆ X，有 |N(S)| ≥ |S|，其中 N(S) 是 S 的邻居集。

Exam tasks involve verifying Hall’s condition for subsets, identifying a subset that fails, and constructing a complete matching if the condition holds.

考试会涉及验证某些子集的霍尔条件、找出不满足条件的子集，以及在条件满足时构造完备匹配。

11. Route Inspection Problem | 路径巡检问题

The route inspection (Chinese postman) problem asks for the shortest closed walk that traverses every edge at least once. For an Eulerian graph, the optimal route is an Eulerian circuit and the total length equals the sum of all edge weights.

路径巡检（中国邮递员）问题要求找出至少经过每条边一次的最短闭合行走。对于欧拉图，最优线路是一条欧拉回路，总长度等于所有边权之和。

For a semi‑Eulerian graph (exactly two odd vertices), the solution is an Eulerian trail plus a shortest path between the two odd vertices. In a general network, identify all odd vertices, pair them up so that the sum of extra distances is minimised, then duplicate those extra paths.

对于半欧拉图（恰有两个奇度顶点），解是一条欧拉迹加上连接这两个奇度顶点的最短路径。对于一般网络，找出所有奇度顶点，将它们配对使额外距离之和最小，然后复制这些额外路径。

This topic reinforces connections between Eulerian trails and shortest‑path algorithms and appears in modelling delivery or inspection routes.

这个主题将欧拉迹与最短路径算法联系起来，常用于建模配送或巡检路线。

12. Common Pitfalls and Exam Tips | 常见误区与应考提示

When applying Kruskal’s algorithm, always sort edges by weight carefully and check for cycles before adding an edge. Using a table to mark connected vertices avoids mistakes.

应用克鲁斯卡尔算法时，务必仔细按权排序，并在加入边之前检查是否成环。使用表格标记已连接的顶点可以避免错误。

For Prim’s algorithm on a matrix, strike out rows and circle columns as you progress; examiners expect clear evidence of the order of edge selection.

在矩阵上执行普里姆算法时，应随进度划去行并圈出列；阅卷人期望看到清晰的选边顺序。

In Dijkstra’s algorithm, keep a neat working table with columns for vertex, permanent label or order of labelling, and working values. Never forget to go “backwards” when the destination is permanently labelled to extract the path.

在迪杰斯特拉算法中，保持整洁的运算表，包含顶点、永久标号或标号顺序、临时值等列。当终点被永久标号后，不要忘记反向提取路径。

For matching problems, draw the bipartite graph clearly, label the two partite sets, and show alternating paths with different colours or styles when augmenting.

解答匹配问题时，清晰画出二部图，标出两个部分点集，并在进行增广时用不同颜色或线型标示交错路径。

Finally, interpret the context: check whether edges are directed, whether weights represent costs or capacities, and always relate your algorithmic solution back to the real‑world scenario in the question.

最后，要结合情境解读：检查边是否有向，权重代表费用还是容量，并始终将算法解与题目中的实际场景相关联。

Published by TutorHao | Decision Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

AS Mathematics: Graph Theory Key Points | AS 数学：图论 考点精讲