Graphs and Networks: Edexcel A-Level Decision Mathematics | 图与网络：爱德思 A-Level 决策数学

📚 Graphs and Networks: Edexcel A-Level Decision Mathematics | 图与网络：爱德思 A-Level 决策数学

In Edexcel Decision Mathematics, graphs and networks are used to model practical problems such as finding the cheapest connecting route, the shortest journey or the most efficient inspection path. A graph is a collection of vertices joined by edges, and a network is a weighted graph in which each edge carries a number such as distance, time or cost. Mastering the core definitions and the standard algorithms is essential because exam questions often ask you to apply Kruskal, Prim or Dijkstra to a given diagram and to interpret the result.

在爱德思决策数学中，图与网络用于建模实际问题，例如寻找最便宜的连接路线、最短行程或最高效的检查路径。图是由边连接起来的顶点集合，而网络是带权图，其中每条边带有一个数字，如距离、时间或成本。掌握核心定义和标准算法至关重要，因为考试题经常要求你对给定图形应用 Kruskal、Prim 或 Dijkstra 算法并解释结果。

1. What Is a Graph? | 什么是图？

A graph G is defined by two sets: V, the set of vertices, and E, the set of edges. Each edge joins two vertices and can be drawn as a straight or curved line. In graph theory, the exact positions of vertices and the lengths of edges do not matter unless the graph is weighted; only the connections matter.

图 G 由两个集合定义：顶点集合 V 和边集合 E。每条边连接两个顶点，可以画成直线或曲线。在图论中，除非是带权图，顶点的具体位置和边的长度并不重要；只有连接关系才重要。

For example, a road network can be modelled by making towns into vertices and roads into edges. If every road has a known length, we write the length next to the edge and call the diagram a network.

例如，道路网络可以将城镇作为顶点、道路作为边来建模。如果每条道路都有已知长度，我们就把长度写在该边旁边，并将该图称为网络。

2. Key Terminology: Vertices, Edges and Degrees | 关键术语：顶点、边与度数

The degree of a vertex is the number of edges incident to it. A loop contributes 2 to the degree of its vertex because it meets the vertex twice. The handshaking lemma states that the sum of all vertex degrees equals 2 × the number of edges.

顶点的度数是指与该顶点相关联的边数。环对其顶点的度数贡献为 2，因为它与顶点相接两次。握手引理指出，所有顶点度数之和等于边数的 2 倍。

In a directed graph, every vertex has an in-degree and an out-degree. The in-degree counts edges arriving at the vertex, while the out-degree counts edges leaving it. These are important when modelling one-way streets or task dependencies.

在有向图中，每个顶点都有入度和出度。入度统计到达该顶点的边，而出度统计离开该顶点的边。这些在建模单行道或任务依赖关系时很重要。

You must also know the terms simple graph, multigraph, walk, path, trail, cycle and connected graph. A simple graph has no loops and no multiple edges between the same pair of vertices.

你还必须了解简单图、多重图、步道、路径、迹、回路和连通图等术语。简单图没有环，同一对顶点之间也没有多条边。

3. Types of Graphs | 图的类型

A simple graph is the most common starting point: no loops and at most one edge between any two vertices. A multigraph allows multiple edges or loops, which is useful in some network problems.

简单图是最常见的起点：没有环，任意两个顶点之间最多有一条边。多重图允许多条边或环，这在某些网络问题中很有用。

A directed graph, or digraph, has each edge marked with an arrow. It is used to model flows, one-way streets or precedence relations. A weighted graph, often called a network, has a number on each edge representing cost, time or distance.

有向图，又称 digraph，每条边都标有箭头。它用于建模流量、单行道或先后关系。带权图，通常称为网络，每条边上有一个数字，表示成本、时间或距离。

Complete graph Kₙ has every pair of vertices joined by exactly one edge, so it has n(n −

Published by TutorHao | A-Level Revision Series | aleveler.com

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