图的矩阵表示

贡献者：零穹

预备知识　图，矩阵及其运算

　　将图的点集和边集的关系用矩阵来体现，就是所谓的图的矩阵表示。体现点与点相邻关系的矩阵称为邻接矩阵；体现点与边关联关系的矩阵称为关联矩阵。当对某个图选定了权函数成为赋权图时，体现权函数的矩阵称为赋权矩阵。

1. 邻接矩阵

　　邻接矩阵是用来体现点点相邻关系的，具体地，设图 $G$ 的点集为 $V (G) = {v_{1}, \dots, v_{n}}$ 。若 $G$ 是无向图，则邻接矩阵的第 $(i, j)$ 个元反映了连接 $v_{i}, v_{j}$ 的边数。若 $G$ 是有向图，则邻接矩阵的第 $(i, j)$ 个元反映了以 $v_{i}$ 为起点， $v_{j}$ 为终点的有向边数。

定义 1　邻接矩阵

　　设 $G$ 是图， $V (G) = {v_{1}, \dots, v_{n}}$ ， $A = (a_{i j})$ 是 $n$ 阶矩阵。若 $G$ 是无向图， $a_{i j}$ 等于连接 $v_{i}, v_{j}$ 的边数；若 $G$ 是有向图， $a_{i j}$ 等于以 $v_{i}$ 为起点， $v_{j}$ 为终点的有向边数。则称 $A$ 为 $G$ 的邻接矩阵（adjacency matrix）。

定理 1　

　　设 $A$ 是有向图 $G$ 的邻接矩阵， $V (G) = {v_{1}, \dots, v_{n}}$ 。则 $A^{k}$ 中的第 $(i, j)$ 元是 $G$ 中长度为 $k$ 的从 $v_{i}$ 到 $v_{j}$ 的有向链的数目。

　　 证明： 使用数学归纳法证明如下：当 $k = 1$ 是，由邻接矩阵 $A$ 的定义（定义 1 ）和链长的定义（定义 1 ），可知定理成立；

　　设 $k = l$ 时定理成立，那么当 $k = l + 1$ 时，设 $a_{i j}^{(l)}, a_{i j}^{(l + 1)}$ 分别是 $A^{l}, A^{l + 1}$ 的 $(i, j)$ 元。由于 $A^{l} = A^{l - 1} A$ ，所以

\begin{matrix} (1) & a_{i j}^{(l + 1)} = \sum_{m = 1}^{n} a_{i m}^{(l)} a_{m j} . \end{matrix}

由假设，

a_{i m}^{(l)}

是从

v_{i}

到

v_{m}

的长为

l

的有向链数，

a_{m j}

是从

v_{m}

到

v_{j}

的长为

l

的有向链数，于是

a_{i m}^{(l)} a_{m j}

是从

V_{i}

到

v_{m}

再到

v_{j}

的长为

l + 1

的有向链数。而所有从

v_{i}

到

v_{j}

的长为

l + 1

的有向链，都是从

v_{i}

到某个

v_{x}

的长为

l

的有向链与

v_{x}

到

v_{j}

的长为 1 的有向链连接构成。

　　因此若记 $A_{m}$ 是从 $V_{i}$ 到 $v_{m}$ 再到 $v_{j}$ 的长为 $l + 1$ 的所有有向链的全体，而 $A$ 记为从 $V_{i}$ 到 $v_{j}$ 的长为 $l + 1$ 的所有有向链的全体，那么

\begin{matrix} (2) & A = ⋃_{m = 1}^{n} A_{m} . \end{matrix}

显然

A_{a} \cap A_{b} = \emptyset, a \neq b

，因此

\begin{matrix} (3) & | A | = \sum_{m = 1}^{n} | A_{m} | . \end{matrix}

而

| A_{m} | = a_{i m}^{(l)} a_{m j}

。因此定理得证。

　　 证毕！

　　这一定理对无向图也是成立的，证明类似。

2. 关联矩阵

　　关联矩阵是用来体现点边的关联关系的，具体地，设图 $G$ 的点集和边集分别为

