第九章 图论-3rd-zhou.ppt

离散数学大连理工大学软件学院,2/128,连通图,定义：设G是有向图。,(1)如果G中任意两个结点都互相可达，则称G是强连通的。(2)如果对于G的任意两结点，必有一个结点可达另一个结点，则称G是单向连通的。(3)如果G的基础图是连通的，则称G是弱连通的。,3/128,子图和分支,定义：设G是G的具有某种性质的子图，并且对于G的具有该性质的任意子图G，只要GG，就有G=G，则称G相对于该性质是G的极大子图。,定义：无向图G的极大连通子图称为G的分支。,定义：设G是有向图：,（1）G的极大强连通子图称为G的强分支。（2）G的极大单向连通子图称为G的单向分支。（3）G的极大弱连同子图称为G的弱分支。,4/128,子图和分支,定理：连通无向图恰有一个分支。非连通无向图有一个以上分支。,定理：强连通（单向连通，弱连通）有向图恰有一个强分支（单向分支，弱分支）；非强连通（非单向连通，非弱连通）有向图有一个以上强分支（单向分支，弱分支）。,5/128,子图和分支,例：,6/128,子图和分支,注意：无向图的每个结点和每条边都恰在一个连通分支中；有向图中，并不是每个边都恰在一个强分支中。在简单有向图中，每个结点每条边都恰在一个弱分支中。在简单有向图中，每个结点每条边至少位于一个单向分支中。,7/128,由结点集合v1，v2，v3，v4，v5，v6和v7形成的诱导子图都是强分图;由结点集合v1，v2，v3，v4，v5，v7，v4，v5和v6，v5所成的诱导子图都是单向分图；由结点集合v1，v2，v3，v4，v5，v6，v7形成的诱导子图是弱分图。,子图和分支,8/128,资源分配图,下面给出简单有向图的一个应用资源分配图。在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得到满足。,9/128,死锁状态,对资源的请求可能发生冲突。如程序A控制着资源r1，请求资源r2；但程序B控制着资源r2，请求资源r1。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现和纠正死锁。,10/128,假设条件,假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。,11/128,分析,令Pt=p1，p2，pm表示计算机系统在时间t的程序集合，QtPt是运行的程序集合，或者说在时刻t至少分配一部分所请求的资源的程序集合。Rt=r1，r2，rn是系统在时刻t的资源集合。资源分配图Gt=是有向图，它表示了时间t系统中资源分配状态。把每个资源ri看作图中一个结点，其中i=1，2，n。表示有向边，E当且仅当程序pkPt已分配到资源ri且等待资源rj。,12/128,分析（续）,例如，令Rt=r1，r2，r3，r4，Qt=p1，p2，p3，p4。资源分配状态是：p1占用资源r4且请求资源r1，p2占用资源r1且请求资源r2和r3，p3占用资源r2且请求资源r3，p4占用资源r3且请求资源r1和r4，于是，可得到资源分配图Gt=如图16.2.7所示。能够证明，在时刻t计算机系统处于死锁状态iff资源分配图Gt中包含强连通图。,13/128,前例资源分配图,14/128,割集,有时删除一个结点和它所关联的边，就产生带有比原图更多的连通分支的子图。把这样的结点称为割点。有时删除一条边，就产生带有比原图更多的连通分支的子图，把这样的边叫做割边或者桥。,15/41,7.4图的矩阵表示,一、邻接矩阵,定义：设是一个简单有向图，其中的结点集合，并且假定各结点已经有了从结点v1到vn的次序。试定义一个nn的矩阵A，使得其中的元素,则称这样的矩阵A是图G的邻接矩阵。,16/41,邻接矩阵,定义：元素或为0或为1的任何矩阵，都称为比特矩阵或布尔矩阵。,邻接矩阵也是布尔矩阵，第i行上值为1的元素的个数，等于结点vi的出度；第j列上值为1的元素的个数，等于结点vj的入度。,17/41,邻接矩阵,图的邻接矩阵不具有唯一性。,对于给定简单有向图来说，其邻接矩阵依赖于集合V中的各元素间的次序关系。,给定两个有向图和相对应的邻接矩阵，如果首先在一个图的邻接矩阵中交换一些行，而后交换相对应的各列，从而有一个图的邻接矩阵，能够求得另外一个图的邻接矩阵，则事实上这样的两个有向图，必定是互为同构的。,18/41,邻接矩阵,例：写出下图的邻接矩阵，并计算各个节点的出度和入度。,解：首先给各结点安排好一个次序，譬如说是。得出邻接矩阵如下：,19/41,邻接矩阵,上例中，如果重新把各结点排列成，就能写出另外一个矩阵如下：,如果首先交换第一行和第三行，而后交换第一列与第三列，接着交换v2和v3所对应的行，而后交换v2和v3所对应的列，那么就能够由邻接矩阵A2求得邻接矩阵A1。,20/41,邻接矩阵,对于给定图G，显然不会因结点编序不同而使其结构会发生任何变化，即图的结点所有不同编序实际上仍表示同一个图。换句话说，这些结点的不同编序的图都是同构的，并且它们的n！个邻接矩阵都是相似的。今后将略去这种由于V中结点编序而引起邻接矩阵的任意性。而取该图的任一个邻接矩阵作为该图的矩阵表示。,21/41,邻接矩阵,由邻接矩阵判断有向图的性质：,如果有向图是自反的，则邻接矩阵的主对角线上的各元素，必定都是1。如果有向图是反自反的，则邻接矩阵的主对角线上的各元素，必定都是0。对于对称的有向图来说，其邻接矩阵也是对称的，也就说，对于所有的i和j而言，都应有aij=aji。如果给定有向图是反对称的，则对于所有的i和j和ij而言，aij=1蕴含aji=0。,22/41,邻接矩阵,可以把简单有向图的矩阵表示的概念，推广到简单无向图、多重边图和加权图。对于简单无向图来说，这种推广会给出一个对称的邻接矩阵，在多重边图或加权图的情况下，可以令,其中的wij，或者是边的重数，或者是边的权。另外，若，则。,在零图的邻接矩阵中，所有元素都应该是0，亦即其邻接矩阵是个零矩阵。,23/41,邻接矩阵,逆图的邻接矩阵：,如果给定的图是一个简单有向图，并且其邻接矩阵是A，则图G的逆图的邻接矩阵是A的转置。对于无向图或者对称的有向图来说，应有。,24/41,在图上的意义,定义矩阵。设是邻接矩阵中的第i行和第j列上的元素，是矩阵中的第i行和第j列上的元素(i,j)。于是，对于来说，有,如果边，则有，如果边，则有。对于某一个确定的k来说，如果和都是给定图的边，则在表示的上述求和表达式中，应该引入基值1。从结点vi和vj二者引出的边，如果能共同终止于一些结点的话，那么这样的一些结点的数目，就是元素的值。,25/41,在图上的意义,例：如图，求,解：,简单算法：原矩阵A中，第i行和第j行相交，有几个1，AAT的第i行第j列就是几。,矩阵的主对角线的元素对应了各个节点的出度。,26/41,在图上的意义,设是邻接矩阵A中的(i,j)元素；是矩阵C中的元素。于是，对于,对于某一个确定的k来说，如果都是给定图的边，则在上式中应引入基值1。可得从图中的一些点所引出的边，如果能够同时终止于结点vi和vj的话，那么这样的一些结点的数目，就是元素Cij的值。,27/41,在图上的意义,例：如图，求,解：,简单算法：原矩阵A中，第i列和第j列相交，有几个1，ATA的第i行第j列就是几。,矩阵的主对角线的元素对应了各个节点的入度。,28/41,邻接矩阵的幂,对于来说，考察邻接矩阵A的幂An可知，邻接矩阵A中的第i行和第j列上的元素值1，说明了图G中存在一条边，也就是说，存在一条从结点vi到vj长度为1的路径。试定义矩阵A2，使得A2中的各元素为,元素值等于从vi到vj长度为2的不同路径的数目。显然，矩阵中主对角线上的元素的值，表示了结点上长度为2的循环的个数。矩阵A3中的元素值(i,j)依次类推。,29/41,邻接矩阵的幂,例：,30/41,邻接矩阵的幂,定理：设是一简单有向图，并且A是G的邻接矩阵。对于来说，矩阵Am中的元素(i,j)的值，等于从vi到vj长度为m的路径数目。,证：对于m进行归纳证明。当m=1时，由邻接矩阵的定义中能够得到Am=A。设矩阵Ak中的元素(i,j)值是，且对于m=k来说结论为真。因为，所以应有,是从结点vi出发，经过结点vk到vj的长度为k+1的各条路径的数目。这里vk是倒数第二个结点。因此，应是从结点vi出发，经过任意的倒数第二个结点到vj的长度为k+1的路径总数。因此，对于m=k+1，定理成立。,31/41,邻接矩阵的幂,根据上述定理，可得出结论：,能使矩阵Am中的元素(i,j)值是非零的最小正整数m，就是距离。对于和来说，如果矩阵中的(i,j)元素值和(j,i)元素值都为0，那么就不会有任何路径连通结点vi和vj。因此，结点vi和vj必定是属于图G的不同分图。,32/41,邻接矩阵的幂,例：给定一个简单有向图，如下图所示，其中的结点集合。试求出图G的邻接矩阵A和A的幂A2，A3,A4。,33/41,邻接矩阵的幂,解：,34/41,二、可达性矩阵,给定一个简单有向图，并且设结点。可知，由图G的邻接矩阵A能够直接确定G中是否存在一条从vi到vj的边。设，由矩阵能够求得从结点vi到vj长度为r的路径数目。试构成矩阵,矩阵Br的(i,j)元素值表示了从结点vi到vj长度小于或等于r的路径数目。当图中的结点数目为n时，矩阵Bn都能够提供足够的信息，以表明从图中的任何结点到其它结点的可达性。,35/41,可达性矩阵,定义：给定一个简单有向图，其中|V|=n，并且假定G中的各结点是有序的。试定义一个nn的路径矩阵P，使得其元素为,路经矩阵P仅表明了图中的任何结点偶对之间是否至少存在一条路径，以及在任何结点上存在循环与否；它并不能指明存在的所有路径。,36/41,可达性矩阵,例：试构成下列有向图的路径矩阵P。,解：设邻接矩阵A=A1。在前面的例中，已经求出过矩阵的幂A2，A3和A4。求出矩阵B4和路径矩阵P如下：,37/41,可达性矩阵,注意：对于具有n个结点的图而言，长度为n的路径不可能是基本路径。假定图中的每一个结点，从它本身出发总是可达的，由矩阵Bn-1构成路径矩阵P，或由矩阵Bn构成路径矩阵P，这两种方法都可以采纳。,38/41,可达性矩阵,首先构成矩阵，而后由他们构成矩阵Bn，再由矩阵Bn构成路径矩阵P，太麻烦了。为了减少计算工作量，应该设法使得不产生这些不必要的信息。,生成路径矩阵的简单方法：布尔矩阵法。,布尔和和布尔积：,对于两个nn的布尔矩阵A和B，A和B的布尔和是,A和B的布尔积是，并分别称为矩阵C和D，它们也都是布尔矩阵。把矩阵C和D的元素分别定义成,39/41,可达性矩阵,邻接矩阵A是个布尔矩阵。路径矩阵P也是个布尔矩阵。对于来说，令,于是，可以把路径矩阵P表示成,注意：A(m)表示布尔矩阵，如果从vi到vj有长度为m的路径的话，矩阵中(i,j)元素为1；Am中(i,j)元素表示从vi到vj的长度为m的路径的个数。,40/41,可达性矩阵,例：对于下述的有向图来说，试求出矩阵A(2),A(3),A(4)和P。,41/41,可达性矩阵,可以用不同的方法解释矩阵。在简单有向图中，应有，因此可以把集合E看成是V中的二元关系。邻接矩阵A是关系E的关系矩阵。在第四章中，曾经把合成关系定义成这样一种关系：如果存在一个结点vk，能使viEvk和vkEvj，则必有viE2vj。换句话说，从vi到vj如果至少存在一条长度为2的路径的话，那么E2的关系矩阵中的(i,j)元素值是1。这就说明了，矩阵A(2)是关系E2的关系矩阵。与此类似，A(3)是V中的关系的关系矩阵，类推。,设E1和E2是V中的两种关系，并且A1和A2分别是E1和E2的关系矩阵。于是,关系和的关系矩阵分别是和。,42/41,闭包,对于集合V中的关系E来说，E的可传递闭包E+应是,可传递闭包E+的关系矩阵应为：,式中的A是关系E的关系矩阵。如果|V|=n，则图中的基本路径或基本循环的长度不会超过n。因此,可见，矩阵A+与路径矩阵P相同。计算关系的可传递闭包等同于计算对应关系图的路径矩阵。,43/41,可达性矩阵判断强分图,由路径矩阵P可以求得含有给定图的任何特定结点的强分图。,设是一个简单有向图，并且G。P是图G的路径矩阵，PT是矩阵P的转置。设矩阵P中的(i,j)元素为Pij，而矩阵PT中的(i,j)元素为PijT。试定义一个矩阵，使得它的(i,j)元素为。于是，矩阵中的第i行，就确定了含有结点vi的强分图。,44/41,可达性矩阵判断强分图,45/41,利用简单有向图的可达矩阵，能够确定某过程是否为递归的。假设VPrg=p1，p2，pn是程序Prg中的过程集合，做有向图G=，其中piVPrg，i=1，2，n；Eiffpi调用pj。如果图G中有包含pi的回路，则断言pi是递归的。为此，由图G的邻接矩阵A=(aij)计算出关系矩阵A+=(aij)。如果A+中的主对角线上的某元素=1，则pi是递归的,可达性矩阵判断递归过程,46/41,例如，已知程序Prg中的过程集合VPrg=p1，p2，p3，p4，p5，其过程的调用关系可表成下图所示的有向图，该图的邻接矩阵A为。A=,可达性矩阵判断递归过程,图16.4.6,47/41,于是可求得A+:A+=由此可知，p2，p4和p5是递归的。,可达性矩阵判断递归过程,48/41