第七章图的基本概念精选文档.ppt

《第七章图的基本概念精选文档.ppt》由会员分享，可在线阅读，更多相关《第七章图的基本概念精选文档.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章图的基本概念第七章图的基本概念本讲稿第一页，共三十页2022/9/2417.3 图的矩阵表示图的矩阵表示给给给给定定定定一一一一个个个个图图图图G G=，使使使使用用用用图图图图形形形形表表表表示示示示法法法法很很很很容容容容易易易易把把把把图图图图的的的的结结结结构构构构展展展展现现现现出出出出来来来来，而而而而且且且且这这这这种种种种表表表表示示示示直直直直观观观观明明明明了了了了。但但但但这这这这只只只只在在在在结结结结点点点点和和和和边边边边(或或或或弧弧弧弧)的的的的数目相当小的情况下才是可行的。显然这限制了图的利用。数目相当小的情况下才是可行的。显然这限制了图的利用。数目相当

2、小的情况下才是可行的。显然这限制了图的利用。数目相当小的情况下才是可行的。显然这限制了图的利用。本本本本节节节节提提提提供供供供另另另另一一一一种种种种图图图图的的的的表表表表示示示示法法法法图图图图的的的的矩矩矩矩阵阵阵阵表表表表示示示示法法法法。它它它它不不不不仅仅仅仅克克克克服服服服了了了了图图图图形形形形表表表表示示示示法法法法的的的的不不不不足足足足，而而而而且且且且这这这这种种种种表表表表示示示示可可可可以以以以充充充充分分分分利利利利用现代工具电子计算机，以达到研究图的目的。用现代工具电子计算机，以达到研究图的目的。用现代工具电子计算机，以达到研究图的目的。用现代工具电子计算机，

3、以达到研究图的目的。本讲稿第二页，共三十页无向图的关联矩阵无向图的关联矩阵注：自环取注：自环取2 2。本讲稿第三页，共三十页本讲稿第四页，共三十页性质性质：若第j列与第k列相同，则ej与ek为平行边本讲稿第五页，共三十页有向图的关联矩阵有向图的关联矩阵本讲稿第六页，共三十页本讲稿第七页，共三十页性质性质：本讲稿第八页，共三十页一个简单图一个简单图G=由由V中每两个结点间中每两个结点间的邻接关系唯一地确定，这种关系可以用一个的邻接关系唯一地确定，这种关系可以用一个矩阵给出，而矩阵形式与图中结点的编序有密矩阵给出，而矩阵形式与图中结点的编序有密切关系，这是用矩阵表示图值得注意的一点。切关系，这是用

4、矩阵表示图值得注意的一点。本讲稿第九页，共三十页有向图的邻接矩阵有向图的邻接矩阵本讲稿第十页，共三十页对对于于给给定定图图D，显显然然不不会会因因结结点点编编序序不不同同而而使使其其结结构构发发生生任任何何变变化化，即即图图的的结结点点所所有有不不同同的的编编序序实实际际上上仍仍表表示示同同一一个个图图。换换句句话话说说，这这些些结结点点的的不不同同编编序序的的图图都都是是同同构构的的，并并且且它它们的邻接矩阵都是相似的。们的邻接矩阵都是相似的。今今后后将将略略去去这这种种由由于于V中中结结点点编编序序而而引引起起邻邻接接矩矩阵阵的的任任意意性性，而而取取该该图图的的任任一一个个邻邻接接矩矩阵

5、作为该图的矩阵表示。阵作为该图的矩阵表示。本讲稿第十一页，共三十页本讲稿第十二页，共三十页性质性质：A(D)A(D)中所有元素之和为中所有元素之和为D D中长度为中长度为1 1的通路总数，其中的通路总数，其中 主对角线元素之和为主对角线元素之和为D D中长度为中长度为1 1的回路（环）的总数。的回路（环）的总数。本讲稿第十三页，共三十页邻接矩阵可展示相应图的一些性质：邻接矩阵可展示相应图的一些性质：若邻接矩阵的元素全为零，则其对应的图若邻接矩阵的元素全为零，则其对应的图是零图；是零图；若邻接矩阵的元素除主对角线元素外全为若邻接矩阵的元素除主对角线元素外全为1，则其对应的图是连通的且为简单完全图

6、。，则其对应的图是连通的且为简单完全图。本讲稿第十四页，共三十页本讲稿第十五页，共三十页此外，当给定的简单图是此外，当给定的简单图是无向图无向图时，邻接时，邻接矩阵是矩阵是对称对称矩阵；反之，若给定任何对称矩阵矩阵；反之，若给定任何对称矩阵A，显然可以唯一地作出以，显然可以唯一地作出以A为其邻接矩阵的简单为其邻接矩阵的简单图图G。于是，所有。于是，所有n个结点的不同编序的简单图个结点的不同编序的简单图的集合与所有的集合与所有n阶对称矩阵的集合可建立阶对称矩阵的集合可建立一一对一一对应。应。本讲稿第十六页，共三十页当所给图是当所给图是简单有向图简单有向图时，其邻接矩阵时，其邻接矩阵并并非非一定是