\begin{matrix} (4) & V (G) = {v_{1}, \dots, v_{n}}, E (G) = {e_{1}, \dots, e_{m}} . \end{matrix}

若

G

是无向图，则关联矩阵的第

(i, j)

个元反映了

v_{i}, e_{j}

是否关联。若

G

是有向图，则关联矩阵的第

(i, j)

个元反映了以

v_{i}

是

e_{j}

的起点还是终点。为方便使用 Mathematica 软件进行图论计算起见，我们这里使用 Mathematica 关于图的关联矩阵定义

定义 2　关联矩阵

　　设 $G$ 是图， $V (G) = {v_{1}, \dots, v_{n}}, E (G) = {e_{1}, \dots, e_{m}}$ ， $A = (a_{i j})$ 是 $n \times m$ 的矩阵。若

\begin{matrix} (5) & a_{i j} = {\begin{aligned} 0, & v_{i} \notin e_{j}, \\ 1, & e_{j} = (*, v_{i}) o r {v_{i}, v_{k}}, i \neq k \\ - 1, & e_{j} = (v_{i}, *), \\ 2, & e_{j} = (v_{i}, v_{i}) \end{aligned} \end{matrix}

则称

A

为

G

的关联矩阵（incidence matrix）。

例 1　

　　设有图 $G = (V, E, φ)$ ，其中

\begin{matrix} (6) & \begin{aligned} V = {v_{1}, v_{2}, v_{3}}, E = {e_{1}, e_{2}, e_{3}, e_{4}, e_{5}}, \\ φ (e_{1}) = (v_{1}, v_{1}), φ (e_{2}) = (v_{1}, v_{1}), \\ φ (e_{3}) = (v_{1}, v_{2}), φ (e_{4}) = (v_{2}, v_{1}), φ (e_{5}) = {v_{1}, v_{2}} . \end{aligned} \end{matrix}

其中我们定义的

e_{1}, e_{2}

尽管都是

(v_{1}, v_{2})

，但是在 mathematica 中可以将它表示为有向环和无向环¹，因此可以用它们演示 mathematica 中它们在关联矩阵中对应的元是相同的。该图具有如下的表示

图 1：例子图的表示

　　那么由关联矩阵定义，该图的关联矩阵为

\begin{matrix} (7) & (\begin{matrix} 2 & 2 & - 1 & 1 & 1 \\ 0 & 0 & 1 & - 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}) . \end{matrix}

　　该例的 Mathematica 代码如下，其表明关联矩阵和我们的定义一致。

图 2：代码及结果展示

定理 2　

　　设 $M$ 是图的关联矩阵，则 $M M^{T}$ 的 $(i, j)$ 元为

