📚 IGCSE CCEA Mathematics: Graph Theory Essentials | IGCSE CCEA 数学：图论考点精讲
Graph theory is a fascinating branch of mathematics that models pairwise relations between objects. For CCEA IGCSE Mathematics, it encompasses a range of practical problem-solving techniques, from route planning to project scheduling. This guide systematically covers all core topics, equipping you with the definitions, algorithms, and strategies needed for success.
图论是数学中一个迷人的分支，用于建立对象间成对关系的模型。在 CCEA IGCSE 数学中，它涵盖了一系列实用的解题技术，从路线规划到项目调度。本指南系统覆盖所有核心主题，为你提供成功所需的定义、算法和策略。
1. Introduction to Graph Theory | 图论简介
A graph is a set of vertices (or nodes) connected by edges (or arcs). It abstracts real-world networks such as roads, utilities, or social connections. Graph theory allows us to analyse these structures mathematically, solving problems like the shortest path, optimal routing, and scheduling with resource constraints.
图是由顶点（节点）通过边（弧）连接而成的集合。它抽象了道路、公用事业或社交网络等现实世界中的网络。图论让我们能用数学方法分析这些结构，解决最短路径、最优路径以及受限资源下的调度等问题。
CCEA IGCSE focuses on practical applications: deciding if a route can travel each edge exactly once (Eulerian), visiting every vertex exactly once (Hamiltonian), finding minimal connectors (trees), and determining project minimum completion time (critical path analysis).
CCEA IGCSE 侧重于实际应用：判断一条路线能否恰好遍历每条边一次（欧拉图），恰好访问每个顶点一次（哈密顿图），寻找最小连接（树），以及确定项目的最短完成时间（关键路径分析）。
2. Basic Terminology | 基本术语
A vertex (plural: vertices) is a point, often labelled with a letter or number. An edge joins two vertices; it may be directed (arrow) or undirected. A loop is an edge from a vertex to itself. The degree of a vertex is the number of edges incident to it, with loops counted twice.
顶点（复数：vertices）是一个点，通常用字母或数字标注。边连接两个顶点；它可以是有向的（箭头）或无向的。自环是从顶点到自身的边。顶点的度是指与该顶点关联的边数，自环计算两次。
A path is a sequence of vertices where each adjacent pair is connected by an edge, with no vertex visited more than once. A circuit (or cycle) is a closed path where the start and end vertex are the same. A graph is connected if there is a path between every pair of vertices.
路径是一个顶点序列，其中每对相邻顶点由边连接，且没有顶点被重复访问。回路（或环）是起点和终点相同的闭合路径。如果每对顶点之间都存在一条路径，则该图是连通的。
| Term | English Definition | 中文定义 |
|---|---|---|
| Vertex | A node in the graph | 图中的节点 |
| Edge | A line connecting two vertices | 连接两个顶点的线 |
| Degree | Number of edges meeting at a vertex | 聚集于一个顶点的边数 |
| Weight | A number assigned to an edge (e.g., distance, cost) | 赋予边的数值（如距离、成本） |
| Digraph | A graph with directed edges | 有向图 |
3. Types of Graphs | 图的类型
A graph can be simple (no loops, at most one edge between any two vertices), or it can contain multiple edges (multigraph). In a complete graph, every pair of vertices is connected directly by an edge. A bipartite graph has its vertex set split into two disjoint sets, and every edge joins a vertex from one set to the other.
图可以是简单的（无自环，任意两顶点之间最多一条边），也可以包含多重边（多重图）。在完全图中，每对顶点都直接由一条边连接。二部图的顶点集划分为两个不相交的子集，每条边都连接两个不同子集的顶点。
For CCEA, recognising bipartite graphs is useful in matching problems (e.g., assigning tasks to workers). A tree is a connected graph with no circuits. A weighted graph has numbers on its edges, often representing distances, times, or costs.
对 CCEA 而言，识别二部图在匹配问题中很有用（例如将任务分配给工人）。树是连通且无环的图。有权图的边上标有数字，通常表示距离、时间或成本。
4. Representing Graphs | 图的表示
We can represent a graph using an adjacency matrix: a square matrix where the entry in row i, column j is the number of edges connecting vertex i to vertex j (0 if none). For a digraph, the matrix is not necessarily symmetric.
我们可以用邻接矩阵表示图：一个方阵，其中第 i 行第 j 列的元素表示连接顶点 i 和顶点 j 的边数（无则为 0）。对于有向图，该矩阵不一定对称。
Another method is an adjacency list, which more compactly lists each vertex's neighbours. CCEA may ask you to draw a graph from a given matrix or, conversely, write the matrix from a diagram. Always check if edges are directed or weighted, and label clearly.
另一种方法是邻接表，更紧凑地列出了每个顶点的邻居。CCEA 可能会要求你根据给定的矩阵画出图，或者反过来，根据图表写出矩阵。一定要检查边是有向还是带权，并清楚标注。
5. Eulerian Graphs | 欧拉图
An Eulerian trail visits every edge of a graph exactly once. An Eulerian circuit is a closed trail that starts and ends at the same vertex. A graph is Eulerian if every vertex has an even degree; a semi-Eulerian graph has exactly two vertices of odd degree (start and end of the trail).
欧拉路径恰好经过图中的每条边一次。欧拉回路是起点和终点相同的闭合路径。如果一个图的所有顶点度数都是偶数，则该图是欧拉图；半欧拉图恰好有两个奇度顶点（路径的起点和终点）。
To find an Eulerian trail, begin at an odd-degree vertex (for semi-Eulerian) or any vertex (for Eulerian). At each step, choose an edge that is not a bridge unless no alternative exists. This is Fleury's algorithm, often examined by asking you to list the route or state if a trail exists.
要找到欧拉路径，从奇度顶点开始（半欧拉图），或在任意顶点开始（欧拉图）。每一步选择一条非桥的边，除非别无选择。这就是弗勒里算法，常考形式是列出路径或判断是否存在某条路径。
Example: the Konigsberg bridge problem is a classic. The CCEA exam may present a network of paths and ask: 'Can a postman walk every street without repeating any?' The answer depends on the parity of vertex degrees.
例子：哥尼斯堡七桥问题是经典的。CCEA 考试可能会给出一个路径网络并问：“邮递员能否不重复地走完每条街道？”答案取决于顶点度数的奇偶性。
6. Hamiltonian Graphs | 哈密顿图
A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle returns to the start. Unlike Eulerian, there is no simple condition to guarantee existence. For IGCSE, you mainly need to identify whether a given graph has a Hamiltonian cycle (e.g., by inspection) and understand its use in the travelling salesperson problem (TSP).
哈密顿路径恰好访问每个顶点一次；哈密顿回路又回到起点。与欧拉情形不同，没有简单的条件来保证其存在。对 IGCSE 而言，你主要需要辨认给定图是否有哈密顿回路（例如通过观察），并理解其在旅行商问题（TSP）中的应用。
A practical method is to try to list a cycle visiting all vertices. For small graphs, this is straightforward. The CCEA exam might ask: 'Is it possible to visit every town exactly once and return?' and then find the shortest such tour using nearest neighbour or other heuristics.
一种实用方法是尝试列出一个访问所有顶点的回路。对小图来说，这很简单。CCEA 考试可能会问：“是否可能恰好访问每个城镇一次并返回？”然后用最近邻法或其他启发式方法找出最短的此类环游。
7. Trees and Spanning Trees | 树与生成树
A tree is a connected graph with no cycles. Essential properties: n vertices, n−1 edges; any two vertices are connected by a unique path. A spanning tree of a graph is a subgraph that is a tree and includes all vertices. A minimum spanning tree (MST) minimises the total weight for a weighted graph.
树是一个无环的连通图。基本性质：n 个顶点，n−1 条边；任意两个顶点间有唯一路径。图的生成树是一个树状子图，包含所有顶点。最小生成树（MST）在带权图中最小化总权重。
To find an MST, use Prim's algorithm (grow from a starting vertex, always adding the cheapest edge connecting a new vertex) or Kruskal's algorithm (sort edges by weight, add if it doesn't create a cycle). CCEA may ask you to apply one of these and state the total weight.
要找到 MST，可使用普里姆算法（从起始顶点生长，总是加入连接新顶点的最便宜边）或克鲁斯卡尔算法（按权重排序边，若不会形成回路则加入）。CCEA 可能要求你应用其中一种算法，并写出总权重。
- Prim's: Choose any start vertex, select the smallest weight edge to a new vertex, repeat until all vertices are included. Break ties arbitrarily.
- 普里姆算法：选择任意起始顶点，选择连接新顶点的最小权重边，重复直到包含所有顶点。平局时任选。
- Kruskal's: List all edges in ascending weight order. Add each edge in turn, skipping those that would form a cycle, until you have n−1 edges.
- 克鲁斯卡尔算法：按权重升序列出所有边。依次添加边，跳过那些会形成环路的边，直到得到 n−1 条边。
8. Shortest Path Algorithms | 最短路径算法
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights. At each stage, you label vertices with temporary distances, permanently fixing the smallest tentative distance, then updating neighbours.
迪杰斯特拉算法在非负权重的有权图中找出从源顶点到所有其他顶点的最短路径。在每一步，你用临时距离标注顶点，永久固定最小的临时距离，然后更新邻居。
CCEA expects you to use the box method: at each vertex, record the order of permanent labelling, the shortest distance, and the previous vertex. You must show working boxes clearly. The exam may also ask for the route itself by tracing back from the destination.
CCEA 期望你使用格框法：在每个顶点处，记录永久标号的顺序、最短距离和前驱顶点。你必须清晰地展示工作框。考试也可能要求通过从目的地回溯来给出路线本身。
A → C → D → F with total weight 18. Always present final routes as a sequence of vertices.
示例：从 A 到 F，你可能找到路径 A → C → D → F，总权重为 18。最终路线总是以顶点序列的形式呈现。
9. Critical Path Analysis | 关键路径分析
Critical path analysis (CPA) helps schedule project activities with dependencies. An activity network (digraph) represents activities as edges (Activity on Arc) or vertices (Activity on Node). CCEA mainly uses the Activity on Arc (AoA) method, where edges are activities and vertices are events (start/end of activities).
关键路径分析（CPA）有助于调度具有依赖关系的项目活动。活动网络（有向图）将活动表示为边（弧表示活动）或顶点（节点表示活动）。CCEA 主要使用弧活动（AoA）表示法，其中边表示活动，顶点表示事件（活动的开始/结束）。
Key terms: earliest start time (EST) and latest finish time (LFT) of each event are computed via forward and backward passes. The critical path is the longest path through the network, determining the minimum project duration. Activities on the critical path have zero total float.
关键术语：每个事件的最早开始时间（EST）和最迟完成时间（LFT）通过正推和逆推计算。关键路径是贯穿网络的最长路径，决定了最短项目工期。关键路径上的活动总时差为零。
- vent = 0. For each subsequent event, EST = max(EST of predecessor + duration of activity).
- 正推：起始事件的 EST = 0。对每个后续事件，EST = max（前驱事件的 EST + 活动持续时间）。
- nt = its EST. For each previous event, LFT = min(LFT of successor − duration of activity).
- 逆推：结束事件的 LFT = 其 EST。对每个前驱事件，LFT = min（后继事件的 LFT − 活动持续时间）。
− EST of tail event − duration. Interpreting floats helps allocate resources efficiently.
总时差 = 头部事件的 LFT − 尾部事件的 EST − 持续时间。解读时差有助于有效分配资源。
10. Matching and Allocation | 匹配与分配问题
A matching in a bipartite graph assigns elements of one set to another. A maximal matching cannot have more edges added; a maximum matching has the largest possible number of edges. The Hungarian algorithm is not typically required at IGCSE, but CCEA may examine inspection methods on small bipartite graphs.
二部图中的匹配将一个集合的元素分配给另一个集合。极大匹配不能再添加边；最大匹配拥有尽可能多的边。IGCSE 通常不要求匈牙利算法，但 CCEA 可能会考查在小二部图上使用观察法。
Alternating paths from an unmatched vertex can improve a matching. You only need to be able to find a maximum matching by trial, and possibly state if a matching is complete (covers all vertices in the smaller set).
来自未匹配顶点的交错路径可以改进匹配。你只需能够通过试探找到最大匹配，并可能需判断匹配是否完全（覆盖较小集合的所有顶点）。
11. Practical Problem-Solving Strategies | 实际解题策略
When approaching a graph theory exam question, first identify the type: is it a route inspection (Eulerian), touring (Hamiltonian), shortest path (Dijkstra), connecting (MST), or scheduling (CPA) problem? Each requires a distinct method.
面对图论考试题时，首先要识别类型：是路径巡查（欧拉）、环游（哈密顿）、最短路径（迪杰斯特拉）、连接（MST）还是调度（CPA）问题？每种问题需要不同的方法。
Read the question carefully: are edges directed? Are weights given? Must you start or end at specific vertices? Use clear labelling and present steps logically. Practice drawing neat, large diagrams and writing matrices accurately.
仔细读题：边是有向的吗？给定了权重吗？是否必须在特定顶点开始或结束？使用清晰的标注并条理清楚地呈现步骤。练习画出整洁、足够大的图表，并准确书写矩阵。
12. Common Mistakes and Exam Tips | 常见错误与考试技巧
One common mistake is confusing Eulerian and Hamiltonian conditions. Remember: Eulerian depends on vertex degrees; Hamiltonian requires inspection. For Dijkstra, forgetting to update a working box can derail all subsequent distances. Double-check each step.
常见错误之一是混淆欧拉条件和哈密顿条件。记住：欧拉性取决于顶点度数；哈密顿性需要通过观察判断。对于迪杰斯特拉算法，忘记更新工作框可能导致所有后续距离出错。每一步都要仔细检查。
In critical path analysis, events are often drawn as nodes; ensure dummies (dotted arcs) are correctly used to preserve dependencies. When listing the critical path, include all consecutive events on the longest path. Always state the minimum duration explicitly.
在关键路径分析中，事件通常绘制为节点；确保正确使用虚活动（虚线弧）来保持依赖关系。列出关键路径时，包括最长路径上的所有连续事件。始终明确写出最短持续时间。
Finally, show all working. Even if the final answer is wrong, method marks are awarded. Manage time well—graph algorithms can be time-consuming, so practice until they are second nature.
最后，展示所有解题过程。即使最终答案有误，方法分依然可以获得。合理分配时间——图算法可能很耗时，因此要大量练习直到驾轻就熟。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图