离散数学第七章第三节ppt课件

.,1,第7-3讲图的矩阵表示,1.邻接矩阵2.可达性矩阵和连通矩阵3.关联矩阵4.课堂练习5.第7-3讲作业,.,2,1、邻接矩阵（1）,定义1设G=简单图,它有n个结点v1,v2,vnV，则n阶方阵A(G)=(aij)称为G的邻接矩阵，这里,例如，左下图的邻接矩阵列于右侧：,.,3,1、邻接矩阵（2）,图的邻接矩阵显然与n个结点的标定次序有关，因而同一个图可得出不同的邻接矩阵。不过这些矩阵可以通过交换行和列而相互得出。具有这样性质的矩阵称它们置换等价。,例如，左下图的两个置换等价邻接矩阵：,置换等价是n阶布尔矩阵集合上的一个等价关系。我们忽略邻接矩阵的多样性，可取图G的任一邻接矩阵视为该图的邻接矩阵,.,4,1、邻接矩阵（3）,简单有向图G的邻接矩阵A(G)=(aij)nn的第i行元素之和等于vi的出度。第j列元素之和等于vj的入度。,例如，左下有向图中，v3的出度=1+1+0+1=3，v3的入度=0+1+0+0=1,.,5,1、邻接矩阵（4）,定理1设简单有向图G=的邻接矩阵为A，则矩阵Ak中的第i行第j列元素等于G中连结vi与vj长度为k的路的数目。,例如，左下有向图，A2中的第2行第1列元素等于2，说明连结v2与v1长度为2的路的有两条：v2v4v1，v2v3v1。,分析:a21(2)=a21a11+a22a21+a23a31+a24a41=00+00+11+11=2注意从v2到v1长度为2的路中间必经由一个结点vk,即v2vkv1(1k4)。K=3时，a23a31=11表示v2到v3、v3到v1有路(边)。,.,6,1、邻接矩阵（5）,定理1设简单有向图G=的邻接矩阵为A，则矩阵Ak中的第i行第j列元素等于G中连结vi与vj长度为k的路的数目。,证明思路分析：对此定理不作全面证明。从A2为例作一些说明。计算连结vi与vj长度为2的路的数目，注意从vi到vj长度为2的路中间必经由一个结点vk,即vivkvj(1kn)，而且aik=akj=1，那么aikakj=1。反之，如果不存在路径vivkvj，则aik=0或akj=0，从而aikakj=0。所以从vi到vj长度为2的路径的数目等于,按矩阵的乘法法则，此和式恰好是A2中第i行第j列元素aij(2)。,.,7,1、邻接矩阵（6）,定理1设简单有向图G=的邻接矩阵为A，则矩阵Ak中的第i行第j列元素等于G中连结vi与vj长度为k的路的数目。,证明思路分析(续)：计算连结vi与vj长度为3的路径的数目，注意从vi到vj长度为3的路径可视为从vi到中间结点vk长度为1的路径，再加上从vk到vj长度为2的路径，所以从vi到vj长度为3的路径的数目等于,.,8,2、可达性矩阵和连通矩阵(1),定义2设G=为简单有向图，V=v1,v2,vn，定义矩阵P=（pij）,其中,有向图G中从vi到vj是否有路可达可通过矩阵运算而得到。,由图G的邻接矩阵A可得可达性矩阵P，令Bn=A+A2+An=(bij)nnBn中的元素bij表示从vi到vj是长度等于或小于n的路径数。若bij0，则表示从vi到vj可达。这样，将Bn中不为零的元素全部换成1，而等于零的元素保持不变，即得可达矩阵。,P称为图G的可达性矩阵。,.,9,2、可达性矩阵和连通矩阵(2),求可达性矩阵可简化为：(1)由图G的邻接矩阵A求可达性矩阵P:P=A(1)A(2)A(n)其中的元素A(i)表示Ai对应的布尔矩阵。(2)用Warshall算法计算：因为有向简单图的邻接矩阵A可视为具有n个结点的集合V上的邻接关系R的关系矩阵，而可达矩阵可视为邻接关系R的传递闭包所对应的矩阵。,设A=(aij)nn、B=(bij)nn是布尔矩阵，令C=AB=(cij)nn，称为布尔矩阵求“和”；令D=AB=(dij)nn，称为布尔矩阵求“积”。其中：,.,10,2、可达性矩阵和连通矩阵(3),方法1：先由邻接矩阵A求B4,B4=A+A2+A3+A4然后写出可达矩阵P。,计算可达矩阵举例:,方法2：将A、A2、A3、A4转换为布尔矩阵A(1)、A(2)、A(3)、A(4)，则P=A(1)A(2)A(3)A(4)。,.,11,2、可达性矩阵和连通矩阵(4),(3)用Warshall算法计算:,计算可达矩阵举例（续）:,.,12,3、关联矩阵(1),定义3设G=为无向图，V=v1,v2,vp，E=e1,e2,eq，定义矩阵M(G)=(mij)pq,其中,例如，写出下图的关联矩阵。,M(G)称为图G的完全关联矩阵。,.,13,3、关联矩阵(2),从完全关联矩阵可得出图的有关信息：(1)因每边只关联两个结点，故每列有且只有两个1，其余为0。(2)每行各元素之和即相应结点的度数。(3)若某行各元素皆为0，则相应结点为孤立结点。(4)平行边所对应的列完全相同。(5)同一个图取不同的点、边序列，其对应的关联矩阵仅存在行序和列序的差异。,.,14,3、关联矩阵(3),定义4设G=为简单有向图，V=v1,v2,vp，E=e1,e2,eq，定义矩阵M(G)=(mij)pq,其中,例如，写出如下简单有向图的关联矩阵。,M(G)称为有向图G的完全关联矩阵。,.,15,3、关联矩阵(4),从有向图的完全关联矩阵可得出图的有关信息：(1)每边关联一个始点，一个终点。故每列只有一个元素为1，一个元素为-1，其余为0。(2)每行的1之和即相应结点的出度，-1之和即相应结点的入度。(3)若某行各元素皆为0，则相应结点为孤立结点。(4)平行边所对应的列完全相同。,.,16,3、关联矩阵(5),定理2设连通图G有r个结点，则其完全关联矩阵的秩为r-1。(证明从略),两个关于关联矩阵的秩的结论：,推论设图G有r个结点，w个最大连通子图，则图G的完全关联矩阵的秩为r-w。,注：(1)矩阵中的任意k阶方阵的行列式该矩阵的k阶子式。(2)矩阵A中不为0的子式的最大阶数r叫A的秩。(3)交换矩阵中两行或两列；用非零数乘矩阵的某行或某列；用非零数乘矩阵的某行或某列后再加到另一行或列的对应元素上。以上三种变换叫矩阵的初等变换。初等变换不改变矩阵的秩。,.,17,4、课堂练习,练习求如下有