5.3 图的矩阵表示_第1页
5.3 图的矩阵表示_第2页
5.3 图的矩阵表示_第3页
5.3 图的矩阵表示_第4页
5.3 图的矩阵表示_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

5.3图的矩阵表示无向图的关联矩阵定义设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},

令mij为vi与ej的关联次数，称(mij)n

m为G的关联矩阵，记为M(G).

M(G)=

性质(1)每一列恰好有两个1或一个2定义设无环有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令

则称(mij)n

m为D的关联矩阵，记为M(D).

M(D)=

性质(1)每一列恰好有一个1和一个-1(2)第i行1的个数等于d+(vi),-1的个数等于d-(vi)(3)1的总个数等于-1的总个数,且都等于m(4)平行边对应的列相同有向图的邻接矩阵定义设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()m

n为D的邻接矩阵,记作A(D),简记为A.性质有向图的邻接矩阵实例无向图的邻接矩阵具有下述性质(1)无向图的邻接矩阵是对称矩阵。(2)如果邻接矩阵中有一行全为零，说明该图中有孤立点。(3)如果邻接矩阵对角线元素全为零，说明该图中没有环。定理设A为n阶有向图D的邻接矩阵,则Al(l

1)中元素

为

D中vi到vj长度为l的通路数，为vi到自身长度为l的回路数，

为D中长度为l的通路总数，

为D中长度为l的回路总数.推论设Bl=A+A2+…+Al(l

1),则Bl中元素为D中长度小于或等于l的通路数，为D中长度小于或等于l的回路数.问在有向图D中(1)长度为1,2,3,4的通路各有多少条？其中回路分别为多少条？(2)长度小于或等于4的通路为多少条？其中有多少条回路？有向图的可达矩阵定义设D=<V,E>为有向图,V={v1,v2,…,vn},令

称(pij)n

n为D的可达矩阵,记作P(D),简记为P.性质:

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

温馨提示

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

最新文档

评论

0/150

提交评论