📚 Modelling with Graphs | 图论建模
Graphs are a central tool in Edexcel A-Level Decision Mathematics. A graph is not a chart or a statistical plot; it is an abstract structure made of vertices and edges that can model connections, routes, networks and relationships. Understanding how to build and interpret graphs is essential before studying algorithms such as Kruskal's, Prim's and Dijkstra's.
图是 Edexcel A-Level 决策数学中的核心工具。图不是图表或统计图，而是一种由顶点和边组成的抽象结构，可以用来模拟连接、路线、网络和关系。在学习 Kruskal、Prim 和 Dijkstra 等算法之前，理解如何建立和解释图是至关重要的。
1. What is a Graph? | 什么是图？
en as G = (V, E). Vertices are also called nodes, and edges are also called arcs or lines.
图 G 由一个有限的顶点集 V 和一个边集 E 组成，其中每条边连接两个顶点。它通常写作 G = (V, E)。顶点也称为节点，边也称为弧或线。
A simple graph has no loops and no multiple edges between the same pair of vertices. A loop is an edge that starts and ends at the same vertex. A graph with multiple edges is called a multigraph.
简单图没有环，也没有同一对顶点之间的多条边。环是起点和终点为同一顶点的边。含有多条重边的图称为多重图。
In modelling, vertices usually represent objects, locations or people, while edges represent the relationships or connections between them. For example, vertices could be towns and edges could be roads linking those towns.
在建模中，顶点通常表示对象、位置或人员，而边表示它们之间的关系或连接。例如，顶点可以是城镇，边可以是连接这些城镇的道路。
2. Vertices, Edges and Degree | 顶点、边与度数
The degree of a vertex is the number of edges incident to it, that is, the number of edges that touch that vertex. A loop contributes 2 to the degree because it touches the vertex twice.
顶点的度数是与该顶点相关联的边的数量，也就是接触到该顶点的边的数目。一个环对该顶点的度数贡献 2，因为它两次接触到该顶点。
of all vertices in a graph is exactly twice the number of edges. In symbols, Σ deg(v) = 2|E|. A direct consequence is that every graph has an even number of vertices with odd degree.
握手引理指出，图中所有顶点的度数之和恰好等于边数的两倍。用符号表示为 Σ deg(v) = 2|E|。一个直接推论是，每个图中具有奇度数的顶点个数为偶数。
s degrees A = 3, B = 2, C = 2, D = 1, and the total degree is 8, which equals 2 × 4 edges.
例如，由顶点 A、B、C 和边 AB、AC、BC 组成的三角形，其度序列为 2、2、2。如果从 A 向新顶点 D 添加一条边，则度数为 A = 3、B = 2、C = 2、D = 1，总度数为 8，等于 2 × 4 条边。
3. Paths, Cycles and Connectedness | 路径、圈与连通性
A path is a sequence of edges that connects a sequence of distinct vertices. The length of a path is the number of edges it contains. For example, in a graph with edges AB, BC, CD, the sequence A-B-C-D is a path of length 3.
路径是连接一系列不同顶点的边的序列。路径的长度是它所包含的边的数量。例如，在一个具有边 AB、BC、CD 的图中，序列 A-B-C-D 是一条长度为 3 的路径。
A cycle, sometimes called a circuit, is a closed path that starts and ends at the same vertex and does not repeat any other vertices or edges. A cycle must have length at least 3 in a simple graph.
圈，有时称为回路，是一条闭合路径，起点和终点为同一顶点，且不重复任何其他顶点或边。在简单图中，圈的长度至少为 3。
A graph is connected if there is a path between every pair of vertices. If a graph is not connected, it can be split into connected components, which are maximal connected subgraphs.
如果图中任意两个顶点之间都存在路径，则图是连通的。如果图不连通，它可以被划分为连通分量，即极大的连通子图。
When modelling a delivery route, a path represents a journey that does not revisit any location, while a cycle represents a round trip that returns to the starting point.
在对配送路线进行建模时，路径表示不重复经过任何地点的行程，而圈表示返回起点的往返行程。
4. Trees and Spanning Trees | 树与生成树
A tree is a connected graph that contains no cycles. A tree with n vertices always has exactly n − 1 edges. This property makes trees fundamental for modelling minimal connection problems.
树是没有圈的连通图。具有 n 个顶点的树恰好有 n − 1 条边。这一性质使树成为建模最小连接问题的基本工具。
A forest is a graph with no cycles, but it may be disconnected. A forest with n vertices and k connected components has n − k edges.
森林是没有圈的图，但它可能是不连通的。具有 n 个顶点和 k 个连通分量的森林有 n − k 条边。
A spanning tree of a connected graph is a subgraph that contains all the vertices of the original graph and is itself a tree. A spanning tree therefore has exactly |V| − 1 edges.
连通图的生成树是包含原图所有顶点并且本身是一棵树的子图。因此，生成树恰好有 |V| − 1 条边。
A minimum spanning tree, or MST, is a spanning tree with the smallest possible total edge weight. It is found using Kruskal's algorithm or Prim's algorithm, both of which are standard Edexcel Decision Mathematics topics.
最小生成树（MST）是总边权尽可能小的一棵生成树。它可以通过 Kruskal 算法或 Prim 算法求得，这两者都是 Edexcel 决策数学的标准考点。
5. Directed Graphs and Digraphs | 有向图
A directed graph, or digraph, has edges with a direction indicated by an arrow. Each directed edge is an ordered pair, so the edge from u to v is written as (u, v) and is not the same as (v, u).
有向图（digraph）的边带有箭头指示的方向。每条有向边是一个有序对，因此从 u 到 v 的边写作 (u, v)，它与 (v, u) 不是同一条边。
In a digraph, each vertex has an out-degree, the number of arcs leaving it, and an in-degree, the number of arcs entering it. The sum of all out-degrees equals the sum of all in-degrees, and both equal the number of arcs.
在有向图中，每个顶点有一个出度，即离开它的弧数，以及一个入度，即进入它的弧数。所有出度之和等于所有入度之和，并且两者都等于弧的数量。
Directed graphs are used to model one-way streets, electrical currents, water flow, task precedence in project planning, and many other systems where direction matters.
有向图用于对单行道、电流、水流、项目规划中的任务优先关系以及许多其他方向很重要的系统进行建模。
For example, if task A must be completed before task B can start, this precedence is represented by a directed arc from A to B, not from B to A.
例如，如果任务 A 必须在任务 B 开始之前完成，则该优先关系由一条从 A 到 B 的有向弧表示，而不是从 B 到 A。
6. Weighted Graphs and Networks | 加权图与网络
A weighted graph assigns a number, called a weight, to each edge. Weights can represent distance, time, cost, capacity, load, or any measurable quantity relevant to the problem.
加权图为每条边分配一个称为权重的数字。权重可以表示距离、时间、成本、容量、负载或任何与问题相关的可测量量。
When a graph is used to model real infrastructure such as roads, cables, or pipelines, it is often called a network. A network is usually a weighted graph, and it may be directed or undirected.
当图用于对道路、电缆或管道等真实基础设施进行建模时，它通常被称为网络。网络通常是加权图，它可以是有向的，也可以是无向的。
The three main optimisation problems on weighted graphs are the shortest path problem, solved by Dijkstra's algorithm; the minimum spanning tree problem, solved by Kruskal's or Prim's algorithm; and the maximum flow problem, solved by flow-augmenting methods.
加权图上的三大优化问题是最短路径问题（由 Dijkstra 算法求解）、最小生成树问题（由 Kruskal 或 Prim 算法求解）以及最大流问题（由增流方法求解）。
When reading a network diagram, always check whether weights are written on the edges and whether arrows indicate directed arcs before choosing an algorithm.
在阅读网络图时，在选择算法之前，务必检查边上是否写有权重，以及箭头是否表示有向弧。
7. Matrix Representations | 矩阵表示
A graph can be represented by an adjacency matrix. For n vertices labelled 1 to n, the entry in row i and column j gives the number of edges from vertex i to vertex j. For a simple undirected graph, the matrix is symmetric and all diagonal entries are 0.
图可以用邻接矩阵表示。对于标记为 1 到 n 的 n 个顶点，第 i 行第 j 列的元素给出了从顶点 i 到顶点 j 的边数。对于简单无向图，矩阵是对称的，并且所有对角元素都为 0。
Consider a triangle with vertices 1, 2, 3 and edges 12, 23, 31. Its adjacency matrix is:
考虑一个顶点为 1、2、3，边为 12、23、31 的三角形。其邻接矩阵为：
0 1 1
1 0 1
1 1 0
The row sum in a simple adjacency matrix equals the degree of that vertex. This gives a quick way to check degrees from a matrix representation.
简单邻接矩阵中的行和等于该顶点的度数。这提供了一种从矩阵表示中快速检查度数的方法。
An incidence matrix has rows for vertices and columns for edges. Entry is 1 if the vertex is incident with that edge, and 0 otherwise. A distance matrix records the shortest distance or direct weight between each pair of vertices.
关联矩阵的行对应顶点，列对应边。如果顶点与该边相关联，则元素为 1，否则为 0。距离矩阵记录每对顶点之间的最短距离或直接权重。
Matrices are useful when inputting graphs into software or when a question asks you to compare two graphs using their structural data.
当需要将图输入软件，或者题目要求使用结构数据比较两个图时，矩阵非常有用。
8. Graph Isomorphism | 图的同构
Two graphs are isomorphic if there is a one-to-one correspondence between their vertex sets that preserves adjacency. In other words, the two graphs have exactly the same structure, but the vertices may be labelled differently.
如果两个图的顶点集之间存在保持相邻关系的一一对应，则这两个图是同构的。换句话说，这两个图具有完全相同的结构，但顶点的标记可能不同。
Isomorphic graphs must have the same number of vertices, the same number of edges, and the same degree sequence. However, these conditions alone are not sufficient to guarantee isomorphism.
同构图必须具有相同的顶点数、相同的边数和相同的度序列。然而，仅凭这些条件并不足以保证同构。
A degree sequence is the list of vertex degrees arranged in non-increasing order. For example, a graph with degrees 1, 3, 2, 2 has degree sequence (3, 2, 2, 1).
度序列是按非递增顺序排列的顶点度数的列表。例如，一个度数为 1、3、2、2 的图，其度序列为 (3, 2, 2, 1)。
To prove two graphs are not isomorphic, find a structural property that differs, such as the number of cycles of a given length, the number of connected components, or whether one is bipartite and the other is not.
要证明两个图不同构，可以找出不同的结构性质，例如特定长度的圈的数量、连通分量的数量，或者一个图是二分图而另一个不是。
9. Modelling Real-World Problems | 现实问题建模
To build a graph model, first list the objects you want to connect. These become vertices. Then decide which pairs are directly related or linked. Those become edges. If the relationship has direction, use a digraph. If there is a measurable quantity associated with each link, add weights.
要建立图模型，首先列出你要连接的对象，它们成为顶点。然后确定哪些对直接相关或相连，它们成为边。如果关系有方向，则使用有向图。如果每个链接都有可测量的量，则添加权重。
Example 1: five towns are joined by roads. Let vertices be the towns and edges be the roads. Assign each edge a weight equal to the distance in km. A minimum spanning tree gives the shortest total road length needed to keep all towns connected without cycles.
示例 1：五个城镇由道路连接。设顶点为城镇，边为道路。为每条边赋权为以 km 为单位的距离。最小生成树给出了在无圈条件下保持所有城镇连通所需的最短道路总长度。
Example 2: a building project has tasks with prerequisites. Let vertices represent the tasks and directed arcs represent precedence. Adding activity durations as weights allows a critical path analysis to determine the minimum completion time.
示例 2：一个建筑项目有若干任务及先决条件。设顶点表示任务，有向弧表示优先关系。将活动持续时间作为权重，可以通过关键路径分析确定最短完成时间。
Example 3: a social network. Let vertices be people and edges represent friendship. The degree of a vertex is the number of friends that person has, and connectivity describes chains of acquaintances through the network.
示例 3：社交网络。设顶点为人，边表示友谊关系。顶点的度数是该人拥有的朋友数量，连通性描述了网络中熟人链的情况。
10. Common Exam Pitfalls | 常见考试失分点
Do not confuse a graph with a chart, a line graph, or a scatter plot. In Decision Mathematics, a graph means vertices and edges. Many marks are lost by ignoring this distinction.
不要将图与图表、折线图或散点图混淆。在决策数学中，图指的是顶点和边。忽视这一区别会丢掉很多分数。
Remember that a tree is connected and has exactly n − 1 edges. However, a graph with n − 1 edges is not automatically a tree unless it is also connected. A disconnected graph with no cycles is a forest.
请记住，树是连通的，并且恰好有 n − 1 条边。但是，具有 n − 1 条边的图不一定就是树，除非它也是连通的。没有圈的不连通图是森林。
When constructing an adjacency matrix, pay attention to whether the graph is directed or undirected. For an undirected graph the matrix must be symmetric; for a directed graph the row sum gives out-degree and the column sum gives in-degree.
在构造邻接矩阵时，要注意图是有向的还是无向的。对于无向图，矩阵必须是对称的；对于有向图，行和给出
Published by TutorHao | A-Level Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图