📚 IB & WJEC Mathematics: Graph Theory Key Points | IB 与 WJEC 数学：图论考点精讲
Graph theory is a fundamental topic in both IB Mathematics: Applications and Interpretation and WJEC Decision Mathematics. Mastering the core concepts, algorithms, and proof techniques will not only secure exam marks but also build logical reasoning skills. Graph theory models relationships and networks, ranging from social connections to transportation systems. This revision guide distills key points, algorithms, and exam strategies tailored for IB and WJEC students.
图论是IB数学：应用与解释以及WJEC决策数学中的基础主题。掌握核心概念、算法和证明技巧不仅能在考试中稳操胜券，还能培养逻辑推理能力。图论能够模拟从社交网络到交通系统的各种关系与网络。这篇复习指南提炼了针对IB与WJEC学生的重点、算法和应试策略。
1. Introduction to Graph Theory | 图论简介
A graph G = (V, E) consists of vertices (nodes) V and edges (lines) E connecting vertices. Edges may be undirected or directed, weighted or unweighted. Graph theory provides tools to solve optimisation problems such as finding the shortest route, spanning a network with minimal cost, and determining if a path exists that traverses each edge exactly once.
图 G = (V, E) 由顶点（节点）集合 V 和连接顶点的边集合 E 组成。边可以是无向的或有向的，带权或不带权。图论为解决诸如寻找最短路径、以最小成本覆盖网络、以及判断是否存在一条恰好遍历每条边一次的路径等优化问题提供了工具。
2. Basic Terminology | 基本术语
Order of a graph: number of vertices, denoted |V|. Size: number of edges, |E|. Degree of a vertex: number of edges incident to it, with loops counted twice. Adjacent vertices: connected by an edge. Path: sequence of vertices where each adjacent pair is connected by an edge. Cycle: closed path with no repeated vertices except start=end. Connected graph: there is a path between any two vertices. Complete graph Kn: every pair of vertices is adjacent. Simple graph: no loops or multiple edges.
图的阶：顶点个数，记作 |V|。边数：边的条数，|E|。顶点的度：与该顶点相关联的边数，自环算两次。相邻顶点：由一条边连接。路径：一个顶点序列，其中相邻顶点均由边连接。圈：起点与终点相同的闭合路径，且中间无重复顶点。连通图：任意两顶点间都存在路径。完全图 Kn：每一对顶点都相邻。简单图：无自环，无多重边。
3. Types of Graphs | 图的类型
Simple graph: at most one edge between any two vertices, no loops. Multigraph: allows multiple edges between the same pair of vertices. Pseudograph: includes loops and multiple edges. Digraph (directed graph): edges have direction (arrows). Weighted graph: each edge carries a numerical weight (cost, distance). Bipartite graph: vertices can be split into two disjoint sets so that every edge connects a vertex in one set to a vertex in the other. Complete bipartite Km,n has all possible edges between the two sets. Complete graph Kn has n(n-1)/2 edges.
简单图：任意两顶点间最多一条边，无自环。多重图：允许同一对顶点间有多条边。伪图：包含自环和多重边。有向图：边有方向（箭头）。带权图：每条边附带一个数值权重（成本、距离）。二分图：顶点可分成两个不相交的集合，每条边连接一个集合中的顶点与另一集合中的顶点。完全二分图 Km,n 包含了两个集合之间所有可能的边。完全图 Kn 有 n(n-1)/2 条边。
4. Representation of Graphs | 图的表示
Graphs can be represented by adjacency matrices: a square matrix where entry aij = number of edges from vertex i to vertex j (1 for simple graphs). For a weighted graph, store the weight instead of 1. Incidence matrices: rows represent vertices, columns represent edges; entry is 1 if the vertex is incident to the edge. Adjacency lists are space-efficient for sparse graphs: each vertex stores a list of its neighbours. In IB and WJEC exams, you will mostly use diagrams and adjacency matrices to model problems.
图可以采用邻接矩阵表示：一个方阵，其中元素 aij = 从顶点 i 到顶点 j 的边数（简单图中为 1）。带权图则存储权重而非 1。关联矩阵：行表示顶点，列表示边；若顶点与边关联则元素为 1。邻接表对于稀疏图更节省空间：每个顶点存储其邻居的列表。在IB和WJEC考试中，你将主要使用图形和邻接矩阵来建立问题模型。
5. Traversability: Eulerian and Hamiltonian Graphs | 可遍历性：欧拉图与哈密顿图
Eulerian trail: a trail that visits every edge exactly once. Eulerian circuit: an Eulerian trail that 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 if exactly two vertices have odd degree (the trail starts and ends at those vertices). Hamiltonian path: visits every vertex exactly once. Hamiltonian cycle: a Hamiltonian path that returns to the start. There is no simple necessary and sufficient condition for Hamiltonian cycles; identifying them often requires exhaustive search or heuristics. Eulerian problems link to the Chinese Postman Problem, while Hamiltonian problems link to the Travelling Salesman Problem (TSP).
欧拉迹：恰好经过每条边一次的迹。欧拉回路：起点与终点相同的欧拉迹。一个连通图有欧拉回路当且仅当每个顶点的度均为偶数。若恰好有两个奇数度顶点，则存在欧拉迹（非回路），迹以这两个顶点为起点和终点。哈密顿路径：恰好经过每个顶点一次。哈密顿圈：返回起点的哈密顿路径。哈密顿圈没有简单的充要条件；识别它通常需要穷举搜索或启发式方法。欧拉问题与中国邮递员问题相关，而哈密顿问题与旅行商问题（TSP）相关。
6. Trees and Spanning Trees | 树与生成树
A tree is a connected graph with no cycles. Properties: a tree with n vertices has exactly n – 1 edges; any two vertices are connected by a unique path; adding any edge creates a cycle. A spanning tree of a connected graph is a subgraph that is a tree and includes all vertices. A minimum spanning tree (MST) is a spanning tree with the smallest total edge weight. MST algorithms are crucial for network design and appear frequently in both IB and WJEC papers.
树是连通且无圈的图。性质：有 n 个顶点的树恰好有 n – 1 条边；任意两顶点由唯一路径连接；添加任何一条边都会产生圈。连通图的生成树是一个包含所有顶点的树状子图。最小生成树（MST）是总边权最小的生成树。MST算法在网络设计中至关重要，在 IB 和 WJEC 试卷中频频出现。
7. Minimum Spanning Tree: Kruskal’s Algorithm | 最小生成树：克鲁斯卡尔算法
Kruskal’s algorithm builds an MST by repeatedly adding the cheapest edge that does not form a cycle. Steps: 1) List all edges in ascending order of weight. 2) Start with an empty edge set. 3) Scan the list: add the next edge if it connects two currently disconnected components (i.e., does not create a cycle). 4) Stop when you have added n-1 edges (n = number of vertices). The algorithm is greedy and efficient when edges are sorted. Use a union-find structure or simply draw the graph to check for cycles. For weighted, connected graphs, Kruskal’s algorithm always yields an MST.
克鲁斯卡尔算法通过反复添加不形成圈的最廉价边来构造最小生成树。步骤：1) 将所有边按权值升序排列。2) 从空边集开始。3) 遍历列表：若某边连接当前两个不连通的分量（即不产生圈），则加入该边。4) 当已加入 n-1 条边时停止（n 为顶点数）。该算法是贪心的，在边已排序时效率很高。可使用并查集或直接画图来检查是否成圈。对于带权连通图，克鲁斯卡尔算法总能得到最小生成树。
8. Prim’s Algorithm and Comparison | 普里姆算法及比较
Prim’s algorithm grows an MST from an initial vertex. Steps: 1) Choose any starting vertex, mark it as in the tree. 2) Among all edges that connect a tree vertex to a non-tree vertex, pick the edge with the smallest weight. 3) Add that edge and the new vertex to the tree. 4) Repeat until all vertices are included. Use a table or a priority queue to manage distances. Prim’s algorithm is preferable for dense graphs (many edges) while Kruskal’s works well for sparse graphs. Both are guaranteed to find the MST. In exams, you may be asked to perform either algorithm on a given network; clearly show the order of edge selection.
普里姆算法从一个初始顶点开始逐步生长最小生成树。步骤：1) 任选一个起始顶点，标记为树内顶点。2) 在所有连接树内顶点与树外顶点的边中，选取权值最小的边。3) 将该边及新顶点加入树中。4) 重复直到所有顶点都包含在内。可以使用表格或优先队列管理距离。普里姆算法适用于稠密图（边很多），而克鲁斯卡尔算法在稀疏图上更优。两种算法都保证能找到最小生成树。考试中可能要求你在给定网络上执行任一算法；请清晰显示边的选择顺序。
9. Shortest Path: Dijkstra’s Algorithm | 最短路径：迪杰斯特拉算法
Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. Procedure: 1) Assign a tentative distance value to every vertex: 0 for the initial vertex, infinity (∞) for others. Mark all vertices unvisited. 2) Set the current vertex as the initial vertex. 3) For each unvisited neighbour, calculate the tentative distance (current distance + edge weight). If this is smaller than the previously recorded distance, update it. 4) When all neighbours are examined, mark the current vertex as visited (its distance is final). 5) Select the unvisited vertex with the smallest tentative distance as the new current vertex, and repeat from step 3. The algorithm terminates when you mark the target vertex as visited, or all vertices are visited. Use a table showing vertices, their distances, previous vertex, and visited status. Dijkstra’s algorithm fails if negative edge weights exist.
迪杰斯特拉算法可在边权非负的图中找出从源顶点到所有其他顶点的最短路径。流程：1) 为每个顶点分配一个试探距离值：起点为 0，其余为无穷大（∞）。将所有顶点标记为未访问。2) 设当前顶点为起点。3) 对于每个未访问的邻居，计算试探距离（当前距离 + 边权）。若该值小于之前记录的距离，则更新。4) 检查完所有邻居后，将当前顶点标记为已访问（其距离已最终确定）。5) 选择未访问顶点中试探距离最小的作为新的当前顶点，从步骤 3 重复。当目标顶点被标记为已访问，或所有顶点均已访问时算法结束。使用表格显示顶点、距离、前驱顶点和访问状态。若存在负权边，迪杰斯特拉算法会失效。
10. Travelling Salesman Problem (TSP) & Upper/Lower Bounds | 旅行商问题及上下界
The Travelling Salesman Problem seeks the shortest Hamiltonian cycle (a tour visiting each vertex exactly once and returning to the start) in a complete weighted graph. TSP is NP-hard, so optimal solutions are impractical for large networks. Exams focus on finding upper and lower bounds. Upper bound: any valid tour length. The nearest neighbour algorithm provides a quick upper bound: start at a vertex, repeatedly go to the nearest unvisited vertex, then return to the start. The minimum spanning tree lower bound is obtained by finding the MST of the reduced graph (omitting one vertex) and adding the two shortest edges from the omitted vertex to the MST. Another lower bound can use the sum of the two smallest edges incident to each vertex, halved (the ‘twice-nearest’ bound). Comparing bounds helps assess how close a heuristic tour is to the optimum. For IB and WJEC, you must clearly show working for both bounds.
旅行商问题旨在完全带权图中寻找最短的哈密顿圈（经过每个顶点恰一次并返回起点的巡回路线）。TSP 是 NP-难的，因此对于大型网络来说最优解并不实际。考试聚焦于找出上界和下界。上界：任何可行巡回的长度。最近邻算法可快速给出上界：从一个顶点开始，反复前往最近的未访问顶点，最后返回起点。最小生成树下界：通过去掉一个顶点后的缩减图求 MST，再加上省略顶点到 MST 的两条最短边得到。另一种下界可使用每个顶点两条最短关联边之和的一半（“两倍最近”界）。比较上下界有助于评估启发式巡回与最优解的接近程度。对于 IB 和 WJEC，你必须清晰展示两种界的计算过程。
11. Exam Tips for IB & WJEC | IB 与 WJEC 考试技巧
When solving graph theory problems, always draw a clear, labelled diagram. For algorithm questions, present a step-by-step table or an ordered list of edges. In IB exams, state the final answer in the required context (e.g., total weight, route). For WJEC Decision Mathematics, show clearly the order of edge selection in Kruskal’s or Prim’s, and update distance tables methodically for Dijkstra. When finding upper/lower bounds, justify your choice and clearly mark any corrections or updates. Check if the question asks for a specific format (e.g., matrix representation, list of vertices). Manage time: graph algorithms are often procedural; practice until you can execute them quickly and accurately. Read the entire question: sometimes you need to modify a graph before applying an algorithm (e.g., eliminate certain edges).
解图论题目时，一定要画出清晰、带标签的示意图。算法题需要呈现逐步的表格或有序的边列表。在IB考试中，用题目要求的语境给出最终答案（如总权重、路线）。对于WJEC决策数学，在克鲁斯卡尔或普里姆算法中要清晰显示边的选择顺序，并在迪杰斯特拉算法中有条理地更新距离表格。求上下界时，要说明选择的理由并清晰标记修正或更新。检查题目是否要求特定格式（如矩阵表示、顶点列表）。管理时间：图算法通常程序化；不断练习直到你能快速、准确地执行。通读全题：有时需要先修改图（如去掉某些边）再应用算法。
12. Common Mistakes and Pitfalls | 常见错误与陷阱
Frequent mistakes include: forgetting to check whether a graph is connected before running algorithms; misidentifying the number of odd-degree vertices in Eulerian problems, leading to a wrong classification; adding an edge in Kruskal’s that creates a cycle because of rushed drawing; updating Dijkstra’s table incorrectly when a shorter path is found but not recording the new predecessor; confusing upper and lower bounds in TSP; assuming a Hamiltonian cycle always exists (many graphs are not Hamiltonian); and misreading directed edges as undirected. Also, when calculating a lower bound from MST, remember to add the two shortest edges from the omitted vertex, not just any two edges. In exam pressure, always double-check arithmetic and cycle detection. Practice with past papers to internalise these checks.
常见错误包括：在运行算法前忘记检查图是否连通；在欧拉问题中错误识别奇数度顶点个数，导致分类错误；在克鲁斯卡尔算法中因草率绘图而加入了一条会产生圈的边；在最短路径找到时错误更新迪杰斯特拉表格，但没有记录新的前驱顶点；混淆 TSP 的上界与下界；假设哈密顿圈始终存在（许多图并非哈密顿图）；将无向边误读为有向边。此外，由 MST 计算下界时，要记得加上从省略顶点出发的两个最短边，而非任意两边。在考试压力下，务必反复检查算术和圈检测。通过练习真题内化这些检查要点。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导