📚 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? | 为什么使用矩阵？
tices, 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 | 无向图的邻接矩阵
ns 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 通常使用简单有向图。
ire 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 | 距离矩阵与加权邻接矩阵
0. If there is no direct edge from i to j, the standard convention is to write ∞ or a dash '-'. Edexcel D1 often uses '-' nnection. 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
广告 / Sponsored正版全套3册 古琴考级曲集 上中下册 上海音乐出版社 上海音乐家协会考级系列丛书 古琴考级基础练习曲教材教程曲谱曲集书音乐 备考教辅 · 正版现货 · 学习备考通用查看详情 / View on Taobao参考价 ¥198.0广告 / Sponsored【新版】2026秋上册薛金星小学教材全解三五四六一二年级上册语文数学英语人教版北师大小学生同步讲解辅导资料解读课堂笔记数学 备考教辅 · 正版现货 · 学习备考通用查看详情 / View on Taobao参考价 ¥26.97
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图