5.4 图的矩阵表示

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

用矩阵表示图时,必须先固定顶点次序和边次序。关联矩阵以顶点为行、边为列;邻接矩阵和可达矩阵以起点为行、终点为列。矩阵形状、数值含义和运算方式不同,不能把三者互相替换。

定义5.4.1:无向图 的关联矩阵 ,其中 是顶点 与边 的关联次数。非环边在两个端点行各为1;环在同一个顶点行取2;其余为0。图中的平行边各有独立列,不能去重。

e1e2e3e4e5v1v2v3v4
图5.4.1:e1为v1上的环,e2、e3是v1与v2间的平行边,e4连接v1、v3,e5连接v3、v4。

按 为行、 为列,有

命题5.4.1:每列之和为2,每行之和为相应顶点的度,全部元素之和为 。不同两列相同,当且仅当相应边的无向端点完全相同,即为两条平行边;行和为0,当且仅当该顶点孤立。环所在列的2不能错误改成1,否则握手计数就会失败。

定义5.4.2:无环有向图的关联矩阵按本书约定,边的起点行填 ,终点行填 ,不关联填0。另一些文献使用反号约定,阅读时应看定义;本节不与其他符号约定混用。有向环被本定义排除,因为同一位置不能同时按这三个分支填写正负1;如需处理环,应明确采用额外约定。

e1e2e3e4e5v1v2v3v4
图5.4.2:v2到v1与v1到v2方向相反,v2指向v4,v3到v4有两条同向平行边。

按给定顶点、边次序,有

每列恰有一个 和一个 ,所以列和为0;两种非零项总数分别均为边数。某行 的个数为出度, 的个数为入度,行和为出度减入度。平行同向边的列相同,反向边的列互为相反数。不能将行和误读成总度。

定义5.4.3:有向图的邻接矩阵 ,其中 为从 指向 的边数。平行边对应大于1的整数,环记在主对角线上。第 行之和为 ,第 列之和为 ,全矩阵元素之和等于边数。

v1v2v3v4
图5.4.3:有向多重图,保留v1到v2的两条同向边,以及v4上的一个环。

该图的邻接矩阵为

定理5.4.1:普通整数矩阵幂 的第 项,是从 到 恰走 条边的通路数,允许重复边和顶点,并按边标号区分不同选择。主对角项是从对应顶点出发、恰走 步回到自身的回路数;全矩阵求和得到全部这类通路数,迹 得到全部回路数。这里按起点和行走顺序计数,不能直接当成不区分起点方向的几何圈个数。

证明: 正是邻接矩阵定义。长度 的通路有唯一的倒数第二顶点 ;先取一条到 的长 通路,再独立选择一条 到 的边,所以条数为 ,归纳完成。平行边在后一因子中计入不同选择,故不会被漏算。

推论5.4.1: 计数长度1到 的通路与回路,不包括零步的恒等通路。若需要包含长度0,再加单位矩阵 。普通整数乘法用于“有多少条”,此前关系的布尔乘法用于“是否存在”;把它们混用会丢失计数或产生错误矩阵。

对图5.4.3,逐次整数乘法得

例如 到 的1、2、3、4步通路分别为0、1、1、2条; 回到自身分别为1、2、3、5条。长度1至4的全部通路共有53条,其中回路15条;这些数字包含复杂通路,不能套用只许顶点不重复的路径计数。

定义5.4.4:可达矩阵 在 可达 时取1,否则取0。按上一节每点可达自身的约定,主对角线全为1,即使该点没有正长度回路。图5.4.2和图5.4.3的可达矩阵分别为

不同起终点的可达性只需考察不超过 步的路径。因此 时,将 的正数改为1、0保留,再把对角线设为1,即得到 ; 时直接为 。也可在布尔邻接矩阵上运行沃舍尔算法,并按本节规定加入恒等可达关系。

这里的可达矩阵与第2章正长度传递闭包存在一个关键区别:后者不自动包含全部自环,而本节的可达性允许零步,所以恒等对全部成立。不能为“统一格式”而把这两个不同定义的数据直接混成同一个。

无向图也可建立邻接与可达矩阵,并且它们对称;没有环时可把每条无向边视作两条反向有向边来作通路计数。本章若允许无向环,计数约定应另外说明:若一条环只计作一次可选边,则邻接矩阵对角项记环条数,行和就不再等于含环顶点的无向度;若为度数公式把对角项加倍,则矩阵幂计数会相应包含两种端点朝向的选择。必须选定一种解释,不能同时用前者计数和后者的度数公式。本节固定的无向关联矩阵仍一律对环填2,二者作用不同。