离散数学 第2版 教学课件 作者 王元元 离散第20讲 图的矩阵表示.ppt

《离散数学 第2版 教学课件 作者 王元元 离散第20讲 图的矩阵表示.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机专业基础课程授课人：王元元单位：计算机理论教研室理工大学指挥自动化学院PowerPointTemplate_Sub1图的基础知识2路径、回路及连通性3欧拉图与哈密顿图4图的矩阵表示2第20讲图的矩阵表示图的矩阵表示《离散数学》第20讲Page122to125邻接矩阵(adjacencymatrix)设G=为一无重边的有向图。其中V={v1,v2,…,vn}，那么nn矩阵A=[aij]，称为图G的邻接矩阵，记为A[G]。v1v2v3v44第20讲图的矩阵表示有向图的邻接矩阵5第20讲图的矩阵表示无向图的邻接矩阵v1v2v

2、3v46第20讲图的矩阵表示邻接矩阵的性质零图的邻接矩阵为对角线元素aii=1表示一图的每个顶点以且仅以环为关联的边，其邻接矩阵为矩阵对称表示第i行之和表示第j列之和表示有向图矩阵所有元素之和为无向图的邻接矩阵是Kn的邻接矩阵是有向完全图的邻接矩阵是零矩阵vi上有环么阵边成对出现vi的出度vj的入度图的边数对称矩阵全1矩阵对角线元素为0，其余元素为1的矩阵7第20讲图的矩阵表示邻接矩阵与同构带有下列邻接矩阵的简单图是否同构？v1v2v3v1v2v3v1v3v4v2v1v3v4v28第20讲图的矩阵表示重图和赋权图的邻接矩阵v1v2v3v

3、4v1v2v3v4v51081164469第20讲图的矩阵表示设A为图G的邻接矩阵，A=[aij]，AT为A的转置矩阵，ο为矩阵乘运算符。若AοB=C,A=[aij],B=[bij],C=[cij]，那么用Ak表示k个矩阵A的乘积。矩阵的运算10第20讲图的矩阵表示=4，v3到v1有4条长度为3的拟路径，它们是(v3,v1,v1,v1),(v3,v4,v1,v1)，(v3,v2,v4,v1)，(v3,v2,v3,v1)。令Ak=[aij(k)]，那么aij(k)的意义是：G中从顶点vi到vj的长度为k的拟路径恰为aij(k)条。邻接矩阵

4、的运算v1v2v3v411第20讲图的矩阵表示邻接矩阵的运算证明：对k作归纳k=1时，A1=A=[aij(1)]=[aij]，显然成立假设Ak=[aij(k)]中aij(k)对任意i,j均表示vi到vj的长度为k的拟路径条数，考虑Ak+1=[aij(k+1)]因为aij(k+1)=而其中aih(k)表示vi到vh的长度为k的拟路径条数，ahj表示vh到vj的长度为1的拟路径条数，两者乘积代表vi到vj最后一步经vh的长度为k+1的拟路径条数因此aij(k+1)=就表示vi到vj的长度为k+1的拟路径条数证毕12第20讲图的矩阵表示邻接矩

5、阵的运算AοAT=[bij]，那么bij的意义是：有bij个顶点v，使得vi到v，vj到v都有边(两边交于v)。bii表示顶点vi的出度。b31=2，有两个顶点v1，v2，使得v3与v1到它们都有边；b33=3，顶点v3的出度为3。v1v2v3v413第20讲图的矩阵表示邻接矩阵的运算ATοA=[bij]，那么bij的意义是：有bij个顶点v，使得v到vi,v到vj都有边bii表示顶点vi的入度。b31＝0，图中确无到v3，v1均有边的顶点；b44=2，而v4的入度正是2v1v2v3v414第20讲图的矩阵表示ο为矩阵乘运算符。若AοB

6、=C,A=[aij],B=[bij],C=[cij]，那么令Ak=[aij(k)]，那么aij(k)的意义是：G中从顶点vi到vj的长度为k的拟路径恰为aij(k)条。=4，v3到v1有4条长度为3的拟路径，它们是(v3,v1,v1,v1),(v3,v4,v1,v1)，(v3,v2,v4,v1)，(v3,v2,v3,v1)。路径矩阵—引入若不考虑路径条数，只考虑有无路径，怎样对矩阵进行简化？15第20讲图的矩阵表示矩阵的∨和∧运算设有n维矩阵A、C，定义∨及∧运算如下若A=[aij]，C=[cij]，则A∨C=[dij]dij=aij∨

7、cijA∧C=[eij]eij=(aik∧ckj)这里为连续求∨运算的缩记符,以下相同16第20讲图的矩阵表示举例17第20讲图的矩阵表示路径矩阵B＝A∨A(2)∨A(3)∨A(4)∨A(5)B=A∨A(2)∨…∨A(n)，它的第i，j分量bij=1当且仅当图G中有vi到vj的路径。B称为图G的路径矩阵(walkmatrix)v1v2v5v3v418第20讲图的矩阵表示用A(m)表示A∧A∧…∧A(m个A)矩阵B=A∨A(2)∨…∨A(n)称为图G的路径矩阵(walkmatrix)，它的第i，j分量bij=1当且仅当图G中有vi到vj的

8、路径。令矩阵P=I∨B，其中I为(nn)么矩阵，称P为图G的可达性矩阵。路径矩阵与可达性矩阵P＝I∨Bv1v2v5v3v419第20讲图的矩阵表示可达性矩阵与强分图v1v2v5v3v4P＝I∨B20第20