7、一定是对称对称矩阵，但所有矩阵，但所有n个结点的不同编序个结点的不同编序的简单图的集合，与所有的简单图的集合，与所有n阶邻接矩阵的集合亦阶邻接矩阵的集合亦可建立一一对应。可建立一一对应。不仅如此，通过对矩阵元素的一些计算还不仅如此，通过对矩阵元素的一些计算还可以得到对应图的某些数量的特征。可以得到对应图的某些数量的特征。本讲稿第十七页，共三十页由给定有向图由给定有向图由给定有向图由给定有向图D D的邻接矩阵的邻接矩阵的邻接矩阵的邻接矩阵A A可计算出矩阵可计算出矩阵可计算出矩阵可计算出矩阵A A的的的的l l次幂，即次幂，即次幂，即次幂，即A Al l。本讲稿第十八页，共三十页在在在在一一一一

8、些些些些实实实实际际际际问问问问题题题题中中中中，有有有有时时时时要要要要判判判判定定定定图图图图中中中中结结结结点点点点v vi i到到到到结结结结点点点点v vj j是是是是否否否否可可可可达达达达，或或或或者者者者说说说说v vi i到到到到v vj j是是是是否否否否存存存存在在在在一一一一要要要要链链链链（或或或或通通通通路路路路）。如如如如果果果果要要要要利利利利用用用用图图图图D D的的的的邻邻邻邻接接接接矩矩矩矩阵阵阵阵A A，则则则则应应应应计计计计算算算算A A2 2，A A3 3，A An n，。当当当当发发发发现现现现其其其其中中中中某某某某个个个个A Ar r中中中中

9、 1 1，就就就就表表表表明明明明v vi i可可可可达达达达v vj j或或或或v vi i到到到到v vj j存存存存在在在在一一一一条条条条链链链链（或或或或通通通通路路路路）。但这种计算繁琐量大，又不知计算。但这种计算繁琐量大，又不知计算。但这种计算繁琐量大，又不知计算。但这种计算繁琐量大，又不知计算A Ar r到何时为止。到何时为止。到何时为止。到何时为止。本讲稿第十九页，共三十页根据定理根据定理10.2.2可知，对于有可知，对于有n个结点的图，个结点的图，任何基本链（或通路）的长度不大于任何基本链（或通路）的长度不大于n-1和任何和任何基本圈（或回路）的长度不大于基本圈（或回路）的

10、长度不大于n。因此，只需。因此，只需考虑考虑 就可以了，其中就可以了，其中1rn。即只要计算。即只要计算Bn=A+A2+A3+An。本讲稿第二十页，共三十页如果关心的是结点间可达性或结点间是否有如果关心的是结点间可达性或结点间是否有如果关心的是结点间可达性或结点间是否有如果关心的是结点间可达性或结点间是否有链（或路），至于结点间的链存在多少条及长度链（或路），至于结点间的链存在多少条及长度链（或路），至于结点间的链存在多少条及长度链（或路），至于结点间的链存在多少条及长度是多少无关紧要，那么便可用下面的定义图的可是多少无关紧要，那么便可用下面的定义图的可是多少无关紧要，那么便可用下面的定义图的

