离散数学(第20讲)图论.ppt
C CS S|S SWWU US ST TXDCXDC8.3图的矩阵表示图的矩阵表示8.3.1邻接矩阵邻接矩阵v邻接矩阵是一个邻接矩阵是一个布尔矩阵布尔矩阵v无向线图的邻接矩阵是对称的无向线图的邻接矩阵是对称的v而有向线图的邻接矩阵不一定对称而有向线图的邻接矩阵不一定对称 C CS S|S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质1设设G是一个线图，则有：是一个线图，则有：1)1)当当有有向向线线图图代代表表关关系系时时，其其邻邻接接矩矩阵阵就就是是前前面面讲过的关系矩阵。讲过的关系矩阵。2)2)零零图图的的邻邻接接矩矩阵阵的的元元素素全全为为零零，并并称称它它为为零零矩矩阵。阵。3)3)图图的的每每一一结结点点都都有有自自回回路路而而再再无无其其他他边边时时，则则该图的邻接矩阵是单位矩阵。该图的邻接矩阵是单位矩阵。4)4)简单图的邻接矩阵主对角元全为零。简单图的邻接矩阵主对角元全为零。5)5)若若设设无无向向简简单单图图G G的的邻邻接接矩矩阵阵A A(a(aijij)n nn n，则则它的补图的邻接矩阵它的补图的邻接矩阵 为为C CS S|S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质26)设无向图设无向图G，Vv1,v2,vn的邻接的邻接矩阵矩阵A(aij)nn，则，则7)7)设有向图设有向图G G，V Vvv1 1,v,v2 2,v,vn n 的邻接的邻接矩阵矩阵A A(a(aijij)n nn n，则，则C CS S|S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质38)设图设图G，Vv1,v2,vn的邻接矩阵的邻接矩阵A(aij)nn，A中所有元素之和为中所有元素之和为A中长度为中长度为1的的路径（包括回路）数目。路径（包括回路）数目。若若G是有向图，它也是边的数目；是有向图，它也是边的数目；若若G是无向图，它是边的数目的二倍减去是无向图，它是边的数目的二倍减去G中自中自回路的数目，因回路的数目，因(vi,vi)看作是一条长度为看作是一条长度为1的路的路径，而不能再看作两条。径，而不能再看作两条。C CS S|S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质49)设有向图设有向图G的邻接矩阵为的邻接矩阵为A 令令BbijAAT，则，则 若若i j，bij表示从表示从vi和和vj引出的终止于共同终引出的终止于共同终点的数目点的数目;若若i=j，bii表示表示vi的引出次数，即出度。的引出次数，即出度。说明：说明：,当且仅当当且仅当aik=1,ajk=1,aik ajk=1,所以此时所以此时vi和和vj都存在都存在 指指向向vk的弧的弧C CS S|S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质510）设有向图设有向图G的邻接矩阵为的邻接矩阵为A 令令BbijATA，则，则 若若i j，bij表示能够同时终止于表示能够同时终止于vi和和vj的起点的起点的数目的数目;若若i=j，bii表示表示vi的引入次数，即入度。的引入次数，即入度。说明：说明：,当且仅当当且仅当aki=1,akj=1,aki akj=1,所以此时存在所以此时存在 vk指向指向vi和和vj的弧的弧C CS S|S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质611）令令B(bij)A AA，则有：，则有：此时，此时，b bijij表示从表示从v vi i到到v vj j长度为长度为2 2的路径数目，如的路径数目，如b bijij0 0，则无长度为，则无长度为2 2的路径的路径;而而b biiii表示经过表示经过v vi i的长度为的长度为2 2的回路数目；的回路数目；B B中所有元素的和就为图中所有元素的和就为图G G中长度为中长度为2 2的路径（含的路径（含回路）总数，主对角线上元素之和为图回路）总数，主对角线上元素之和为图G G中长度中长度为为2 2的回路总数。的回路总数。C CS S|S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质712）令令C(cij)AmAAA(aij(m)n n，则，则有：有：此时，此时，c cijij表示从表示从v vi i到到v vj j长度为长度为m m的路径数目，如的路径数目，如c cijij0 0，则无长度为，则无长度为m m的路径，而的路径，而c ciiii给出了经过给出了经过v vi i的长度为的长度为m m的回路数目。的回路数目。为为G G中长中长度为度为m m的路径（含回路）总数，主对角线上元素的路径（含回路）总数，主对角线上元素之和之和为为G G中长度为中长度为m m的回路总数。的回路总数。C CS S|S SWWU US ST TXDCXDC例例G1中长度为中长度为2的路径（含回路）总数为的路径（含回路）总数为21，其中，其中9条为回路。条为回路。G1中长度为中长度为3的路径（含回路）总数为的路径（含回路）总数为48，其中，其中10条为回路。条为回路。C CS S|S SWWU US ST TXDCXDC例例(续续)G2中长度为中长度为2的路径（含回路）总数为的路径（含回路）总数为11，其中，其中5条为回路。条为回路。G2中长度为中长度为3的路径（含回路）总数为的路径（含回路）总数为16，其中，其中3条为回路。条为回路。C CS S|S SWWU US ST TXDCXDCA A(a(aijij)n nn n为为G G的邻接矩阵，的邻接矩阵，A Ak k n nn n。则。则为从结点为从结点v vi i到结点到结点v vj j长度为长度为k k的路径数目；为结的路径数目；为结点点v vi i到自身的长度为到自身的长度为k k的回路数目；为的回路数目；为G G中中长度为长度为k k的路径（含回路）总数。的路径（含回路）总数。定理定理设设G为线图，为线图，Vv1,v2,vn，C CS S|S SWWU US ST TXDCXDC故故，而而a ai ik k是是结结点点v vi i到到v vj j长长度度为为1 1的的路路径径数数目目，是是结结点点v vk k到到v vj j长长度度为为m m的的路路径径数数目目，证明证明(对对k用归纳法用归纳法)1)当当k1时，显然成立。时，显然成立。2)设设km时，定理成立。时，定理成立。3)证明证明km1时定理成立。时定理成立。因为因为故故是是从从结结点点v vi i经经过过v vk k到到结结点点v vj j的的长长度度为为m m+1 1的的路路径径数数目目，那那么么是是从从结结点点v vi i到到结结点点v vj j的长度为的长度为m+1m+1的路径数目。的路径数目。C CS S|S SWWU US ST TXDCXDC推论推论设设G为线图，为线图，Vv1,v2,vn，A(aij)nn为为G的邻接矩阵，令的邻接矩阵，令其中其中则则 为从结点为从结点vi到结点到结点vj长度小于等于长度小于等于r的路径数的路径数目；为结点目；为结点vi到自身的长度小于等于到自身的长度小于等于r的回路的回路数目；为数目；为G中长度小于等于中长度小于等于r的路径（含回的路径（含回路）总数；为路）总数；为G中所有长度小于等于中所有长度小于等于r的回路的回路总数。总数。C CS S|S SWWU US ST TXDCXDC所以，要研究图中所以，要研究图中v vi i和和v vj j之间的任意长路径的情之间的任意长路径的情况，只需求出况，只需求出但实际上，在但实际上，在n n个结点的简单有向图中，基本个结点的简单有向图中，基本路径长度不超过路径长度不超过n-1;n-1;基本回路长度不超过基本回路长度不超过n n。我们只需要考虑我们只需要考虑A A到到A An n 就可以了解就可以了解v vi i和和v vj j之间之间的可达性了。的可达性了。即考察即考察C CS S|S SWWU US ST TXDCXDC例例在图在图G2中中 C CS S|S SWWU US ST TXDCXDC例例(续续)C CS S|S SWWU US ST TXDCXDC8.3.2可达性矩阵可达性矩阵定定 义义 设设 G 是是 一一 个个 线线 图图，其其 中中 Vv1,v2,vn，并并假假定定结结点点已已经经有有了了从从v1到到vn的的次序，定义相应的次序，定义相应的n阶方阵阶方阵P(pij)nn，其中，其中(i(i，j j1 1，2 2，3 3，n)n)称矩阵称矩阵P P为图为图G G的的可达性矩阵可达性矩阵。无向图的可达性矩阵是对称的，而有向图的无向图的可达性矩阵是对称的，而有向图的可达性矩阵则不一定对称。可达性矩阵则不一定对称。C CS S|S SWWU US ST TXDCXDC可达性矩阵可达性矩阵P中元素的确定中元素的确定由矩阵由矩阵Bn可知：可知：如如0 0，则表明从结点，则表明从结点v vi i到到v vj j是不可达的；是不可达的；如如0 0，则表明从结点，则表明从结点v vi i到到v vj j有长度不大于有长度不大于n n的路径，即此时从结点的路径，即此时从结点v vi i到到v vj j是可达的。是可达的。所以有：所以有：p pijij0 00 0，p pijij1 10 0，(i,j(i,j1,2,3,1,2,3,n),n)。在图在图G G2 2中中 C CS S|S SWWU US ST TXDCXDC定理定理设设G为为线线图图，A、P分分别别是是G的的邻邻接接矩矩阵阵和和可达性矩阵，则有可达性矩阵，则有这里，这里，A(i)表示表示i个个A进行布尔乘法。进行布尔乘法。C CS S|S SWWU US ST TXDCXDC例例如在图如在图G2中，中，A A(2)(2)=A=A(1)(1)A A(3)(3)=A=A(2)(2)A A(4)(4)=A=A(3)(3)C CS S|S SWWU US ST TXDCXDC矩阵与图的连通性矩阵与图的连通性1)无无向向线线图图G是是连连通通图图当当且且仅仅当当它它的的可可达达性性矩矩阵阵P的的所所有有元素都均为元素都均为1；2)有有向向线线图图G是是强强连连通通图图当当且且仅仅当当它它的的可可达达性性矩矩阵阵P的的所所有元素都均为有元素都均为1；3)有有向向线线图图G是是单单向向连连通通图图当当且且仅仅当当它它的的可可达达性性矩矩阵阵P及及其其转转置置矩矩阵阵PT，可可令令PPPT中中除除对对主主角角元元外外的的其其余余元素均为元素均为1；4)有有向向线线图图G是是弱弱连连通通图图当当且且仅仅当当它它的的邻邻接接矩矩阵阵A及及其其转转置置矩矩阵阵AT，可可令令BAAT作作为为邻邻接接矩矩阵阵而而求求出出的的可可达性矩阵达性矩阵P中所有元素均为中所有元素均为1。C CS S|S SWWU US ST TXDCXDC定理定理设设G为线图，为线图，P(pij)nn是图是图G的可的可达达性性矩矩阵阵，P PT T是是P P的的转转置置矩矩阵阵，若若PPPPT T的的第第i i行行的的非非 零零 元元 素素 在在 第第 j j1 1,j,j2 2,j,jk k列列，则则 结结 点点v vi i,v,vj j1 1,v,vj j2 2,v,vj jk k在在同同一一个个强强连连通通分分支支中中，即即vvi i,v,vj j1 1,v,vj j2 2,v,vj jk k 导导出出的的子子图图是是G G的的一一个个强强连连通通分图。分图。C CS S|S SWWU US ST TXDCXDC例例利用可达性矩阵求右图的利用可达性矩阵求右图的所有强连通分图。所有强连通分图。解解 该该图的邻接矩阵为图的邻接矩阵为A A(4)(4)A A(2)(2)，A A(5)(5)A A(3)(3)C CS S|S SWWU US ST TXDCXDC例例(续续)这说明，这说明，v1在一个强连通分支中，在一个强连通分支中，v2在一个在一个强连通分支中，强连通分支中，v3,v4和和v5在一个强连通分支中，在一个强连通分支中，因此该图的所有强连通分图分别为结点子集因此该图的所有强连通分图分别为结点子集v1，v2，v3,v4,v5导出的子图。导出的子图。
