(52)--5.8 图的可达矩阵与关联矩阵表示.ppt

《(52)--5.8 图的可达矩阵与关联矩阵表示.ppt》由会员分享，可在线阅读，更多相关《(52)--5.8 图的可达矩阵与关联矩阵表示.ppt（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的可达矩阵与关联矩阵表示设D=是n阶有向简单图，V=v1,v2,vn，称P=(pij)nn 为D的可达矩阵，其中：pij=10 i，j=1,2,n 从vi到 vj 至少存在一条通路否则1、可达矩阵首先构造有向图的邻接矩阵A，接着计算A2，A3，An，再构造矩阵B=A+A2+A3+An，最后利用关系：确定P的元素pij，从而构造出可达矩阵P。pij=1 bij 00 bij=02、有向图的可达矩阵的求解例：求右图的可达矩阵，判断它是否为强连通图？V1V4V2V3V5解：1.写出邻接矩阵2.计算 A2,A3,A4,A5.V1V4V2V3V5解：3.计算 B=A+A2+A3+A4 +A5 ,可见该

2、有向图中任何两个结点之间都是相互可达的，所以该图是一个强连通图。例：求右图的可达矩阵，判断它是否为强连通图？设G=是至少有一边的(n,m)无环图,V=v1,v2,vn,E=e1,e2,em,称M(G)=(mij)nm为G的关联矩阵，其中：mij=10vi 关联 ej其它v4e1e2e3e4v1v2v3图G3、无向图的关联矩阵无向图的关联矩阵的性质：当且仅当vi是孤立点v1 1 1 1 0 v2 0 1 1 1 v3 1 0 0 1 v4 0 0 0 0 e1 e2 e3 e4v4e1e2e3e4v1v2v3图G设D=是至少有一条有向边的(n，m)无环有向图，V=v1,v2,vn,E=e1,e2,em，称M(D)=(mij)nm为D的关联矩阵，其中：mij=101ej 是vi 的出边vi 与 ej 不关联ej 是vi 的入边v1v4v3v2e1e2e3e4图Dv54、有向图的关联矩阵有向图的关联矩阵的性质：v1 -1 0 0 0 v2 1 -1 0 0 v3 0 1 -1 1 v4 0 0 1 -1v5 0 0 0 0 e1 e2 e3 e4 v1v4v3v2e1e2e3e4图Dv5(1)第i行中，1的个数是 vi 的出度，-1的个数是 vi 的入度；(2)矩阵中每列都有且仅有一个1和一个-1；(3)若矩阵中有全零元素行，则图有孤立点。THANK YOU