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