第七章图的基本概念PPT讲稿.ppt

第七章图的基本概念第七章图的基本概念第1页，共30页，编辑于2022年，星期一2022/9/1817.3 图的矩阵表示图的矩阵表示给给给给定定定定一一一一个个个个图图图图G G=，使使使使用用用用图图图图形形形形表表表表示示示示法法法法很很很很容容容容易易易易把把把把图图图图的的的的结结结结构构构构展展展展现现现现出出出出来来来来，而而而而且且且且这这这这种种种种表表表表示示示示直直直直观观观观明明明明了了了了。但但但但这这这这只只只只在在在在结结结结点点点点和和和和边边边边(或或或或弧弧弧弧)的数目相当小的情况下才是可行的。显然这限制了图的利用。的数目相当小的情况下才是可行的。显然这限制了图的利用。的数目相当小的情况下才是可行的。显然这限制了图的利用。的数目相当小的情况下才是可行的。显然这限制了图的利用。本本本本节节节节提提提提供供供供另另另另一一一一种种种种图图图图的的的的表表表表示示示示法法法法图图图图的的的的矩矩矩矩阵阵阵阵表表表表示示示示法法法法。它它它它不不不不仅仅仅仅克克克克服服服服了了了了图图图图形形形形表表表表示示示示法法法法的的的的不不不不足足足足，而而而而且且且且这这这这种种种种表表表表示示示示可可可可以以以以充充充充分分分分利利利利用用用用现现现现代工具电子计算机，以达到研究图的目的。代工具电子计算机，以达到研究图的目的。代工具电子计算机，以达到研究图的目的。代工具电子计算机，以达到研究图的目的。第2页，共30页，编辑于2022年，星期一无向图的关联矩阵无向图的关联矩阵注：自环取注：自环取2 2。第3页，共30页，编辑于2022年，星期一第4页，共30页，编辑于2022年，星期一性质性质：若第j列与第k列相同，则ej与ek为平行边第5页，共30页，编辑于2022年，星期一有向图的关联矩阵有向图的关联矩阵第6页，共30页，编辑于2022年，星期一第7页，共30页，编辑于2022年，星期一性质性质：第8页，共30页，编辑于2022年，星期一一个简单图一个简单图G=由由V中每两个结点间中每两个结点间的邻接关系唯一地确定，这种关系可以用一个的邻接关系唯一地确定，这种关系可以用一个矩阵给出，而矩阵形式与图中结点的编序有密矩阵给出，而矩阵形式与图中结点的编序有密切关系，这是用矩阵表示图值得注意的一点。切关系，这是用矩阵表示图值得注意的一点。第9页，共30页，编辑于2022年，星期一有向图的邻接矩阵有向图的邻接矩阵第10页，共30页，编辑于2022年，星期一对对于于给给定定图图D，显显然然不不会会因因结结点点编编序序不不同同而而使使其其结结构构发发生生任任何何变变化化，即即图图的的结结点点所所有有不不同同的的编编序序实实际际上上仍仍表表示示同同一一个个图图。换换句句话话说说，这这些些结结点点的的不不同同编编序序的的图图都都是是同同构构的的，并并且且它它们的邻接矩阵都是相似的。们的邻接矩阵都是相似的。今今后后将将略略去去这这种种由由于于V中中结结点点编编序序而而引引起起邻邻接接矩矩阵阵的的任任意意性性，而而取取该该图图的的任任一一个个邻邻接接矩矩阵阵作为该图的矩阵表示。作为该图的矩阵表示。第11页，共30页，编辑于2022年，星期一第12页，共30页，编辑于2022年，星期一性质性质：A(D)A(D)中所有元素之和为中所有元素之和为D D中长度为中长度为1 1的通路总数，其中的通路总数，其中 主对角线元素之和为主对角线元素之和为D D中长度为中长度为1 1的回路（环）的总数。的回路（环）的总数。第13页，共30页，编辑于2022年，星期一邻接矩阵可展示相应图的一些性质：邻接矩阵可展示相应图的一些性质：若邻接矩阵的元素全为零，则其对应的图若邻接矩阵的元素全为零，则其对应的图是零图；是零图；若邻接矩阵的元素除主对角线元素外全为若邻接矩阵的元素除主对角线元素外全为1，则其对应的图是连通的且为简单完全图。，则其对应的图是连通的且为简单完全图。第14页，共30页，编辑于2022年，星期一第15页，共30页，编辑于2022年，星期一此外，当给定的简单图是此外，当给定的简单图是无向图无向图时，邻接时，邻接矩阵是矩阵是对称对称矩阵；反之，若给定任何对称矩阵矩阵；反之，若给定任何对称矩阵A，显然可以唯一地作出以，显然可以唯一地作出以A为其邻接矩阵的简单为其邻接矩阵的简单图图G。于是，所有。于是，所有n个结点的不同编序的简单图个结点的不同编序的简单图的集合与所有的集合与所有n阶对称矩阵的集合可建立阶对称矩阵的集合可建立一一对一一对应。应。第16页，共30页，编辑于2022年，星期一当所给图是当所给图是简单有向图简单有向图时，其邻接矩阵时，其邻接矩阵并并非非一定是一定是对称对称矩阵，但所有矩阵，但所有n个结点的不同编序个结点的不同编序的简单图的集合，与所有的简单图的集合，与所有n阶邻接矩阵的集合亦阶邻接矩阵的集合亦可建立一一对应。可建立一一对应。不仅如此，通过对矩阵元素的一些计算还不仅如此，通过对矩阵元素的一些计算还可以得到对应图的某些数量的特征。可以得到对应图的某些数量的特征。第17页，共30页，编辑于2022年，星期一由给定有向图由给定有向图由给定有向图由给定有向图D D的邻接矩阵的邻接矩阵A可计算出矩阵可计算出矩阵A A的的l l次幂，即次幂，即A Al。第18页，共30页，编辑于2022年，星期一在在在在一一一一些些些些实实实实际际际际问问问问题题题题中中中中，有有有有时时时时要要要要判判判判定定定定图图图图中中中中结结结结点点点点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中中中中 1 1，就就就就表表表表明明明明v vi i可可可可达达达达v vj j或或或或v vi i到到到到v vj j存存存存在在在在一一一一条条条条链链链链（或或或或通路）。但这种计算繁琐量大，又不知计算通路）。但这种计算繁琐量大，又不知计算通路）。但这种计算繁琐量大，又不知计算通路）。但这种计算繁琐量大，又不知计算A Ar r到何时为止。到何时为止。到何时为止。到何时为止。第19页，共30页，编辑于2022年，星期一根据定理根据定理10.2.2可知，对于有可知，对于有n个结点的图，个结点的图，任何基本链（或通路）的长度不大于任何基本链（或通路）的长度不大于n-1和任何和任何基本圈（或回路）的长度不大于基本圈（或回路）的长度不大于n。因此，只需。因此，只需考虑考虑 就可以了，其中就可以了，其中1rn。即只要计算。即只要计算Bn=A+A2+A3+An。第20页，共30页，编辑于2022年，星期一如果关心的是结点间可达性或结点间是否有链如果关心的是结点间可达性或结点间是否有链如果关心的是结点间可达性或结点间是否有链如果关心的是结点间可达性或结点间是否有链（或路），至于结点间的链存在多少条及长度是多少（或路），至于结点间的链存在多少条及长度是多少（或路），至于结点间的链存在多少条及长度是多少（或路），至于结点间的链存在多少条及长度是多少无关紧要，那么便可用下面的定义图的可达矩阵来表无关紧要，那么便可用下面的定义图的可达矩阵来表无关紧要，那么便可用下面的定义图的可达矩阵来表无关紧要，那么便可用下面的定义图的可达矩阵来表示结点间可达性。示结点间可达性。示结点间可达性。示结点间可达性。第21页，共30页，编辑于2022年，星期一定义定义定义定义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=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的可达矩阵。的可达矩阵。的可达矩阵。的可达矩阵。有向图的可达矩阵有向图的可达矩阵第22页，共30页，编辑于2022年，星期一可见，可达矩阵表明了图中任意两结点间是否至少存在可见，可达矩阵表明了图中任意两结点间是否至少存在可见，可达矩阵表明了图中任意两结点间是否至少存在可见，可达矩阵表明了图中任意两结点间是否至少存在一条链一条链一条链一条链(或通路或通路或通路或通路)以及在结点处是否有圈以及在结点处是否有圈以及在结点处是否有圈以及在结点处是否有圈(或回路或回路或回路或回路)。从图从图从图从图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)1)，这种变换后的矩阵即是可，这种变换后的矩阵即是可，这种变换后的矩阵即是可，这种变换后的矩阵即是可达矩阵达矩阵达矩阵达矩阵P P。显然可达矩阵是布尔矩阵。显然可达矩阵是布尔矩阵。显然可达矩阵是布尔矩阵。显然可达矩阵是布尔矩阵。第23页，共30页，编辑于2022年，星期一应用：求有向图的强连通分支。应用：求有向图的强连通分支。设设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 pijij=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的列号为下的列号为下标的结点构成了包含标的结点构成了包含v vi i的强分图的强分图第24页，共30页，编辑于2022年，星期一例如例如:求下列有向图的通路总数求下列有向图的通路总数,回路总数回路总数,可达矩阵可达矩阵,及强连通分支的顶点集及强连通分支的顶点集.第25页，共30页，编辑于2022年，星期一 长度小于等于长度小于等于5 5的通路总数的通路总数7070长度小于等于长度小于等于5 5的回路总数的回路总数1212第26页，共30页，编辑于2022年，星期一该图的强连通分支的顶点集为该图的强连通分支的顶点集为vv1 1,v,v2 2,v,v3 3,v,v4 4,v,v5 5.第27页，共30页，编辑于2022年，星期一利利用用简简单单有有向向图图的的可可达达矩矩阵阵，能能够够确确定定某某过程是否为递归的。过程是否为递归的。假假设设VP=p1,p2,pn 是是程程序序P中中的的过过程程集集合合，做做有有向向图图D=，其其中中pi VP，i=1,2,n；Epi调调用用pj。如如果果图图D中中有有包包含含pi的的回回路路，则则可可断断言言pi是是递递归归的的。为为此此，由由图图G的的邻邻接接矩矩阵阵A=(aij)计计算算出出可可达达矩矩阵阵A+=()。如如果果A+中中的的主主对对角角线上的某元素线上的某元素 =1，则，则pi是递归的。是递归的。第28页，共30页，编辑于2022年，星期一已知加权的简单图已知加权的简单图G=，定义一个矩阵，定义一个矩阵W=(wij)，其中：，其中：w,w是边是边vi,vj（或弧（或弧）E的的权权wij=0，vi与与vj不相邻不相邻则称则称W为图为图G的权矩阵的权矩阵权矩阵权矩阵第29页，共30页，编辑于2022年，星期一作业作业:P174 7.18:P174 7.18第30页，共30页，编辑于2022年，星期一