邻接矩阵

在图论中，邻接矩阵（英語：）是表示一种图结构的常用表示方法。它用数字方阵记录各点之间是否有边相连，数字的大小可以表示边的权值大小。

距離矩陣可算是鄰接矩陣的擴充。

定义

階為 $n$ 的圖 $G$ 的鄰接矩陣 $A$ 是 $n\times n$ 的。將 $G$ 的頂點標籤為 $v_{1},v_{2},...,v_{n}$ 。若 $(v_{i},v_{j})\in E(G)$ ， $A_{ij}=1$ ，否則 $A_{ij}=0$ 。也可以用大于0的值表示边的权值，例如可以用边权值表示一个点到另一个点的距离。[1]

无向图的鄰接矩陣是對稱矩陣。

例子

例1

可以用矩阵表示为：

{\begin{bmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{bmatrix}}

例2

典型的邻接矩阵

这个矩阵中每一行代表一个点，行a即为点a，每一列代表某一行的点所指向的点，矩阵的每一个（小格）表示一条边。图中的所有边（指向性的箭头）带有权值，通常约定权值为0的边为不存在的边。

如此图中的a指向b，箭头旁边的数字（边的权值）为2，在矩阵中表示为行a列b为2。又如矩阵中行c列b为6，图中表现为一条从c指向b权值为6的边。

特性

設圖 $G$ 的鄰接矩陣為 $A$ ，边的取值为1。

如果顶点有自我连接产生的自环（loop），则在矩阵的主对角线上会有非零的值；如果没有自环，则主对角线上全部是0。
$A^{n}$ 的元素 $A_{ij}^{n}$ 可以表示由頂點 $i$ 到頂點 $j$ 長度為 $n$ 的徑的數目。[2]
$G$ 沒有有向圈若且唯若 $I-A$ 可逆。 $(I-A)^{-1}$ 的元素 $ij$ 表示由頂點 $i$ 到頂點 $j$ 的所有徑的數目。因為： $(I-A)^{-1}=I+A+A^{2}+A^{3}+...$

应用

传球问题

A、B、C、D四人传球6次，从A开始，最终回到A手里，有多少种传法？

非矩阵解法：

m个人传n次球， $\sum _{i=1}^{[{\frac {n}{2}}]}(m-1)^{i}(m-2)^{n-2i}C_{n-1-i}^{i-1}$ [3]
$(m-1)P_{n+1}=1-P_{n},P_{n}={\frac {1}{m}}(1-({\frac {-1}{m-1}})^{n-1})$ ，将P_n乘上总传法数 $(m-1)^{n-1}$ [3]

矩阵解法：

$A={\begin{bmatrix}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\\\end{bmatrix}},A^{6}={\begin{bmatrix}183&182&182&182\\182&183&182&182\\182&182&183&182\\182&182&182&183\\\end{bmatrix}}$

图论算法的计算机实践

邻接矩阵法是比较简单的图论问题建模方法，它以方形二维阵列的形式存储图的数据。它在算法应用中的主要特点包括：

各元素的取值与边的输入顺序无关。[1]
利用输入数据建图之前，因为不一定每对点之间都有边相连，所以先要执行将所有边的权值设为无效值的初始化步骤。以此法建模有 $n$ 个点和 $m$ 条边的图，其初始化需要 $O(n^{2})$ 的时间复杂度，建图的时间则为 $O(m)$ 。[1]
以此法建模有 $n$ 个点和 $m$ 条边的图，其内存空间开销的规模是 $O(n^{2})$ 。[1]

主要缺点包括：

遍历元素时，存在的边和不存在的边都不得不检查一遍，导致遍历效率低。[1]
不能存储重复的边。[1]
当顶点数量多时，内存空间开销会很大。[1]
存储稀疏图时会得到稀疏矩阵，空间利用率不高。[1]
存储无向图时，由于此时矩阵是对称的，而对称位置上的成对元素保存的信息是重复的，导致空间利用率不高。

随机过程

在随机过程理论中，表示单步状态变化的转移矩阵就是一种邻接矩阵。

参考资料

梁冰; 冯林. . 吴文虎 (主审); 房鸣 (主审); 孙琳 (责任编辑) (编). . 大学生创意·创新·创业教育与实践系列教材 1. 北京: 高等教育出版社. 2018: 130–131. ISBN 978-7-04-049192-0 （中文（中国大陆）‎）.
刘亚国. . 张家口职业技术学院学报. 2007, (4) [2014-01-12]. （原始内容存档于2014-01-12）（中文（中国大陆）‎）.
吴炜超. 马涛; 何万程; 郭子伟 , 编. . 《人教网刊》第4期. 2011年6月23日 [2019年12月15日]. （原始内容存档于2016年3月5日）（中文（中国大陆）‎）.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[梁冰_2018-1] 梁冰; 冯林. . 吴文虎 (主审); 房鸣 (主审); 孙琳 (责任编辑) (编). . 大学生创意·创新·创业教育与实践系列教材 1. 北京: 高等教育出版社. 2018: 130–131. ISBN 978-7-04-049192-0 （中文（中国大陆）‎）.

[2] 刘亚国. . 张家口职业技术学院学报. 2007, (4) [2014-01-12]. （原始内容存档于2014-01-12）（中文（中国大陆）‎）.

[ball-3] 吴炜超. 马涛; 何万程; 郭子伟 , 编. . 《人教网刊》第4期. 2011年6月23日 [2019年12月15日]. （原始内容存档于2016年3月5日）（中文（中国大陆）‎）.