Modelling with Graphs: Constructing and Analysing Networks | 图的建模：网络的构建与分析

📚 Modelling with Graphs: Constructing and Analysing Networks | 图的建模：网络的构建与分析

Graph theory provides a powerful language for describing relationships and structures. In A‑level Decision Mathematics, modelling with graphs allows us to represent real‑world situations – transport links, communication networks, project tasks, or even social connections – as abstract diagrams of vertices and edges. By stripping away unnecessary detail, graph models become the starting point for optimisation algorithms that find efficient routes, minimise costs, or plan projects.

图论提供了一种描述关系和结构的强大语言。在 A‑level 决策数学中，图的建模使我们能够将现实世界的情况——交通连接、通信网络、项目任务甚至社交联系——表示为抽象的顶点和边的图。通过去掉不必要的细节，图模型成为优化算法的起点，这些算法可以找到高效路线、最小化成本或规划项目。

1. Introduction to Graph Modelling | 图建模简介

Modelling with graphs involves translating a real problem into a graph consisting of points (vertices) joined by lines (edges). This abstraction highlights the connections that matter while ignoring physical distances or shapes. For example, a road map can be modelled as a graph where towns are vertices and roads are edges. Once the graph is drawn, algorithms can be applied to answer questions such as the cheapest connection or the quickest journey.

图建模涉及将实际问题转化为由点（顶点）和连线（边）组成的图。这种抽象突显重要的连接关系，而忽略物理距离或形状。例如，公路地图可以建模为一个图，其中城镇是顶点，道路是边。一旦图形被画出，就可以应用算法来回答例如最便宜的连接或最快的行程等问题。

2. Vertices, Edges and Loops | 顶点、边和环

A graph is defined by its vertex set V and edge set E. An edge connects two vertices and can be drawn as a straight or curved line. A loop is a special edge that starts and ends at the same vertex. The degree of a vertex is the number of edges incident to it, counting a loop twice. Understanding these basic elements is essential before moving on to more complex graph types.

一个图由其顶点集 V 和边集 E 定义。一条边连接两个顶点，可以画成直线或曲线。环是一条特殊的边，它从同一个顶点开始并结束。顶点的度是与它关联的边的数量，环计算两次。在进入更复杂的图类型之前，理解这些基本元素至关重要。

3. Directed and Undirected Graphs | 有向图与无向图

In an undirected graph, edges have no orientation: they simply represent a two‑way relationship. Most road networks can be treated as undirected if all roads are two‑way. In contrast, a directed graph (digraph) uses arrows on edges to indicate one‑way movement, such as one‑way streets or flow of materials in a supply chain. Mixed graphs contain both directed and undirected edges.

在无向图中，边没有方向性：它们仅仅表示双向关系。如果所有道路都是双向的，大多数道路网络可以视为无向图。相反，有向图（有向图）利用边上的箭头指示单向移动，例如单行道或供应链中的物料流动。混合图包含有向边和无向边两种类型。

4. Weighted Graphs and Networks | 加权图与网络

When numbers (weights) are assigned to edges, the graph becomes a weighted graph or network. Weights can represent distance, time, cost, or capacity. A network provides the extra information needed to solve optimisation problems. For instance, in a delivery network, the weight on an edge might be the driving time in minutes, allowing the calculation of the total journey time.

当数字（权值）被赋予给边时，图就成为加权图或网络。权值可以表示距离、时间、成本或容量。网络提供了解决优化问题所需的额外信息。例如，在配送网络中，边上的权值可能是以分钟计的驾驶时间，从而可以计算总的行程时间。

5. Adjacency Matrices | 邻接矩阵

directly connected. For an undirected graph with n vertices, we use an n×n matrix where a ‘1’ indicates an edge and ‘ For a weighted graph, the matrix entries become the weights, with a special symbol such as ‘–’ or ‘ djacency matrices are useful for computer processing but do not show the visual structure.

邻接矩阵是一个正方形表格，记录哪些顶点直接相连。对于具有 n 个顶点的无向图，我们使用一个 n×n 矩阵，其中‘1’表示有边，‘0’表示无边。对于加权图，矩阵条目变为权值，缺席的边则用特殊符号如‘–’或‘∞’表示。邻接矩阵便于计算机处理，但不显示视觉结构。

	A	B	C
A	0	1	0
B	1	0	1
C	0	1	0

For the simple undirected graph with vertices A, B, C where A is connected to B and B to C, the adjacency matrix is shown above. A '1' appears in row A, column B and row B, column A, reflecting the two‑way connection.

对于具有顶点 A、B、C 的简单无向图，A 与 B 相连，B 与 C 相连，邻接矩阵如上所示。在 A 行 B 列以及 B 行 A 列出现 ‘1’，反映了双向连接。

广告 / Sponsored

6. Distance Matrices | 距离矩阵

A distance matrix records the lengths of shortest paths between all pairs of vertices. Unlike the adjacency matrix, it is not restricted to direct edges; it gives the minimum total weight between any two vertices, taking indirect routes into account. This matrix can be constructed after running shortest path algorithms such as Dijkstra's.