11、可是多少无关紧要，那么便可用下面的定义图的可达矩阵来表示结点间可达性。达矩阵来表示结点间可达性。达矩阵来表示结点间可达性。达矩阵来表示结点间可达性。本讲稿第二十一页，共三十页定义定义定义定义7.3.27.3.2 给定有向图给定有向图给定有向图给定有向图D D=，将其结点按下标编序，将其结点按下标编序，将其结点按下标编序，将其结点按下标编序得得得得V V=v v1 1，v v2 2，v vn n 。定义一个。定义一个。定义一个。定义一个n n阶方阵阶方阵阶方阵阶方阵P P=(=(p pij ij)，其中，其中，其中，其中 1 1 v vi i到到到到v vj j可达可达可达可达P Pij ij=

12、0 0 否则否则否则否则(P(P(P(Piiiiiiii=1,i=1,2,n,=1,i=1,2,n,=1,i=1,2,n,=1,i=1,2,n,若需要则添加）若需要则添加）若需要则添加）若需要则添加）则称矩阵则称矩阵则称矩阵则称矩阵P P是图是图是图是图D D的可达矩阵。的可达矩阵。的可达矩阵。的可达矩阵。有向图的可达矩阵有向图的可达矩阵本讲稿第二十二页，共三十页可见，可达矩阵表明了图中任意两结点间是否至少存在一条可见，可达矩阵表明了图中任意两结点间是否至少存在一条可见，可达矩阵表明了图中任意两结点间是否至少存在一条可见，可达矩阵表明了图中任意两结点间是否至少存在一条链链链链(或通路或通路或通

13、路或通路)以及在结点处是否有圈以及在结点处是否有圈以及在结点处是否有圈以及在结点处是否有圈(或回路或回路或回路或回路)。从图从图从图从图D D的邻接矩阵的邻接矩阵的邻接矩阵的邻接矩阵A A可以得到可达矩阵可以得到可达矩阵可以得到可达矩阵可以得到可达矩阵P P，即令，即令，即令，即令B Bn n=A A+A A2 2+A A3 3+A An n，再从，再从，再从，再从B Bn n中非零元素改为中非零元素改为中非零元素改为中非零元素改为1 1而零元素不变而零元素不变而零元素不变而零元素不变(若若若若需要，主对角线元素均改为需要，主对角线元素均改为需要，主对角线元素均改为需要，主对角线元素均改为1)

14、1)，这种变换后的矩阵即是可达矩，这种变换后的矩阵即是可达矩，这种变换后的矩阵即是可达矩，这种变换后的矩阵即是可达矩阵阵阵阵P P。显然可达矩阵是布尔矩阵。显然可达矩阵是布尔矩阵。显然可达矩阵是布尔矩阵。显然可达矩阵是布尔矩阵。本讲稿第二十三页，共三十页应用：求有向图的强连通分支。应用：求有向图的强连通分支。设设P P是是D D的可达矩阵，其元素的可达矩阵，其元素p pijij,P,PT T是是P P的转的转置，其元素置，其元素p pijijT T,则图则图D D的强连通分支可从矩阵的强连通分支可从矩阵P P PPT T求得。因从求得。因从v vi i到到v vj j可达，则可达，则p pij

15、ij=1=1，从，从v vj j到到v vi i可达，则可达，则p pjiji=1=1，即，即p pijijT T=1=1，于是当且仅当，于是当且仅当v vi i和和v vj j相互可达时，相互可达时，PPPPT T的第的第(i,j)(i,j)个元素的值为个元素的值为1 1定理定理7.3.27.3.2 给定简单有向图给定简单有向图D D中的任意结中的任意结点点v vi i，若，若P P=(=(p pijij)是是D D的可达矩阵，的可达矩阵，P PT T=(=(p pjiji)是是P P的的转置矩阵，则转置矩阵，则P PP PT T的第的第i i行元素为行元素为1 1的列号为下的列号为下标的结

16、点构成了包含标的结点构成了包含v vi i的强分图的强分图本讲稿第二十四页，共三十页例如例如:求下列有向图的通路总数求下列有向图的通路总数,回路总数回路总数,可达矩阵可达矩阵,及强连通分支的顶点集及强连通分支的顶点集.本讲稿第二十五页，共三十页 长度小于等于长度小于等于5 5的通路总数的通路总数7070长度小于等于长度小于等于5 5的回路总数的回路总数1212本讲稿第二十六页，共三十页该图的强连通分支的顶点集为该图的强连通分支的顶点集为vv1 1,v,v2 2,v,v3 3,v,v4 4,v,v5 5.本讲稿第二十七页，共三十页利利用用简简单单有有向向图图的的可可达达矩矩阵阵，能能够够确确定定

17、某某过程是否为递归的。过程是否为递归的。假假设设VP=p1,p2,pn 是是程程序序P中中的的过过程程集集合合，做做有有向向图图D=，其其中中pi VP，i=1,2,n；Epi调调用用pj。如如果果图图D中中有有包包含含pi的的回回路路，则则可可断断言言pi是是递递归归的的。为为此此，由由图图G的的邻邻接接矩矩阵阵A=(aij)计计算算出出可可达达矩矩阵阵A+=()。如如果果A+中中的主对角线上的某元素的主对角线上的某元素 =1，则，则pi是递归的。是递归的。本讲稿第二十八页，共三十页已知加权的简单图已知加权的简单图G=，定义一个矩阵，定义一个矩阵W=(wij)，其中：，其中：w,w是边是边vi,vj（或弧（或弧）E的的权权wij=0，vi与与vj不相邻不相邻则称则称W为图为图G的权矩阵的权矩阵权矩阵权矩阵本讲稿第二十九页，共三十页作业作业:P174 7.18:P174 7.18本讲稿第三十页，共三十页