📚 Graph Theory Essentials for IGCSE OCR Maths | IGCSE OCR 数学：图论 考点精讲
Graph theory is a vibrant topic that appears in OCR IGCSE Mathematics through problem‑solving and decision‑making contexts. It equips you with tools to model connections, optimise networks and find efficient routes – all essential skills for tackling exam questions involving algorithms and logical reasoning.
图论是 OCR IGCSE 数学中以问题解决和决策分析形式呈现的一个活跃主题。它让你掌握建模连接、优化网络和寻找高效路径的工具——这些都是在考试中应对涉及算法和逻辑推理的题目必不可少的技能。
1. What is a Graph? | 什么是图？
A graph is a set of vertices (or nodes) connected by edges (or arcs). In IGCSE problems, vertices represent objects, and edges represent relationships – like towns linked by roads or tasks in a project.
图是一组由边（或弧）连接的顶点（或节点）。在 IGCSE 题目中，顶点代表对象，边代表关系——例如由道路连接起来的城镇或项目中的任务。
Graphs can be directed or undirected. Directed edges have arrows showing one‑way connections, while undirected edges allow movement in both directions. Weighted graphs have numbers on edges that represent distances, times or costs.
图可以是有向或无向的。有向边带有表示单向连接的箭头，而无向边则允许双向通行。加权图在边上带有数字，代表距离、时间或成本。
A graph model must be clearly defined – always check whether the context requires directed edges, loops or multiple edges between the same two vertices.
图模型必须清晰定义——务必检查上下文是否需要有向边、环或两个相同顶点之间的多重边。
2. Types of Graphs | 图的类型
Understanding common graph types is crucial for identifying which algorithm to apply.
理解常见的图类型对于判断该应用哪个算法至关重要。
Simple graph: no loops or multiple edges.
简单图：没有环或多重边。
Complete graph (Kₙ): every pair of vertices is directly connected. For example, K₄ has 4 vertices and 6 edges.
完全图 (Kₙ)：每一对顶点都直接相连。例如，K₄ 有 4 个顶点和 6 条边。
Tree: a connected graph with no cycles. A tree with n vertices has exactly n−1 edges, making it the sparsest connected structure.
树：没有回路的连通图。有 n 个顶点的树恰好有 n−1 条边，它是最稀疏的连通结构。
Bipartite graph: vertices split into two sets where edges only join vertices from different sets. These appear in matching problems.
二分图：顶点分成两个集合，边只连接不同集合的顶点。常见于匹配问题。
3. Key Terminology | 关键术语
You must be fluent in the language of graph theory to interpret exam questions correctly.
你必须熟练掌握图论的语言，才能正确解读考题。
- Degree / Valency – number of edges meeting at a vertex. A vertex with odd degree is called an odd vertex.
- 度/价 – 在一个顶点处相遇的边的数量。度数为奇数的顶点称为奇顶点。
- Path – a sequence of edges connecting a sequence of vertices, with no vertex repeated.
- 路径 – 连接一系列顶点的边的序列，其中顶点不重复。
- Circuit / Cycle – a closed path; the start and end vertices are the same.
- 回路/圈 – 闭合的路径；起点和终点是同一个顶点。
- Connected graph – there is a path between every pair of vertices.
- 连通图 – 每对顶点之间都存在一条路径。
- Weight – the number on an edge, often representing distance, time or cost.
- 权 – 边上的数字，通常表示距离、时间或成本。
Memorising these definitions saves time when reading algorithm instructions in the exam.
记住这些定义，能让你在考试中阅读算法指令时节省时间。
4. Eulerian and Hamiltonian Paths/Circuits | 欧拉路径/回路与哈密顿路径/回路
Eulerian trails and circuits are about traversing every edge exactly once, while Hamiltonian ones visit every vertex exactly once.
欧拉迹与回路关注的是恰好遍历每条边一次，而哈密顿路径与回路则是恰好访问每个顶点一次。
For an Eulerian circuit to exist, the graph must be connected and all vertices must have even degree. An Eulerian trail (not a circuit) exists if exactly two vertices have odd degree – these become the start and end.
欧拉回路存在的条件是：图必须连通，且所有顶点的度数都为偶数。欧拉迹（非回路）存在的条件是：恰好有两个顶点度数为奇数——这两个顶点分别成为起点和终点。
| Problem | Condition |
| Eulerian circuit | Connected, all even degrees |
| Eulerian trail | Connected, exactly 2 odd degrees |
Eulerian Conditions
OCR questions often ask you to determine whether a route covering every edge exactly once is possible – the Chinese Postman problem is a real‑world extension.
OCR 考题经常让你判断是否存在恰好遍历每条边一次的路线——中国邮递员问题是它的现实应用拓展。
A Hamiltonian cycle visits every vertex exactly once and returns to the start. There is no simple necessary and sufficient condition like for Eulerian circuits; you normally check by inspection or via the travelling salesperson context.
哈密顿回路访问每个顶点恰好一次并回到起点。没有像欧拉回路那样简单的充要条件；通常通过观察，或在旅行商问题的上下文中检查。
5. Trees and Spanning Trees | 树与生成树
A tree is a connected graph with no cycles. Removing any edge disconnects it; adding any edge creates exactly one cycle.
树是没有回路的连通图。删除任何一条边都会使其变得不连通；添加任何一条边都会恰好产生一个回路。
A spanning tree of a graph G is a subgraph that includes all vertices of G, is connected, and contains no cycles. A graph may have many spanning trees.
图 G 的生成树是包含 G 的所有顶点、连通且无回路的子图。一个图可以有多个生成树。
g tree = n − 1, where n is the number of vertices. This is a quick check in exam problems.
任何生成树的边数 = n − 1，其中 n 是顶点数。这在考试中是快速检验的方法。
Finding the minimum spanning tree (MST) is a core skill – the tree with the smallest total weight connecting all vertices.
找到最小生成树 (MST) 是一项核心技能——即总权重最小的、连接所有顶点的树。
6. Minimum Spanning Trees – Kruskal’s Algorithm | 最小生成树 – Kruskal 算法
Kruskal’s algorithm builds an MST by sorting edges by weight and selecting them one by one, avoiding cycles.
Kruskal 算法通过按权重对边排序，并逐一选取来构建 MST，同时避免形成回路。
Steps:
步骤：
- List all edges in ascending order of weight.
- 按权重递增顺序列出所有边。
- Start with an empty set of edges for the MST. Select the edge with smallest weight.
- 从一个空的 MST 边集开始。选择权重最小的边。
- Continue selecting the next smallest edge that does not form a cycle with the already chosen edges.
- 继续选择下一条最小的边，该边不能与已选的边构成回路。
- Stop when n−1 edges have been selected.
- 当选择了 n−1 条边时停止。
Use a table to record chosen edges and reject those that would create a cycle. OCR often provides an incomplete table for you to finish.
使用表格记录已选的边，并拒绝那些会产生回路的边。OCR 通常提供一个不完整的表格，让你完成。
Kruskal is efficient for sparse graphs. Remember that if two edges have the same weight, you may choose either – the MST may not be unique, but the minimum total weight is.
Kruskal 适用于稀疏图。记住，如果两条边权重相同，你可以任选一条——MST 可能不唯一，但最小总权重是唯一的。
7. Minimum Spanning Trees – Prim’s Algorithm | 最小生成树 – Prim 算法
Prim’s algorithm grows the MST from an initial vertex by repeatedly adding the cheapest edge that connects a tree vertex to a non‑tree vertex.
Prim 算法从一个初始顶点开始生长 MST，反复添加连接树内顶点与树外顶点的最便宜边。
Steps:
步骤：
- Choose any start vertex and add it to the tree.
- 任选一个起点顶点，加入树中。
- From all edges connecting tree vertices to non‑tree vertices, choose the one with the smallest weight.
- 在连接树内顶点与树外顶点的所有边中，选择权重最小的那一条。
- Add that edge and the new vertex to the tree.
- 将该边和新顶点加入树中。
- Repeat until all vertices are in the tree.
- 重复直到所有顶点都在树中。
Using a table with columns for ‘tree vertices’, ‘edges available’, ‘chosen edge’ and ‘weight’ helps organise your working. Prim’s algorithm is particularly suited to dense graphs or when given a starting point.
使用包含“树内顶点”、“可选边”、“已选边”和“权重”各列的表格，有助于组织你的解题过程。Prim 算法特别适合稠密图或指定了起点的情况。
In an exam, you may be asked to apply Prim using a matrix – this is simply the algorithm applied to a table of weights.
在考试中，你可能会被要求用矩阵应用 Prim 算法——这本质上就是将算法应用于权重表格。
8. Shortest Path – Dijkstra’s Algorithm | 最短路径 – Dijkstra 算法
Dijkstra’s algorithm finds the shortest route from a source vertex to all other vertices in a weighted graph with non‑negative weights.
Dijkstra 算法在具有非负权重的加权图中，找出从源顶点到所有其他顶点的最短路径。
Core idea: assign temporary distance labels to vertices, update them as shorter paths are found, and finalise the smallest tentative distance step by step.
核心思想：给顶点赋予临时距离标号，当找到更短路径时更新它们，并逐步确定最小的试探性距离。
Your working must show the box notation clearly: a box with the final distance and the previous vertex. OCR marking schemes expect the order of labelling and a neat record of temporary values.
你的解题过程必须清晰展示框注记法：一个包含最终距离和前驱顶点的方框。OCR 评分标准要求标注的顺序和清晰的临时值记录。
If the graph is small, you might trace the algorithm without boxes, but using boxes prevents errors. Always check for backtracking when you need the actual path, not just the distance.
如果图较小，你可以不使用方框而直接追踪算法，但使用方框可以避免错误。当你需要实际路径而不仅仅是距离时，务必进行回溯。
Dijkstra’s algorithm is often combined with a map‑style problem – schools, delivery routes or networks of roads.
Dijkstra 算法常与地图类问题结合——学校、配送路线或公路网。
9. Critical Path Analysis (CPA) Intro | 关键路径分析简介
Some IGCSE OCR extension or problem‑solving contexts introduce the basics of activity networks. A project is made up of activities with durations; these are represented on an activity‑on‑edge (A‑on‑E) or activity‑on‑node diagram.
一些 IGCSE OCR 的拓展或问题解决情境会引入活动网络的基础知识。一个项目由带有持续时间的活动组成；这些活动用边表示（A‑on‑E）或节点表示（A‑on‑Node）的图表来呈现。
An activity network is a directed graph where arcs represent activities, and vertices represent events (start/end of an activity). Dummy activities (dashed lines, weight 0) are used to preserve logical dependencies without consuming time.
活动网络是一个有向图，弧线代表活动，顶点代表事件（活动的开始/结束）。虚活动（虚线，权重为 0）用于在不消耗时间的前提下保持逻辑依赖关系。
The critical path is the longest path through the network; it determines the minimum project completion time. Any delay on a critical activity delays the whole project.
关键路径是网络中耗时最长的路径；它决定了项目的最短完工时间。任何关键活动的延迟都会导致整个项目延期。
To find it, calculate early event times (forward pass) and late event times (backward pass). An event’s float is late time minus early time; critical events have zero float.
为找到关键路径，需要计算最早事件时间（正向遍历）和最晚事件时间（反向遍历）。事件的时差等于最晚时间减去最早时间；关键事件的时差为零。
OCR questions may give a precedence table and ask you to draw the network, or provide a network and require the critical path and floats. Practice both directions.
OCR 题目可能给出一个前导关系表，要求你绘制网络图；或者提供网络图，要求找出关键路径和时差。两个方向都要练习。
10. Exam Tips | 考试技巧
Mastering graph theory questions in OCR IGCSE requires a precise, step‑by‑step approach.
在 OCR IGCSE 中掌握图论题目，需要精确的、逐步进行的解题方法。
- Always draw a clear, labelled diagram when not given. Use pencil for edges you may need to change.
- 如果没有给出图，务必绘制一个清晰的带标注的图。用铅笔绘制可能需要修改的边。
- For Kruskal, list edges in weight order first, then tick them off. For Prim, mark the tree vertices clearly.
- 对于 Kruskal 算法，先按权重顺序列出边，然后逐一标记。对于 Prim 算法，清楚地标记树内顶点。
- In Dijkstra, record temporary values neatly; cross them out when replaced. Show boxed permanent labels.
- 在 Dijkstra 算法中，整洁地记录临时值；当它们被替换时划掉它们。展示带有框注记的永久标号。
- Check that your spanning tree has exactly n−1 edges, or that your shortest path tree includes all vertices.
- 检查你的生成树是否恰好有 n−1 条边，或者你的最短路径树是否包含所有顶点。
- If a network contains negative weights, Dijkstra fails – use an alternative or follow the question’s guidance.
- 如果网络包含负权重，Dijkstra 算法会失效——应使用替代方法或遵循题目的指示。
- Time management: graph questions are often worth many marks; do not rush the labelling stages.
- 时间管理：图论题目通常分值较高；不要急于完成标注阶段。
- Finally, communicate your method clearly – OCR rewards a visible, logical sequence of decisions.
- 最后，清晰地展示你的解题过程——OCR 看重可见且逻辑清晰的决策顺序。
Published by TutorHao | Graph Theory Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图