📚 Graphs and Networks | 图与网络
Graphs and networks lie at the heart of decision mathematics, providing powerful tools for modelling connections, optimising routes, scheduling projects, and analysing flows. In the Edexcel A-Level further maths specification, this topic develops your ability to think algorithmically and apply structured methods to real-world problems.
图与网络是决策数学的核心，为建立连接模型、优化路径、规划项目和分析流量提供了强大的工具。在Edexcel A-Level进阶数学大纲中，这一主题培养你用算法思维和结构化方法解决实际问题的能力。
1. What is a Graph? | 什么是图？
A graph consists of a set of vertices (also called nodes) and a set of edges (or arcs) that connect pairs of vertices. Graphs can represent roads, computer networks, social connections, and many other structures where objects are linked.
图由一组顶点（亦称节点）和一组连接顶点对的边（或弧）构成。图可以表示道路、计算机网络、社交关系以及许多其他对象相连的结构。
Vertices are usually shown as points, and edges as lines or curves joining them. If the order of connection matters, the graph is directed and its edges are called arcs, drawn as arrows. If not, it is an undirected graph.
顶点通常表示为点，边表示为连接它们的线段或曲线。如果连接顺序重要，图就是有向的，其边称为弧，用箭头绘制；否则为无向图。
2. Graph Terminology | 图的相关术语
A vertex is said to have a degree (or valency), which is the number of edges incident to it. In a directed graph, we distinguish in-degree and out-degree.
一个顶点有一个度（或价），即与其相连的边的数目。在有向图中，我们区分入度和出度。
A path is a sequence of edges that connects a sequence of vertices without repeating vertices. A cycle (or circuit) is a closed path where the start and end vertex are the same and no other vertex repeats. A graph is connected if there is a path between every pair of vertices; otherwise it is disconnected.
路径是一系列边，连接一系列顶点且不重复顶点。圈（回路）是起点和终点相同且中间顶点不重复的闭合路径。如果任意两顶点间都有路径，则该图是连通的；否则是不连通的。
A tree is a connected graph with no cycles. A spanning tree of a graph is a subgraph that is a tree and includes all the vertices of the original graph.
树是连通且无圈的图。一个图的生成树是这样一棵树：它是该图的子图且包含原图所有顶点。
3. Types of Graphs | 图的类型
A simple graph has no loops and no multiple edges between the same pair of vertices. A complete graph Kn is a simple graph where every pair of vertices is connected by exactly one edge.
简单图没有环和重边（相同顶点对之间的多条边）。完全图 Kn 是一个简单图，其中每对顶点之间恰好有一条边相连。
A bipartite graph is one whose vertices can be split into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other. A weighted graph has numbers (weights) assigned to its edges, representing distances, costs, or times.
二部图的顶点可划分为两个不相交的集合，使得每条边都从一个集合的顶点连到另一个集合的顶点。赋权图的边上标有数字（权重），表示距离、成本或时间。
4. Representing Graphs with Matrices | 用矩阵表示图
An adjacency matrix trix where the entry in row i, column j is the number of edges from vertex i to vertex j. For a simple graph, entries are 0 or 1, and the matrix is symmetric if the graph is undirected.
对于有n个顶点的图，邻接矩阵是一个n×n矩阵，其中第i行第j列的元素是从顶点i到顶点j的边数。对于简单图，元素为0或1，且若为无向图，矩阵是对称的。
An incidence matrix relates vertices to edges: it has rows representing vertices and columns representing edges. Entry (i, j) is 1 if vertex i is incident to edge j, and 0 otherwise. For directed graphs, +1 can be used for the start of an arc and −1 for the end.
关联矩阵将顶点与边关联：行表示顶点，列表示边。若顶点i与边j相关联，则元素(i, j)为1，否则为0。对于有向图，可用+1表示弧的起点，−1表示终点。
| A | B | C | |
| A | 0 | 1 | 0 |
| B | 1 | 0 | 1 |
| C | 0 | 1 | 0 |
The adjacency matrix is compact and useful for computer representation; incidence matrices are helpful when edges have identities themselves.
邻接矩阵紧凑且便于计算机表示；当边具有自身标识时，关联矩阵更加有用。
5. Minimum Spanning Trees – Kruskal’s Algorithm | 最小生成树——Kruskal算法
A minimum spanning tree (MST) connects all vertices of a weighted, connected graph with the minimal total edge weight. Kruskal’s algorithm builds the MST by considering edges in ascending order of weight.
最小生成树（MST）以最小的总边权连接赋权连通图的所有顶点。Kruskal算法通过按权重升序考虑边来构造最小生成树。
Sort all edges in order of increasing weight.
将所有边按权重递增顺序排序。
Select the edge with the smallest weight and add it to the tree, unless it would form a cycle with the edges already chosen. If it would, reject it.
选择权重最小的边加入树中，除非它会与已选的边形成圈。如果会形成圈，则舍弃。
Repeat until you have included exactly (n – 1) edges, where n is the number of vertices.
重复上述步骤直到恰好包涵 (n – 1) 条边，其中n为顶点数。
Kruskal’s algorithm is efficient and easy to apply, especially when edges are pre-sorted or presented in a table.
Kruskal算法高效且易于应用，尤其在边已排序或以表格形式呈现时。
6. Minimum Spanning Trees – Prim’s Algorithm | 最小生成树——Prim算法
Prim’s algorithm builds the MST by starting from any chosen vertex and repeatedly adding the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree.
Prim算法通过选择任意起始顶点，并反复添加连接树内顶点与树外顶点的最便宜边来构造最小生成树。
Start with any vertex; mark it as part of the tree.
从任意顶点开始；将其标记为树的一部分。
Among all edges that connect a tree vertex to a non-tree vertex, pick the one with the smallest weight. Add that edge and the new vertex to the tree.
在所有连接树内顶点和树外顶点的边中，选择权重最小的一条。将该边和新顶点加入树中。
Repeat until all vertices are included.
重复直到所有顶点都被包含。
Prim’s algorithm can be implemented in matrix form using a distance table, which is useful when the graph is dense.
Prim算法可用距离表以矩阵形式实现，当图较为稠密时十分有用。
7. Dijkstra’s Shortest Path Algorithm | Dijkstra最短路径算法
Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. It uses a labelling method and permanent/temporary labels.
Dijkstra算法在边权非负的图中找出从源顶点到所有其他顶点的最短路径。它使用标号法和永久/临时标号。
Steps: Assign the start vertex a permanent label of 0 and all others a temporary label of infinity. From the current permanently labelled vertex, update temporary labels of all directly reachable vertices if a shorter distance is found. Then choose the smallest temporary label, make it permanent, and repeat until all vertices are permanent.
步骤：为起点分配永久标号0，其他顶点临时标号无穷大。从当前永久标号顶点出发，更新所有可直接到达顶点的临时标号（若找到更短距离）。然后选择最小的临时标号使其永久，并重复直到所有顶点均永久化。
The algorithm also records the preceding vertex to reconstruct the shortest path. A table is often used to track labels and working values.
该算法还会记录前驱顶点，以便重建最短路径。常用表格跟踪标号和工作值。
8. The Route Inspection (Chinese Postman) Problem | 路线检查（中国邮递员）问题
The route inspection problem asks for the shortest closed walk that traverses every edge of a graph at least once. If the graph is Eulerian (all vertices have even degree), an Eulerian circuit exists and is the optimal route.
路线检查问题要求找出至少遍历每条边一次的最短闭合回路。如果图是欧拉图（所有顶点度数为偶数），则存在欧拉回路，即为最优路线。
If there are odd-degree vertices, the graph must have an even number of them. The solution involves pairing odd vertices and duplicating the shortest paths between them, making a new graph where all degrees are even. The total length is the original total weight plus the sum of the shortest paths between paired odd vertices.
若有奇度数顶点，其个数必为偶数。解决方法是将奇度数顶点配对，并复制它们之间的最短路径，构造一个所有度数为偶数的新图。总长度为原总权重加上配对奇顶点间最短路径之和。
Finding the optimal pairing is done by considering all possible pairings and choosing the one with minimal extra distance.
通过考虑所有可能的配对方式并选择附加距离最小的配对，可找到最优配对。
9. Introduction to Critical Path Analysis | 关键路径分析导论
Critical path analysis (CPA) is a project management technique that models tasks as activities on a directed, acyclic network. Each activity has a duration and dependency relationships.
关键路径分析（CPA）是一种项目管理技术，将任务建模为有向无环网络中的活动。每项活动有耗时和依赖关系。
In the activity-on-node convention, nodes represent activities; arcs show precedence. An activity cannot start until all its immediate predecessors are complete. The network starts at a source node and ends at a sink node.
在节点表示活动（AON）的方式中，节点代表活动，箭头表示先后关系。一项活动只有在所有紧前活动完成后才能开始。网络从一个源节点开始，到一个汇节点结束。
10. Forward and Backward Pass, Floats and Critical Path | 正推逆推，浮动与关键路径
A forward pass calculates the earliest start time (EST) and earliest finish time (EFT) for each activity, moving left to right. The project duration is the EFT of the final activity.
正推法从左到右计算每项活动的最早开始时间（EST）和最早完成时间（EFT）。项目工期为最后活动的EFT。
A backward pass calculates the latest finish time (LFT) and latest start time (LST) moving right to left, starting with the project duration as the LFT for the sink. The total float for an activity is (LFT – EFT) or (LST – EST).
逆推法从右到左计算最晚完成时间（LFT）和最晚开始时间（LST），以项目工期作为汇节点的LFT开始。活动的总浮动时间为 (LFT – EFT) 或 (LST – EST)。
Activities with zero total float are critical; they form the critical path(s). Any delay on these activities directly delays the whole project. Gantt charts can visually show float and scheduling.
总浮动时间为零的活动是关键活动，它们构成关键路径。这些活动的任何延误都将直接延误整个项目。甘特图可以直观地展示浮动时间和排程。
EST(i) = max{EFT of all predecessors}
LFT(i) = min{LST of all successors}
Total Float = LFT – EFT
最早开始时间 EST(i) = 所有紧前活动EFT的最大值
最晚完成时间 LFT(i) = 所有后续活动LST的最小值
总浮动时间 = LFT – EFT
Careful analysis of floats helps resource levelling and crashing, enabling managers to shorten projects at minimum extra cost.
仔细分析浮动时间有助于资源平衡和赶工，使管理者能以最小额外成本缩短项目工期。
Published by TutorHao | Decision Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图