有向图的邻接矩阵

有向图的邻接矩阵

ID:11330999

大小:103.50 KB

页数:4页

时间:2018-07-11

有向图的邻接矩阵_第1页
有向图的邻接矩阵_第2页
有向图的邻接矩阵_第3页
有向图的邻接矩阵_第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中长度为的通路数和回路数可以用矩阵(简记)来表示,这里,其中,  即  则为顶点到顶点长度为的通路数,为到自身长度为的回路数。中所有元素之和为D中长

3、度为的通路数,而中对角线上元素之和为D中始于(终于)各顶点的长度为的回路数。  在图7.12中,计算,,如下:      观察各矩阵发现,,,。于是,D中到长度为2的通路有3条,长度为3的通路有4条,长度为4的通路有6条。由,,可知,D中到自身长度为的回路各有1条(此时回路为复杂的)。由于,所以D中长度为2的通路总数为10,其中有3条回路。  从上述分析,可得下面定理。  定理7.5设为有向图D的邻接矩阵,,则中元素为到长度为的通路数,为D中长度为的通路总数,其中为D中长度为的回路总数。  若再令矩阵    ,    ,    

4、……    ,  上面定理有下面推论。  推论 设,则中元素为D中到长度小于等于的通路数,为D中长度小于等于的通路总数,其中为D中长度小于等于的回路总数。

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。