距离矩阵记录了所有顶点对之间最短路径的长度。与邻接矩阵不同，它不局限于直接边；它给出了任意两个顶点之间的最小总权值，考虑了间接路线。该矩阵可以在运行诸如迪杰斯特拉的最短路径算法后构建。

7. Connectivity and Paths | 连通性与路径

A graph is connected if there is a path between every pair of vertices. A path is a sequence of edges that visits vertices without repeating any. Understanding connectivity is vital when modelling: if a network is not connected, some components cannot be reached from others. In algorithms, we often work with connected graphs to ensure a solution exists for all vertices.

如果一个图的每一对顶点之间都存在一条路径，则该图是连通的。路径是一个边的序列，它访问顶点但不重复任何顶点。在建模时理解连通性至关重要：如果网络不连通，有些部分无法从其他部分到达。在算法中，我们通常处理连通图，以确保所有顶点都存在解。

8. Trees and Spanning Trees | 树与生成树

A tree is a connected graph with no cycles. A spanning tree of a graph is a subgraph that includes all vertices, is connected, and contains exactly n−1 edges for n vertices. Spanning trees are central to network design because they provide the minimum number of edges to keep a network connected, eliminating redundant links.

树是一个无环的连通图。一个图的生成树是一个子图，它包含所有顶点，是连通的，并且对于 n 个顶点恰好包含 n−1 条边。生成树是网络设计的核心，因为它们提供保持网络连通所需的最少边数，消除了冗余连接。

9. Minimum Spanning Trees: Prim’s Algorithm | 最小生成树：普里姆算法

Prim’s algorithm builds a minimum spanning tree (MST) by growing a tree from an arbitrary start vertex. At each step, it adds the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree. This greedy approach guarantees an MST when all edge weights are non‑negative. The algorithm is efficient for dense graphs and can be tracked using a priority table.

普里姆算法通过从任意起始顶点开始生长一棵树来构建最小生成树 (MST)。在每一步中，它添加最便宜的边，该边连接树中已有的一个顶点和尚未在树中的一个顶点。当所有边权非负时，这种贪心方法可以保证得到 MST。该算法对密集图效率高，并且可以使用优先权值表进行跟踪。

10. Minimum Spanning Trees: Kruskal’s Algorithm | 最小生成树：克鲁斯卡尔算法

Kruskal’s algorithm sorts all edges by weight and adds them one by one, skipping those that would create a cycle. It continues until a spanning tree includes all vertices. Kruskal’s method works well on sparse graphs and is conceptually simpler, making it a favourite in exam problems. Both Prim’s and Kruskal’s algorithms produce an MST of minimum total weight.

克鲁斯卡尔算法将所有边按权值排序，并逐一添加，跳过那些会形成环的边。它持续进行直到生成树包含所有顶点。克鲁斯卡尔方法在稀疏图上效果好，概念上更简单，使其成为考试题目中的常见算法。普里姆和克鲁斯卡尔算法都能产生总权值最小的 MST。

11. Shortest Path: Dijkstra’s Algorithm | 最短路径：迪杰斯特拉算法

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non‑negative weights. The algorithm maintains a set of ‘solved’ vertices and repeatedly updates tentative distances for neighbours. A common approach uses a labelling box with order of labelling, final distance, and working values. Once all vertices are labelled, the shortest path tree is complete.

迪杰斯特拉算法在具有非负权值的加权图中，找到从源顶点到所有其他顶点的最短路径。该算法维护一组“已解”顶点，并不断更新邻居的临时距离。一种常见方法使用标签框，包括标签顺序、最终距离和工作值。一旦所有顶点都被标记，最短路径树就完成了。

Working values update: min(current distance, distance via new permanent vertex)

工作值更新：min(当前距离, 经新永久顶点的距离)

12. Real-World Modelling with Graphs | 现实世界中的图建模

Graphs model a staggering range of real situations: road and rail networks, airline routes, internet data flow, pipe systems, and even timetabling constraints. The classic Chinese Postman Problem (route inspection) asks for the shortest walk that traverses every edge at least once; the Travelling Salesperson Problem seeks the shortest cycle visiting every vertex exactly once. Both rely on graph theory and algorithmic thinking to produce practical solutions.

图可以模拟极为广泛的实际情况：道路和铁路网络、航线、互联网数据流、管道系统，甚至时间表约束。经典的中国邮递员问题（路线检查）要求找到至少遍历每条边一次的最短步行路线；旅行商问题则寻求访问每个顶点恰好一次的最短回路。这两者都依赖于图论和算法思维来产生实用的解决方案。

The power of modelling with graphs lies not in drawing pictures, but in the disciplined conversion of a messy problem into a clean mathematical structure that can be solved systematically. Mastering the definitions and standard algorithms gives you a toolkit for tackling unseen problems in Decision Mathematics 1 and beyond.

图建模的力量不在于画图，而在于将杂乱的问题有纪律地转化为可以系统求解的清晰数学结构。掌握定义和标准算法，就为你提供了一套工具包，用于解决决策数学 1 及更高层次中未曾见过的问题。

Published by TutorHao | Decision Mathematics 1 Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）