📚 GCSE CCEA Maths: Graph Theory Key Points | GCSE CCEA 数学：图论考点精讲
Graph theory is a branch of mathematics that deals with networks of points connected by lines. In CCEA GCSE Maths, graph theory questions often appear in the context of decision mathematics, testing your ability to model real-world situations and apply algorithms to find optimal solutions. Mastering key definitions, algorithms like Kruskal’s, Prim’s and Dijkstra’s, and understanding tree properties is essential for success.
图论是研究由点和线连接而成的网络的数学分支。在 CCEA GCSE 数学中，图论题目常出现在决策数学背景下，考察你将实际问题建模并使用算法寻找最优解的能力。掌握关键定义、Kruskal、Prim 和 Dijkstra 算法以及树的性质是取得高分的关键。
1. What is a Graph? | 图是什么？
A graph G is a mathematical structure consisting of a set of vertices V (also called nodes) and a set of edges E joining pairs of vertices. Graphs provide a visual way to represent connections such as roads between towns, friendship links on social media or pipelines in a utility network.
图 G 是由顶点集 V（也称节点）和连接顶点对的边集 E 构成的数学结构。图以直观方式呈现各种连接，例如城镇之间的道路、社交媒体上的好友链接或公共事业管网。
An edge may have a direction (making the graph directed) or no direction (undirected). In CCEA exams, most graphs are undirected and weighted, where each edge carries a numerical weight representing distance, time or cost.
边可以带有方向（有向图）或无方向（无向图）。CCEA 考试中绝大多数图是无向加权图，每条边附带一个数值权重，代表距离、时间或成本。
2. Vertices, Edges and Degrees | 顶点、边与度
The degree of a vertex is the number of edges incident to it. A loop (an edge connecting a vertex to itself) contributes 2 to the degree. In an undirected graph, the sum of degrees of all vertices equals twice the total number of edges. This is known as the Handshaking Lemma.
度是顶点关联的边数。自环（连接顶点自身的边）贡献 2。在无向图中，所有顶点的度数之和等于边数的两倍，这称为握手引理。
Sum of degrees = 2 × number of edges
度数和 = 2 × 边数
For example, if a graph has 4 vertices with degrees 2, 3, 3 and 2, the sum is 10, so there must be exactly 5 edges. In directed graphs we speak of in-degree (arrows coming in) and out-degree (arrows going out), but these are less common in CCEA graph theory questions.
例如，若某图有 4 个顶点，度数分别为 2、3、3 和 2，总和为 10，因此必须有 5 条边。有向图中区分入度（进入的箭头）和出度（发出的箭头），但 CCEA 图论考题较少涉及。
3. Simple Graphs, Complete Graphs and Subgraphs | 简单图、完全图与子图
A simple graph has no loops and at most one edge between any pair of vertices. A complete graph, denoted Kn, is a simple graph in which every possible pair of distinct vertices is joined by an edge. K3 is a triangle, K4 has 6 edges, and so on.
简单图没有自环，且任意两顶点之间至多有一条边。完全图，记作 Kn，是一种简单图，其中任意两个不同顶点之间都由一条边相连。K3 是一个三角形，K4 有 6 条边，依此类推。
A subgraph is obtained by selecting a subset of vertices and edges from the original graph. Subgraphs are central to the idea of a spanning tree – we take all vertices but only some of the edges to create a tree.
子图是从原图中选取部分顶点和边而形成的图。子图是生成树概念的核心——我们保留所有顶点，仅选用部分边构成树。
4. Paths, Cycles and Connectivity | 路径、回路与连通性
A walk is a sequence of edges. A trail is a walk with no repeated edges; a path is a trail with no repeated vertices. A cycle (or circuit) is a closed path – it starts and ends at the same vertex and has at least one edge, with no other repeated vertices.
行走是边的序列。迹是没有重复边的行走；路径是没有重复顶点的迹。回路（或称环）是一个闭合路径——起点与终点重合，至少包含一条边，且没有其他重复顶点。
A graph is connected if there is a path between every pair of vertices. If a graph is disconnected, it splits into connected components. Many algorithms, such as Prim’s or Dijkstra’s, require the graph to be connected.
如果任意两顶点之间都存在路径，则图是连通的。若图不连通，它会分裂成若干个连通分支。许多算法，如 Prim 算法和 Dijkstra 算法，要求图是连通的。
5. Trees and Spanning Trees | 树与生成树
A tree is a connected graph with no cycles. In a tree with n vertices, there are exactly n – 1 edges. Adding any new edge creates exactly one cycle; removing any edge disconnects the tree. A forest is a disjoint collection of trees.
树是不含回路的连通图。n 个顶点的树恰好有 n – 1 条边。添加任一边都恰好产生一个回路；删除任一边都会使树不连通。林是互不相交的树的集合。
A spanning tree of a connected graph is a subgraph that includes all the vertices of the original graph and is a tree. A connected graph may have many different spanning trees. Finding one with the minimum total weight is the goal of minimum spanning tree algorithms.
连通图的生成树是包含该图所有顶点的一棵树。一个连通图可以有多个不同的生成树。寻找总权重最小的生成树正是最小生成树算法的目标。
6. Minimum Spanning Tree – Kruskal’s Algorithm | 最小生成树—— Kruskal 算法
Kruskal’s algorithm selects edges in order of increasing weight, avoiding cycles, until exactly n – 1 edges have been chosen.
Kruskal 算法按权重升序选择边，避免形成回路，直到恰好选出 n – 1 条边。
-
List all edges in ascending order of weight.
将所有边按权重升序排列。
-
Pick the edge with the smallest weight that does not form a cycle with the edges already selected. Add it to the tree.
选取权重最小且不与已选边构成回路的边，将其加入树中。
-
Repeat step 2 until n – 1 edges have been chosen.
重复步骤 2，直到选出 n – 1 条边。
You can use a priority list or sort the edges in a table. A cycle is formed if both ends of the new edge are already connected through previously selected edges. If two edges have the same weight, you may choose either, but in CCEA exams follow the instruction (often choose alphabetical order of vertices).
你可以使用优先列表或将边在表格中排序。若新边的两个端点通过之前选中的边已经连通，则形成回路。如果多条边权重相同，可以任选其一，但 CCEA 考试通常要求按字母顺序选择（注意题意）。
7. Minimum Spanning Tree – Prim’s Algorithm | 最小生成树—— Prim 算法
Prim’s algorithm grows a tree from an arbitrary starting vertex, repeatedly adding the cheapest edge that connects the tree to a vertex not yet in the tree.
Prim 算法从任意起点出发，逐步“生长”一棵树，不断将连接树内顶点与树外顶点的最便宜边加入。
-
Start by choosing any vertex. Mark it as ‘in the tree’.
先任选一个顶点，标记为“在树内”。
-
Look at all edges connecting a tree vertex to a non-tree vertex. Pick the one with the smallest weight and add that vertex and edge to the tree.
检查所有连接树内顶点与树外顶点的边，选取权重最小的边，将该顶点和边加入树。
-
Repeat until all vertices are in the tree.
重复以上步骤，直到所有顶点都在树内。
Prim’s algorithm can be implemented using a table or by building the tree directly on the network diagram. It always yields the same total weight as Kruskal’s, though the edges selected may differ when there are ties.
Prim 算法既可通过表格实现，也可直接在网络图上操作。Prim 算法得到的总权重与 Kruskal 算法相同，但在有权重相等的情况下，所选边可能不同。
8. Shortest Path – Dijkstra’s Algorithm | 最短路径—— Dijkstra 算法
Dijkstra’s algorithm finds the shortest path from a start vertex to every other vertex in a weighted graph with non-negative edge weights. It uses labels (distance, previous vertex) that are updated as the algorithm progresses.
Dijkstra 算法在边权非负的加权图中找出从起点到所有其他顶点的最短路径。它使用标号（距离，前驱顶点），并在算法推进中不断更新。
-
Assign a distance of 0 to the start vertex and ∞ to all others. Make the start vertex the ‘current vertex’.
给起点标距离 0，其余顶点标距离 ∞。将起点设为“当前顶点”。
-
For each unvisited neighbour of the current vertex, calculate the tentative distance = (distance to current) + weight of edge. If this is smaller than the recorded distance, update it and note the current vertex as the previous vertex.
Published by TutorHao | GCSE Mathematics Revision Series | aleveler.com更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导