《有向图的邻接矩阵》由会员分享，可在线阅读，更多相关《有向图的邻接矩阵（4页珍藏版）》请在金锄头文库上搜索。
1、有向图的邻接矩阵设有向图 ， ， 。令 为 邻接到 的边 的条数，称 为D 的邻接矩阵，记作 。为图 7.12的邻接矩阵，不难看出：(1) (即第i 行元素之和为 的出度)， 。(2) (即第j 列元素之和为 的入度)， 。(3)由(1)，(2)可知， 为D 中边的总数，也可看成是D 中长度为 1的通路总数，而 为D 中环的个数，即D 中长度为1的回路总数。D 中长度大于等于2的通路数和回路数应如何计算呢？为此，先讨论长度等于2的通路数和回路数。 在图D 中，从顶点 到顶点 的长度等于2的通路，中间必经过一顶点 。 对于任意的k ，若有通路 ，必有 且 ，即 。 反之，若D 中不存在通路 ，必
2、有 或 ，即 。于是在图 D 中从顶点 到顶点 的长度等于2的通路数为：由矩阵的乘法规则知， 正好是矩阵 中的第i 行与第j 列元素，记 ，即 就是从顶点 到顶点 的长度等于 2的通路数， 时， 表示从顶点 到顶点 的长度等于2的回路数。因此， 即 矩阵中所有元素的和 为长度等于2的通路 总数(含回路)，其中对角线的元素和 为长度等于2的回路总数。根据以上分析，则有下面的推论。定义 有向图 ， ，D 中长度为 的通路数和回路 数可以用矩阵 (简记 )来表示，这里 ，其中 ，即 则 为顶点 到顶点 长度为 的通路数， 为 到自身长度为 的回路 数。 中所有元素之和 为D 中长度为 的通路数，而
3、中对角线上元素 之和 为D 中始于(终于)各顶点的长度为 的回路数。 在图7.12中，计算 ， ， 如下：观察各矩阵发现， ， ， 。于是，D 中 到 长度 为2的通路有3条，长度为3的通路有4条，长度为4的通路有6条。由 ， ， 可知，D 中 到自身长度为 的回路各有1条 (此时回路为复杂的)。由于 ，所以D 中长度为2的通路总数为10， 其中有3条回路。从上述分析，可得下面定理。定理7.5 设 为有向图D 的邻接矩阵， ，则 中元 素 为 到 长度为 的通路数， 为D 中长度为 的通路总数，其中 为D 中长度为 的回路总数。若再令矩阵，上面定理有下面推论。 推论 设 ，则 中元素 为D 中 到 长度小 于等于 的通路数， 为D 中长度小于等于 的通路总数，其中 为 D 中长度小于等于 的回路总数。
