有向图的邻接矩阵有向图的邻接矩阵
有向图的邻接矩阵
设有向图,,。令为邻接到的边的条数,称为D的邻接矩阵,记作。
为图7.12的邻接矩阵,不难看出:
(1)(即第i行元素之和为的出度),
。
(2)(即第j列元素之和为的入度),
。
(3)由(1),(2)可知,为D中边的总数,也可看成是中长度为D1的通路总数,而为D中环的个数,即D中长度为1的回路总数。
D中长度大于等于2的通路数和回路数应如何计算呢,
为此,先讨论长度等于2的通路数和回路数。
在图D中,从顶点到顶点的长度等于2的通路,中间必经过一顶点。对...
有向图的邻接矩阵
有向图的邻接矩阵
设有向图,,。令为邻接到的边的条数,称为D的邻接矩阵,记作。
为图7.12的邻接矩阵,不难看出:
(1)(即第i行元素之和为的出度),
。
(2)(即第j列元素之和为的入度),
。
(3)由(1),(2)可知,为D中边的总数,也可看成是中长度为D1的通路总数,而为D中环的个数,即D中长度为1的回路总数。
D中长度大于等于2的通路数和回路数应如何计算呢,
为此,先讨论长度等于2的通路数和回路数。
在图D中,从顶点到顶点的长度等于2的通路,中间必经过一顶点。对于任意的k,若有通路,必有且,即。反之,若D中不存在通路,必有或,即。于是在图D中从顶点到顶点的长度等于2的通路数为:
由矩阵的乘法
知,正好是矩阵中的第i行与第j列元素,记,即就是从顶点到顶点的长度等于2的通路数,时,
示从顶点到顶点的长度等于2的回路数。
因此,即矩阵中所有元素的和为长度等于2的通路总数(含回路),其中对角线的元素和为长度等于2的回路总数。
根据以上分析,则有下面的推论。
定义 有向图,,D中长度为的通路数和回路数可以用矩阵(简记)来表示,这里,其中
,
即
则为顶点到顶点长度为的通路数,为到自身长度为的回路数。中所有元素之和为D中长度为的通路数,而中对角线上元素之和为D中始于(终于)各顶点的长度为的回路数。
在图7.12中,计算,,如下:
观察各矩阵发现,,,。于是,D中到长度为
通路有4条,长度为4的通路有6条。由,2的通路有3条,长度为3的
,可知,D中到自身长度为的回路各有1条(此时回路为复杂的)。由于,所以D中长度为2的通路总数为10,其中有3条回路。
从上述分析,可得下面定理。
定理7.5 设为有向图D的邻接矩阵,,则中元素为
到长度为的通路数,为D中长度为的通路总数,其中为D中长度为的回路总数。
若再令矩阵
,
,
……
,
上面定理有下面推论。
推论 设,则中元素为D中到长度小于等于的通路数,为D中长度小于等于的通路总数,其中为D中长度小于等于的回路总数。
本文档为【有向图的邻接矩阵】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。