离散数学___图的矩阵表示.ppt

《离散数学___图的矩阵表示.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、7.3图的矩阵表示无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵1无向图的关联矩阵定义设无向图G=,V={v1,v2,…,vn},E={e1,e2,…,em},令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G).2例:求下图G的关联矩阵上图G的关联矩阵:3无向图的关联矩阵性质：（5）当且仅当vi为孤立点。4有向图的关联矩阵定义设无环有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em},令则称(mij)nm为D的关联

2、矩阵，记为M(D).5例:求图G的关联矩阵。上图G的关联矩阵:6有向图的关联矩阵(续)性质(4)平行边对应的列相同7定义设有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记为A.有向图的邻接矩阵8求下图G的邻接矩阵。解上图G的邻接矩阵。给出了图G的邻接矩阵，就等于给出了图G的全部信息。图的性质可以由矩阵A通过运算而获得。9定义设有向图D=,V={v1,v2,…,vn},E={e

3、1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记为A.性质有向图的邻接矩阵10D中的通路及回路数定理设A为n阶有向图D的邻接矩阵,则Al(l1)中元素为D中vi到vj长度为l的通路数，为vi到自身长度为l的回路数，为D中长度为l的通路总数，为D中长度为l的回路总数.11D中的通路及回路数(续)例有向图D如图所示,求A,A2,A3,A4,并回答诸问题：(1)D中长度为1,2,3,4的通路各有多少条？其中回路分别为多少条？(2)D中长度小于或等于

4、4的通路为多少条？其中有多少条回路？推论设Bl=A+A2+…+Al(l1),则Bl中元素为D中长度小于或等于l的通路数，为D中长度小于或等于l的回路数.12例(续)长度通路回路合计50818121133141417313在下图中v1到v3长度为1、2、3、4的通路分别有多少条，G中共有长度为4的通路多少条，其中回路多少条，长度小于等于4的通路共有多少条，其中回路多少条。14解:因为15所以，由v1到v3长度为1、2、3、4的通路分别有0、2、2、4条，G中共有长度为4的通路43条，其中回路11条，

5、长度小于等于4的通路共有87条，其中回路22条。注无向图也有相应的邻接矩阵，一般只考虑简单图，无向图的邻接矩阵是对称的，其性质基本与有向图邻接矩阵的性质相同。16例如:下图邻接矩阵为：17有向图的可达矩阵称(pij)nn为D的可达矩阵,记作P(D),简记为P.性质:P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.定义设D=为有向图,V={v1,v2,…,vn},令18有向图的可达矩阵(续)例右图所示的有向图D的可达矩阵为19设G=V,E是n阶简单有向图，V={v

6、1,v2,…,vn}，由可达性矩阵的定义知，当i≠j时，如果vi到vj有路，则pij=1；如果vi到vj无通路，则pij=0；又如果vi到vj有通路，则必存在长度小于等于n–1的通路。又n阶图中，任何回路的长度不大于n，如下计算图G的可达性矩阵P：B=E+A+A2+…+An-1=(bij)n×n其中E是单位矩阵。则20图9.24邻接矩阵A和A2，A3，A4如下：2122则图G的可达性矩阵B=A0＋A＋A2＋A3＋A4=P=23可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图

7、也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。24定义设G=V,E是简单无向图，V={v1,v2,…,vn}P(G)=(pij)n×n其中：i,j=1,…,n称P(G)为G的连通矩阵。简记为P。无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。25