第七章图的基本概念优秀课件.ppt

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