离散数学图的矩阵表示.ppt
离散数学图的矩阵表示离散数学图的矩阵表示1现在学习的是第1页，共25页无向图的关联矩阵无向图的关联矩阵定定义义设设无无向向图图G=,V=v1,v2,vn,E=e1,e2,em,令令mij为为vi与与ej的的关关联联次次数数，称称(mij)n m为为G的的关关联联矩矩阵阵，记为记为M(G).2现在学习的是第2页，共25页 例例:求下图求下图G的关联矩阵的关联矩阵l上图上图G的关联矩阵的关联矩阵:3现在学习的是第3页，共25页无向图的关联矩阵无向图的关联矩阵性质：（5）当且仅当当且仅当vi为孤立点。为孤立点。4现在学习的是第4页，共25页有向图的关联矩阵有向图的关联矩阵定义定义设无环有向图设无环有向图D=,V=v1,v2,vn,E=e1,e2,em,令令则称则称(mij)n m为为D的关联矩阵的关联矩阵，记为，记为M(D).5现在学习的是第5页，共25页n例例:求图求图G的关联矩阵。的关联矩阵。l 上图上图G的关联矩阵的关联矩阵:6现在学习的是第6页，共25页有向图的关联矩阵有向图的关联矩阵(续续)性质性质(4)平行边对应的列相同平行边对应的列相同7现在学习的是第7页，共25页定义定义设有向图设有向图D=,V=v1,v2,vn,E=e1,e2,em,令令为顶点为顶点vi邻接到顶点邻接到顶点vj边的条数，称边的条数，称()m n为为D的邻接矩阵的邻接矩阵,记作记作A(D),简记为简记为A.有向图的邻接矩阵有向图的邻接矩阵 8现在学习的是第8页，共25页n求下图求下图G的邻接矩阵的邻接矩阵。l解解上图上图G的邻接矩阵。的邻接矩阵。给出了图给出了图G的邻接矩阵，就等于给出了图的邻接矩阵，就等于给出了图G的全部的全部信息。图的性质可以由矩阵信息。图的性质可以由矩阵 A通过运算而获得通过运算而获得。9现在学习的是第9页，共25页定义定义设有向图设有向图D=,V=v1,v2,vn,E=e1,e2,em,令令为顶点为顶点vi邻接到顶点邻接到顶点vj边的条数，称边的条数，称()m n为为D的邻接矩阵的邻接矩阵,记作记作A(D),简记为简记为A.性质性质有向图的邻接矩阵有向图的邻接矩阵 10现在学习的是第10页，共25页 D中的通路及回路数中的通路及回路数定理定理设设A为为n阶有向图阶有向图D的邻接矩阵的邻接矩阵,则则Al(l 1)中中元素元素为为D中中vi到到vj长度为长度为l 的通路数，的通路数，为为vi到自身长度为到自身长度为l 的回路数，的回路数，为为D中长度为中长度为l 的通路总数，的通路总数，为为D中长度为中长度为l 的回路总数的回路总数.11现在学习的是第11页，共25页D中的通路及回路数中的通路及回路数(续续)例例有向图有向图D如图所示如图所示,求求A,A2,A3,A4,并回答诸问题：并回答诸问题：(1)D中长度为中长度为1,2,3,4的通路各有多的通路各有多少条？其中回路分别为多少条？少条？其中回路分别为多少条？(2)D中长度小于或等于中长度小于或等于4的通路为多的通路为多少条？其中有多少条回路？少条？其中有多少条回路？推论推论设设Bl=A+A2+Al(l 1),则则Bl中元素中元素为为D中长度小于或等于中长度小于或等于l 的通路数，的通路数，为为D中长度小于或等于中长度小于或等于l 的回路数的回路数.12现在学习的是第12页，共25页例(续)长度长度 通路通路 回路回路合计合计50818121133141417313现在学习的是第13页，共25页在下图中在下图中v1到到v3长度为长度为1、2、3、4的通路分别有多少条，的通路分别有多少条，G中共有长度为中共有长度为4的通路多少条，其中回路多少条，长度的通路多少条，其中回路多少条，长度小于等于小于等于4的通路共有多少条，其中回路多少条。的通路共有多少条，其中回路多少条。14现在学习的是第14页，共25页l解解:因为因为 15现在学习的是第15页，共25页l 所以，由所以，由v1到到v3长度为长度为1、2、3、4的通路的通路分别有分别有0、2、2、4条，条，G中共有长度为中共有长度为4的的通路通路43条，其中回路条，其中回路11条，长度小于等于条，长度小于等于4的通路共有的通路共有87条，其中回路条，其中回路22条。条。l注注无无向向图图也也有有相相应应的的邻邻接接矩矩阵阵，一一般般只只考考虑虑简简单单图图，无无向向图图的的邻邻接接矩矩阵阵是是对对称称的的，其其性质基本与有向图邻接矩阵的性质相同。性质基本与有向图邻接矩阵的性质相同。16现在学习的是第16页，共25页 例如例如:下图邻接矩阵为：下图邻接矩阵为：17现在学习的是第17页，共25页有向图的可达矩阵有向图的可达矩阵称称(pij)n n为为D的可达矩阵的可达矩阵,记作记作P(D),简记为简记为P.性质性质:P(D)主对角线上的元素全为主对角线上的元素全为1.D强连通当且仅当强连通当且仅当P(D)的元素全为的元素全为1.定义定义设设D=为有向图为有向图,V=v1,v2,vn,令令18现在学习的是第18页，共25页有向图的可达矩阵(续)例例右图所示的有向图右图所示的有向图D的可达矩阵为的可达矩阵为19现在学习的是第19页，共25页 设设G=V,E 是是n阶阶简简单单有有向向图图，V=v1,v2,vn，由由可可达达性性矩矩阵阵的的定定义义知知，当当ij时时，如如果果vi到到vj有有路路，则则pij=1；如如果果vi到到vj无无通通路路，则则pij=0；又又如如果果vi到到vj有有通通路路，则则必必存存在在长长度度小小于于等等于于n1的的通通路路。又又n阶阶图图中中，任任何何回回路路的的长长度不大于度不大于n，如下计算图，如下计算图G的可达性矩阵的可达性矩阵P：B=E+A+A2+A n-1=(b ij)nn 其中其中 E 是单位矩阵。则是单位矩阵。则20现在学习的是第20页，共25页 图图9.24邻接矩阵邻接矩阵A和和A2，A3，A4如下：如下：21现在学习的是第21页，共25页 22现在学习的是第22页，共25页则图则图G的可达性矩阵的可达性矩阵B=A0AA2A3A4 =P=23现在学习的是第23页，共25页可可达达性性矩矩阵阵用用来来描描述述有有向向图图的的一一个个结结点点到到另另一一个个结结点点是是否否有有路路，即即是是否否可可达达。无无向向图图也也可可以以用用矩矩阵阵描描述述一一个个结结点点到到另另一一个个结结点点是是否否有有路路。在在无无向向图图中中，如如果果结结点点之之间间有有路路，称称这这两两个个结结点点连连通通，不不叫叫可可达达。所所以以把把描描述述一一个个结结点点到到另另一一个个结结点点是是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。否有路的矩阵叫连通矩阵，而不叫可达性矩阵。24现在学习的是第24页，共25页 定义定义设设G=V,E 是简单无向图，是简单无向图，V=v1,v2,vn P(G)=(pij)nn其中：其中：i,j=1,n称称P(G)为为G的连通矩阵。简记为的连通矩阵。简记为P。无向图的邻接矩阵是对称阵，无向图的连通矩无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。似。25现在学习的是第25页，共25页
