有向图的邻接矩阵_第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，若有通路，必有且，即。反之，若D中不存在通路，必有或，即。于是在图D中从顶点到顶点的长度等于2的通路数为：由矩阵的乘法规则知，正好

2、是矩阵中的第i行与第j列元素，记，即就是从顶点到顶点的长度等于2的通路数，时，表示从顶点到顶点的长度等于2的回路数。因此，即矩阵中所有元素的和为长度等于2的通路总数(含回路)，其中对角线的元素和为长度等于2的回路总数。根据以上分析，则有下面的推论。定义 有向图，D中长度为的通路数和回路数可以用矩阵(简记)来表示，这里，其中，即 则为顶点到顶点长度为的通路数，为到自身长度为的回路数。中所有元素之和为D中长度为的通路数，而中对角线上元素之和为D中始于(终于)各顶点的长度为的回路数。在图7.12中，计算，如下： 观察各矩阵发现，。于是，D中到长度为2的通路有3条，长度为3的通路有4条，长度为4的通路有6条。由，可知，D中到自身长度为的回路各有1条(此时回路为复杂的)。由于，所以D中长度为2的通路总数为10，其中有3条回路。从上述分析，可得下面定理。定理7.5 设为有向图D的邻接矩阵，则中元素为到长度为的通路数，为D中长度为的通路总数，其中为D中长度为的回路总数。若再令矩阵，上面定理有下面推论。推论设，则中元素为D中到长度小于等于的通路数，为D中长

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论