邻接矩阵的乘方

在书上看到了一个很有意思的结论:在无向图的邻接矩阵S里,S的n次方的结果矩阵Sn的第(i,j)个元素的意义是从第i个结点到第j个结点总共可能的长度为n的路径的数量。

赶紧写篇博文记录一下:

结论的含义

先来说说这个结论的含义。
以n=2作为例子,也即S2
如图所示,假设有这么一个无向图:

graph TD;
    A((1))---B((2)) & C((3))---D((4));
    B((2))---C((3))

那么,这个无向图对应的邻接矩阵是:

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

那么

S^2 = \begin{bmatrix}
2&1&1&2\\
1&3&2&1\\
1&2&3&1\\
2&1&1&2\\
\end{bmatrix}

可以看到,S2(1,1) = 2,也就是说,从节点1到节点1的长度为n=2的路径有两条:(1->2->1)和(1->3->1)。

结论的原理

下面来稍微解释一下这个结论的原理。

首先我们来看矩阵乘法中S2 (i,j) 计算公式:

(S^2)_{i,j} = (row_i)*(column_j) = s_{i1}s_{1j} + s_{i2}s_{2j} + s_{i3}s_{3j} + s_{i4}s_{4j}

可以看到,si1 实际上是结点i到结点1的路径个数(这实际上也是邻接矩阵的定义),其余元素以此类推,那么si1s1j 只有当 i->1->j这个路径存在的时候才为1,否则为0.因为只要i->1和1->j其中任意一个路径不存在,那么其对应的si1或s1j就为0,因此此时这种情况乘积si1s1j 为0。

然后,乘积累加的意义是,i->x->j的路径的数量(x从1到4)。

现在已经知道了S*S = S2的意义,那么考虑一下S2S的意义。

其实也很简单,因为S2的每一个元素S2 (i,j)的含义是从结点i到结点j所有长度为2的路径的数量,再套用一次上面的分析,S2 (i,j) * s(y,j)只有在路径i->x->y``y->j两个路径都存在才为1,累加起来S^3^ (i,j)就是所有从结点i到结点j所有长度为3的路径的数量。

以此类推,Sn的每一个元素Sn (i,j) 自然就是所有可能的从结点i到结点j所有长度为n的路径的数量。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据