Representing Graphs and Networks Using Matrices | 用矩阵表示图与网络

📚 Representing Graphs and Networks Using Matrices | 用矩阵表示图与网络

Graphs and networks are fundamental concepts in discrete mathematics, used to model relationships, connections, and routes. An efficient way to represent these structures for computational analysis is by using matrices. This article explores adjacency matrices and distance matrices, showing how to construct them from graph diagrams and how to interpret their entries to solve problems such as finding the number of walks or shortest paths.

图与网络是离散数学中的基本概念，用于建模关系、连接和路径。用矩阵来表示这些结构是一种高效的计算分析方法。本文将探讨邻接矩阵和距离矩阵，展示如何根据图形构造矩阵，以及如何解释矩阵中的元素，从而解决诸如求步数或最短路径等问题。

1. Graphs and Networks Overview | 图与网络概述

A graph consists of vertices (or nodes) connected by edges (or arcs). In an undirected graph, edges have no direction; in a directed graph (digraph), each edge has an arrow indicating direction. Networks extend graphs by assigning weights (e.g., distances, times, capacities) to edges. These structures can be conveniently encoded in matrices.

图由顶点（节点）和连接它们的边（弧）组成。在无向图中，边没有方向；在有向图中，每条边用箭头指示方向。网络通过为边赋予权重（如距离、时间、容量）对图进行扩展。这些结构可以方便地用矩阵编码。

---

2. Adjacency Matrix for Undirected Graphs | 无向图的邻接矩阵

an edge. For an undirected graph with n vertices, we create an n × n matrix M. The entry m_ij (row i, column j) is 1 if there is an edge between vertex i and vertex j, and 0 otherwise. Since the graph is undirected, the matrix is symmetric: m_ij = m_ji. A loop (an edge connecting a vertex to itself) is represented by a 1 on the main diagonal.

邻接矩阵记录哪些顶点之间直接有边相连。对于包含 n 个顶点的无向图，我们构建一个 n × n 矩阵 M。如果顶点 i 和顶点 j 之间有边，则元素 m_ij（第 i 行第 j 列）为 1，否则为 0。由于图是无向的，矩阵是对称的：m_ij = m_ji。自环（连接顶点自身的边）用主对角线上的 1 表示。

For example, consider vertices A, B, C with edges AB and AC. The adjacency matrix is shown below. Notice the symmetry and the row sums: A has degree 2, B and C have degree 1.

例如，考虑顶点 A、B、C，边 AB 和 AC，邻接矩阵如下。注意矩阵的对称性及行和：A 的度为 2，B 和 C 的度为 1。

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

---

3. Adjacency Matrix for Directed Graphs | 有向图的邻接矩阵

In a directed graph, the adjacency matrix is not necessarily symmetric. If there is an arc from vertex i to vertex j, we put a 1 in row i, column j. A 0 indicates no direct arc. The matrix can now have different entries for m_ij and m_ji as 1 on the diagonal. For a digraph with vertices 1→2, 2→3, 3→1, the matrix is asymmetric.

在有向图中，邻接矩阵不一定对称。如果存在从顶点 i 到顶点 j 的弧，我们在第 i 行第 j 列填 1；0 表示没有直接弧。此时 m_ij 和 m_ji 可能取值不同。自环在对角线上用 1 表示。对于一个有向图，顶点 1→2，2→3，3→1，其矩阵是非对称的。

	1	2	3
1	0	1	0
2	0	0	1
3	1	0	0

ice that row 1 sum = 1 (out-degree of vertex 1), column 1 sum = 1 (in-degree of vertex 1).

注意，第 1 行和为 1（顶点 1 的出度），第 1 列和为 1（顶点 1 的入度）。

---

广告 / Sponsored

4. Distance Matrix (Weight Matrix) | 距离矩阵（权重矩阵）

When edges have weights, we use a distance matrix (or weight matrix). For a network with n vertices, the matrix D has entries d_ij r a dash, depending on convention. For undirected weighted networks, the matrix is symmetric. Distance matrices are essential for algorithms like Floyd's or Dijkstra's for shortest path problems.