\begin{matrix} (8) & n_{i j} = {\begin{aligned} d_{G} (v_{i}) + 2 r = d_{G}^{+} (v_{i}) + d_{G}^{- 1} (v_{i}) + 2 r, & i = j, \\ - μ (v_{i}, v_{j}) - μ (v_{j}, v_{i}) + ν (v_{i}, v_{j}), & i \neq j . \end{aligned} \end{matrix}

其中

μ (v_{i}, v_{j})

表示以

v_{i}

为起点

v_{j}

为终点的边数，

ν (v_{i}, v_{j})

是以

v_{i}, v_{j}

为端点的无向边个数。且

M M^{T}

的第

i

行和

i

列元素之和为

\begin{matrix} (9) & 4 r + 2 N_{i} . \end{matrix}

其中

N_{i}

是过

v_{i}

的无向边数。

　　 证明： 设 $N = M M^{T}$ ，由于当对某个 $k$ 而言， $M_{i k} M_{j k}$ 在 $i \neq j$ 时，当是有向边 $e_{k}$ 的两端点时为 -1，当是无向边 $e_{k}$ 的两端点时 1；而 $M_{i k} M_{i k}$ 为 $e_{k}$ 的端点且 $e_{k}$ 不是环时为 1，是环时为 4。因此 $\sum_{k = 1}^{| E (G) |} M_{i k} M_{j k}, i \neq j$ 表示以 $v_{i}, v_{j}$ 为端点的边数的负值+该点上 4 倍的环数， $\sum_{k = 1}^{| E (G) |} M_{i k} M_{i k}$ 表示以 $v_{i}$ 为端点的边数加上 3 倍的环数，即该点的度加 2 倍的环数。因此，若设 $r$ 是过点 $v_{i}$ 的环数，则有

\begin{matrix} (10) & n_{i j} = {\begin{aligned} d_{G} (v_{i}) + 2 r_{i} = d_{G}^{+} (v_{i}) + d_{G}^{- 1} (v_{i}) + 2 r_{i}, & i = j, \\ - μ (v_{i}, v_{j}) - μ (v_{j}, v_{i}) + ν (v_{i}, v_{j}), & i \neq j . \end{aligned} \end{matrix}

其中

r_{i}

是过

v_{i}

的环数，

μ (v_{i}, v_{j})

表示以

v_{i}

为起点

v_{j}

为终点的边数，

ν (v_{i}, v_{j})

是以

v_{i}, v_{j}

为端点的无向边个数。由

N

的定义知

N

是对称的。且

\begin{matrix} (11) & \begin{aligned} \sum_{j = 1}^{| V |} n_{i j} & = d_{G} (v_{i}) + 2 r - \sum_{j = 1, j \neq i}^{| V |} (μ (v_{i}, v_{j}) + μ (v_{j}, v_{i}) - ν (v_{i}, v_{j})) \\ = d_{C} (v_{i}) + 2 r - (d_{G} (v_{i}) - 2 r) + 2 \sum_{j = 1, j \neq i}^{| V |} ν (v_{i}, v_{j}) \\ = 4 r + 2 \sum_{j = 1, j \neq i}^{| V |} ν (v_{i}, v_{j}) . \end{aligned} \end{matrix}

证毕！

例 2　

　　对例 1 的图，有 $d (v_{1}) = 7, d (v_{2}) = 3, d (v_{3}) = 0$ ，由定理 2 ，可以看出它的关联矩阵和其转置的乘积为

\begin{matrix} (12) & (\begin{matrix} 11 & - 1 & 0 \\ - 1 & 3 & 0 \\ 0 & 0 & 0 \end{matrix}) . \end{matrix}

使用定理 2 的结果计算行和得：第一行和为

4 * 2 + 2 * 1 = 10

，第 2 行为

1

，第 3 行为 0。由上面的矩阵可验证这是一致的。

3. 赋权矩阵

　　赋权矩阵是用来体现赋权函数的，其有不同的定义方式。例如，设图 $G$ 的点集为 $V (G) = {v_{1}, \dots, v_{n}}$ ，则赋权矩阵是一个 $n$ 阶矩阵。若 $G$ 为有向图，则其第 $(i, j)$ 个元反映了以 $v_{i}$ 为起点 $v_{j}$ 为终点的所有边的权值之和；若 $G$ 为无向图，则其第 $(i, j)$ 个元反映了连接 $v_{i}, v_{j}$ 的所有边的权值之和。

定义 3　赋权矩阵

　　若 $G$ 是图， $ω$ 是其上的权函数。则给出权函数的矩阵称为赋权矩阵。

1. ^ 在某些现实的意义上其不是等价的，比如一条以 $a$ 为端点的环，规定只能逆时针走，那么它就是单向的，而若双向可走则才等价于无向环，此时应当由表示顺时针和逆时针的记号进行方向的标记，比如"-"，即 $(- a, a)$ 表示逆时针， $(a, - a)$ 表示逆时针。这都是定义的问题，仅仅为了一一对应我们关心的问题，没有标准的表示，只要符合表达了对应关系即可，但是为了方便往往会约定某一种习惯定义，正如我们习惯了集合用花括号定义

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

图的矩阵表示

1. 邻接矩阵

定义 1 邻接矩阵

定理 1

2. 关联矩阵

定义 2 关联矩阵

例 1

定理 2

例 2

3. 赋权矩阵

定义 3 赋权矩阵

定义 1　邻接矩阵

定理 1　

定义 2　关联矩阵

例 1　

定理 2　

例 2　

定义 3　赋权矩阵