📚 Representing Graphs and Networks Using Matrices | 用矩阵表示图与网络
Graphs and networks are central to Edexcel Decision Mathematics 1. A graph can be drawn as a set of vertices connected by edges, but to process it with algorithms or to check properties such as connectivity and shortest paths, we need a compact algebraic form. Matrices provide exactly that: an adjacency matrix records which vertices are joined, a distance matrix records weighted lengths, and an incidence matrix records which edges meet which vertices. This article explains how to build and interpret these matrices, with exam-style examples.
图与网络是 Edexcel Decision Mathematics 1 的核心内容。图可以画成由边连接的一组顶点，但要用算法处理或检查连通性、最短路径等性质，就需要紧凑的代数形式。矩阵恰好提供了这种工具：邻接矩阵记录哪些顶点相连，距离矩阵记录加权长度，关联矩阵记录每条边与哪些顶点相接。本文讲解如何建立和解释这些矩阵，并配有考试风格例题。
1. Why use matrices? | 为什么使用矩阵？
In Edexcel D1, a graph or network is often given visually. However, many algorithms – such as finding shortest paths, counting routes or checking connectedness – become simpler if the graph is stored as a matrix. A matrix is a rectangular array of numbers with rows and columns; for a graph with n vertices, we use an n × n matrix. The three most common matrix representations are the adjacency matrix, the distance matrix and the incidence matrix.
在 Edexcel D1 中，图或网络通常以图形方式给出。但许多算法——例如求最短路径、统计路线数量或检查连通性——如果把图存储为矩阵就会变得更简单。矩阵是一个由行和列组成的矩形数字阵列；对于有 n 个顶点的图，我们使用 n × n 矩阵。三种最常见的矩阵表示是邻接矩阵、距离矩阵和关联矩阵。
2. Key terms and conventions | 关键术语与约定
A graph consists of vertices, also called nodes, and edges, also called arcs in a directed graph. 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 directed graph, or digraph, has edges with a direction, drawn with arrows. A network is a graph with weights, such as distances, times or costs, on its edges.
图由顶点（也叫节点）和边（有向图中也叫弧）组成。简单图没有环，也没有连接同一对顶点的多条边。环是从一个顶点出发回到自身的边。有向图（digraph）的边具有方向，用箭头表示。网络是边上带有权重（如距离、时间或成本）的图。
3. Adjacency matrix of an undirected graph | 无向图的邻接矩阵
For an undirected simple graph with n vertices, the adjacency matrix is an n × n matrix A. Label the rows and columns in the same vertex order. The entry in row i and column j is 1 if there is an edge between vertex i and vertex j, and 0 otherwise. Since edges are undirected, the entry in row i, column j equals the entry in row j, column i, so A is symmetric. The main diagonal is all 0 because a simple graph has no loops.
对于有 n 个顶点的无向简单图，邻接矩阵是一个 n × n 矩阵 A。行和列按相同的顶点顺序标注。若顶点 i 与顶点 j 之间有一条边，则第 i 行第 j 列的元素为 1，否则为 0。由于边是无向的，第 i 行第 j 列的元素等于第 j 行第 i 列的元素，所以 A 是对称矩阵。主对角线全为 0，因为简单图没有环。
For example, the complete graph K₃ with vertices A, B, C has adjacency matrix:
例如，顶点为 A、B、C 的完全图 K₃ 的邻接矩阵为：
| A | B | C | |
|---|---|---|---|
| A | 0 | 1 | 1 |
| B | 1 | 0 | 1 |
| C | 1 | 1 | 0 |
The symmetry is clear: each 1 above the diagonal has a matching 1 below it.
对称性很明显：对角线上方的每个 1 在下方都有一个对应的 1。
4. Adjacency matrix of a directed graph | 有向图的邻接矩阵
For a digraph, the entry in row i and column j is 1 if there is a directed edge from vertex i to vertex j. The matrix is not necessarily symmetric. A loop at vertex i makes the entry in row i, column i equal to 1. Always read row as ‘from’ and column as ‘to’. If a graph has multiple edges in the same direction, some versions record the number of edges instead of just 1, but Edexcel D1 usually uses simple digraphs.
对于有向图，若存在从顶点 i 到顶点 j 的有向边，则第 i 行第 j 列的元素为 1。矩阵不一定对称。顶点 i 处的环使第 i 行第 i 列的元素等于 1。始终把行读作“从”，把列读作“到”。如果同方向有多条边，有些版本记录边的数量而不是 1，但 Edexcel D1 通常使用简单有向图。
For example, if there is an edge A → B, put 1 in row A, column B. The reverse edge B → A is a separate edge and would require a 1 in row B, column A. This distinction is essential when modelling one-way roads or directed flows.
例如，如果有一条边 A → B，则在 A 行 B 列放 1。反向边 B → A 是另一条边，需要在 B 行 A 列放 1。在建立单向道路或有向流动模型时，这种区分至关重要。
5. Distance matrix and weighted adjacency matrix | 距离矩阵与加权邻接矩阵
In a network, each edge has a weight. The distance matrix D is an n × n matrix where the entry in row i, column j is the weight of the edge from i to j, and the diagonal entries are 0. If there is no direct edge from i to j, the standard convention is to write ∞ or a dash ‘-‘. Edexcel D1 often uses ‘-‘ to mean no direct connection. For an undirected network, D is symmetric; for a directed network it may not be.
在网络中，每条边都有一个权重。距离矩阵 D 是一个 n × n 矩阵，其中第 i 行第 j 列的元素是从 i 到 j 的边的权重，对角线元素为 0。如果从 i 到 j 没有直接边，通常约定写 ∞ 或“-”。Edexcel D1 常用“-”表示没有直接连接。对于无向网络，D 是对称的；对于有向网络，则不一定对称。
Distance matrices are used directly by algorithms such as Dijkstra’s shortest path algorithm. They give a compact summary of immediate connections, while dashes show where a path cannot be completed in one step.
距离矩阵直接用于 Dijkstra 最短路径等算法。它简洁地汇总了直接连接，而“-”表示无法一步完成路径的位置。
Published by TutorHao | A-Level Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导