当边具有权重时，我们使用距离矩阵（或称权重矩阵）。对于包含 n 个顶点的网络，矩阵 D 的元素 d_ij 等于 i 与 j 之间边的权重。若无直接边，根据惯例，该元素可记为 ∞（无穷大）或横线。对于无向加权网络，该矩阵是对称的。距离矩阵对于最短路径问题的 Floyd 算法或 Dijkstra 算法至关重要。

ces A, B, C and weighted edges AB=5, AC=3, BC=2 (no direction) yields the distance matrix:

例如，包含顶点 A、B、C 且边权重为 AB=5、AC=3、BC=2 的无向网络，其距离矩阵为：

	A	B	C
A	–	5	3
B	5	–	2
C	3	2	–

placed with ∞ during computation, but for clarity in exams use a consistent dash notation.

计算时虚线可用 ∞ 代替，但在考试中为确保清晰，常统一使用横线符号。

---

5. Constructing Matrices from Diagrams | 从图形构造矩阵

To build an adjacency matrix from a graph diagram, label the vertices clearly. Decide on an order (usually alphabetical or numerical). Then fill in the matrix row by row, placing 1 where an edge exists. For distance matrices, replace 1 with the given weight and use a suitable symbol for non-adjacent pairs. Double-check symmetry for undirected cases.

要根据图形构建邻接矩阵，需要明确标注顶点，确定顺序（通常按字母或数字顺序），然后逐行填写矩阵，在存在边的位置填 1，否则填 0。对于距离矩阵，将 1 替换为给定权重，并用适当符号表示不相邻的顶点对。对于无向情况，务必检查对称性。

A systematic approach: list vertices as row and column headers, then mark each edge in both directions (for undirected) or as directed. This reduces errors when dealing with larger graphs.

一种系统的方法是：先列出所有顶点作为行列标题，然后对每条边在无向图中双向标记，在有向图中按方向标记。这能在处理较大图形时减少错误。

---

6. Interpreting Matrix Entries | 解释矩阵元素

The sum of a row in an adjacency matrix gives the degree of that vertex (number of edges connected to it) for undirected graphs. For directed graphs, row sum equals out-degree, column sum equals in-degree. In a distance matrix, reading a row shows the direct distances from that vertex to all others; the smallest non-zero entry indicates the nearest neighbour.

在无向图的邻接矩阵中，某行的和等于该顶点的度（连接到它的边的数目）。对于有向图，行和等于出度，列和等于入度。在距离矩阵中，读取某行可以显示从该顶点到所有其他顶点的直接距离；最小的非零元素表示最近邻。

Additionally, a zero matrix (all entries 0) represents a graph with no edges. A complete graph on n vertices has an adjacency matrix with 0 on the diagonal and 1 everywhere else. These patterns help in quick identification.

此外，全零矩阵表示没有边的图。n 个顶点的完全图，其邻接矩阵对角线全为 0，其余位置全为 1。这些模式有助于快速识别。

---

7. Powers of the Adjacency Matrix | 邻接矩阵的幂

A powerful property: the (i,j) entry of M^k (the k-th power of the adjacency matrix M) gives the number of walks of length k from vertex i to vertex j. For example, M² tells us how many walks of length 2 exist between each pair of vertices. This is useful for checking connectivity and finding routes in networks with multiple steps.

一个强大的性质：M^k（邻接矩阵 M 的 k 次幂）的 (i,j) 元素给出了从顶点 i 到顶点 j 长度恰好为 k 的步数。例如，M² 能告诉我们每对顶点之间长度为 2 的步数。这对于检查连通性以及在需要多步的网络中寻找路径非常有用。

Consider M for vertices A–B–C chain (undirected). M² and the reverse, but in an undirected graph a walk can repeat vertices, so A→B→C and A→B→C? e distinct sequence: A-B-C if vertices are distinct, but since walks allow revisiting, A-B

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

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