关联矩阵$M$与节点的度，$MM^{T}$

摘要: 关联矩阵与节点的度

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们来看一个算法导论中比较有意思的一个习题，具体见第三版 22. 1-7，关于关联矩阵与节点的度。

关联矩阵的定义

对于有向无环图 $G = (V, E)$，其关联矩阵式满足以下条件的 $|V| \times |E|$ 矩阵 $B = (b_{ij})$：

$$b_{ij} = \left\{ \begin{array}{**lr**} -1 \quad 边 j 从节点 i 发出 \\ 1 \quad 边 j 从节点 i 进入 \\ 0 \quad 边 j 与节点 i 没关系 \\ \end{array} \right.$$

下图是一个例子：

$BB^{T}$ 的含义

按照定义，有：

$$BB^{T}(i, j) = \sum\limits_{e\in E}b_{ie}b_{ej}^{T} = \sum\limits_{e\in E}b_{ie}b_{je}$$

• 如果 $i = j$，且 $e$ 与 $i$ 有关，则 $b_{ie}b_{je} = 1$，否则。$b_{ie}b_{je} = 0$。
• 如果 $i \neq j$，且 $e$ 与 $i$，$j$ 有关，也就是 $e = (i, j)$ 或 $e = (j, i)$，则 $b_{ie}b_{je} = -1$。

还是以上图为例子：

$$BB^{T} = \begin{bmatrix} -1 & 1 & -1 & 0 & 0 & 0 \\ 1 & 0 & 0 & -1 & 0 & 0 \\ 0 & -1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & -1 \\ 0 & 0 & 0 & 1 & -1 & 1 \\ \end{bmatrix} \begin{bmatrix} -1 & 1 & 0 & 0 & 0 \\ 1 & 0 & -1 & 0 & 0 \\ -1 & 0 & 0 & 1 & 0 \\ 0 & -1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & -1 \\ 0 & 0 & 0 & -1 & 1 \\ \end{bmatrix}$$

对照着示例图，我们可以发现 $BB^{T}(i, j)$ 的含义如下：

$$BB^{T}(i, j) = \left\{ \begin{array}{**lr**} 节点 i 的度（入度 + 出度） \quad i = j \\ i 到 j 的边的条数的相反数 \quad i \neq j \\ \end{array} \right.$$

---