《小点基问题》PPT课件.ppt

《《小点基问题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《小点基问题》PPT课件.ppt（23页珍藏版）》请在三一办公上搜索。

1、第六章 最小点基问题,先看一个例子.图中画了一个有向图,它的每一个顶点vi代表篮球队的一个队员,它的弧代表的意思是：如果有一条从vi出发而指向vj的弧,就表示队员vi能够通知vj.现在教练想要通知全体队员都来练球.请你帮教练考虑一下,他至少要通知几个队员(然后由这些队员再转告其他队员),才能使所有队员都被通知到.,6.1 什么是最小点基问题,例如教练通知了v1,那么v1可以再通知v3,v3又能转告v2,v5.不难看出,如果教练通知了v1,v6,v7,v11,那么只要按图画的那样做,全部队员就都能接到通知了.,但是,是不是至少通知四个队员呢？能不能再少通知几个呢？,大家试一下就可以知道,通知三个

2、人就够了,例如可以只通知v1,v7,v11,而且再少就不可能了.,上面这个例子很简单,通过简单的分析,试验就知道至少要通知三个人.但是如果遇到一个类似的问题,但是图中的顶点很多,那么仅仅靠试验就不行了.必须要有系统的方法.,本章的主要目的就是介绍解决这类问题的一种方法.,前面已经学习过可达的概念：由vi可达vj是指如果存在一条从顶点vi到顶点vj的有向路.再引入一个概念：,定义6.1.1 设G=(V,A)是一个有向图,vi与vj是G的两个顶点,如果由vi可达vj,就称vi是vj的前代,而称vj是vi的后代.,这个概念在我们刚才考虑的下通知问题中是很重要的,因为如果教练通知了vi,那么所有vi的

3、后代vj就都可以间接的得到通知了,而要保证所有队员都得到通知,由教练直接通知的队员的集合B必须具有下面的性质：“对于任意个队员vj，一定存在B中的一个vi,使得vi是vj的前代.”或者说,B的所有后代包括了G的所有顶点.按照上面的分析,可以给出下面的定义：,定义6.1.2 设G=(V,A)是一个有向图,B是若干个顶点的集合,或者说B是V的子集.如果对于任意的vjV,都存在一个viB,使得vi是vj的前代,则称B是一个点基.,例如刚才讲的，在图的图G中,B1=v1,v6,v7,v11及B2=v1,v7,v11都是点基.有了点基这个概念，便可以提出我们要解决的问题了.,问题1 求一个包含顶点最少的

4、点基(这样的点基今后叫最小点基).问题2 设图G的每一个顶点vi都对应一个非负数ai(ai叫做vi的权),现在要求一个点基,使得它所包含的顶点对应的ai之和最小(这样的点基今后叫权最小的点基).,显然,前面讲的下通知问题可以归结为问题1.另外如果教练通知队员vi时必须付出一定的代价ai(例如ai可以代表教练给vi打电话所需的时间),那么,如果教练考虑如何以最小的代价使所有队员都能得到通知,就会遇到求权最小的点基问题,即问题2.,前面我们学习过强连通分支的概念.显然，我们有如下求强连通分支的方法：首先任意取一个顶点vi，然后把所有与vi互相可达的顶点vj都找出来,这些顶点的集合S1(注意vi也属

5、于S1)生成的子图S1(就是S1和所有起点和终点都属于S1的弧组成的那个子图)就是包含vi的强连通分支,然后再取一个不属于S1的顶点vk,再求出与vk互相可达的顶点集合S2,再生成一个强连通分支S2,.,最后就可以把所有强连通分支都求出来了.,6.2 求强连通分支的方法,但是怎样从vi求S1呢？,由定义不难看出,如果顶点vi与vj互相可达,那么vj既是vi的后代(因为由vi可达vj),又是vi的前代(因为由vj可达vi).因此,要求所有与vi互相可达的顶点集合S1,只要先求出vi的所有后代的集合R,再求出vi的所有前代的集合P.然后找出所有既属于R又属于P的顶点,这些顶点就组成了集合S1.,为

6、了求出vi的所有后代的集合R,也可以采用一种标号法,在这种标号法中,一旦能确定一个顶点是vi的后代,就给它一个标号“+”.具体计算时,首先给vi以标号“+”,这是因为vi可达vi自己,因此vi本身也是vi的后代.然后逐步扩大已标号的范围,办法是：如果发现一个顶点vk是已标号的,而又存在一条以vk为起点的弧(k,j),这时,如果vj还没有得到标号,就可以给vj以标号“+”.,这样做的道理很简单,因为vk有标号,说明它是vi的后代,即存在一条从vi到vk的有向路,这条有向路接上弧就是一条从vi到vj的有向路(如图6.2.1),因此vj也是vi的后代.这样不断扩大已标号顶点的范围,直到无法扩大为止,

7、这时，所有已标号的顶点就恰好是vi的后代的集合R了.,vi,vj,vk,+,+,+,+,+,+,图,例如在图中，要求v7的所有后代的集合R,首先在v7旁边标上“+”,因为v7有标号,是以v7为起点的弧,所以v4也可以得到标号,v4又可以使v6得到标号,v7又可以使v12得到标号,最后,在v7,v4,v6,v12,v8,v9六个顶点得到标号后,就无法再扩大标号点的范围了,因此,R就包含上述六个顶点.,+,+,+,+,+,+,当一个图顶点和弧很多时，为了使标号过程有条不紊,从而避免重复,通常在考虑一个有标号的顶点vk时,应该把所有从vk出发的弧都考察一遍,如果的终点vj还没有标号,就给它标上号.考

8、察完以后,顶点vk就可以认为已经“检查”过了,今后就不必再考虑它了(因为它再也不会使别的顶点得到标号了),然后再取一个已标号的顶点而没有“检查”过的顶点来考虑,如果发现所有有标号的顶点都已经被检查过了,那么狠显然,已经不能再扩大已标号点的范围了.,仍以图为例，在给v7以标号以后,只有v7一个点是已标号而未检查的,考虑v7,这时,应该把所有从v7出发的弧全考虑一遍,这里有、和三条,因此v4,v8和v12都可以得到标号.这时,v7已检查完了,因此,我们在v7的标号+外面画一个圈,表示它已经检查过了(见图6.2.2).,然后再取一个已标号而未检查过的顶点.例如取v12,没有从v12出发的弧,因此,考

9、虑v12的结果没有使任何顶点得到标号.但v12仍算已检查过了,所以在它旁边的+外面也画一个圈.余下的类似可做.,把上面讲的总结起来,就可以得到下面的求顶点vi的所有后代的集合R的计算方法了：,步骤1 给vi以标号+,vi是已标号而未检查的顶点.步骤2 看看是否有已标号而未检查的顶点,如果没有,计算结束,所有已标号的顶点就组成集合R.如果有,任取一个这样的顶点vk,转入步骤3.步骤3 找出以vk为起点的所有弧,一条一条地考虑这些弧,如果的终点vj没有标号,就给vj以标号+,vj成为已标号而未检查的顶点.这些弧都考虑过以后,vk成为已检查过的,在它旁边的+外面画一个圈,转回步骤2.,如果想求顶点v

10、i的所有前代的集合P,可以采用与上面完全相似的方法.步骤1和步骤2是一样的,唯一的差别是步骤3,本来,在取定了vk以后,考虑的是以vk为起点的弧,现在则应该改为考虑以vk为终点的弧,如果这条弧的起点vj还没有标号,就应该给它以标号.另外,为了在一张图上同时求vi的所有前代与后代,那么，在求前代时，可以用“-”作为标号.,仍以图中的图为例,现在来求v7的前代的集合P,在给v7以标号“-”以后,考虑以v7为终点的弧,这里只有一条,因此v8也可以得到标号,但是,别的顶点再也得不到标号了,因此P=v7,v8.,在右图中,标有+的顶点是v7的后代,标有-的顶点是v7的前代,因此,很显然,既标有+又标有-

11、的顶点就是与v7互相可达的顶点了,从右图可以看出,这种顶点只有v7与v8两个,因此,与v7对应的S1=v7,v8.,在求出了一个强连通分支S1以后,应该看看,是不是有不属于它的顶点,有的话,就再任意取一个不属于S1的顶点vj,再求出包含vj的强连通分支S2；然后再取一个既不属于S1也不属于S2的顶点vk,直到每一个顶点都属于一个强连通分支为止.,例如在图中,取不属于S1的顶点v9,不难算出,v9的后代集合R=v9,前代集合P=v7,v8,v9,v10,v11,所以S2=v9,当然它生成的子图也只包含v9一个顶点,而不包含任何弧.继续做下去,最后可看出,图中的有向图共有八个强连通分支,它们分别是

12、由：S1=v7,v8,S2=v9,S3=v10,S4=v11,S5=v12,S6=v4,v6,S7=v5,S8=v1,v2,v3生成的.,6.3 问题1与问题2的解,问题1 求一个包含顶点最少的点基(这样的点基今后叫最小点基).问题2 设图G的每一个顶点vi都对应一个非负数ai(ai叫做vi的权),现在要求一个点基,使得它所包含的顶点对应的ai之和最小(这样的点基今后叫权最小的点基).,定义6.3.1 设Si是有向图G的一个强连通分支,如果在G中,不存在终点属于Si而起点不属于Si的弧,就称Si为最高的强连通分支.,S1=v7,v8，S2=v9，S3=v10，S4=v11，S5=v12，S6=

13、v4,v6，S7=v5，S8=v1,v2,v3.,现在就用这个定义来判断一下.图的八个强连通分支中,哪几个是最高的.,问题1的解法：,步骤1 找出图G=(V,A)的所有强连通分支.步骤2 从强连通分支中找出所有最高的强连通分支.步骤3 从每个最高的强连通分支中任意取一个顶点,组成的顶点集合B就是G的一个最小点基.,按照上面讲的三个步骤来解决前面讲的教练下通知问题就很容易了.由前面已经求出来的结果可知：图中的图的所有强连通分支：,S1=v7,v8，S2=v9，S3=v10，S4=v11，S5=v12，S6=v4,v6，S7=v5，S8=v1,v2,v3.,又已知：最高的强连通分支有三个：S1,S

14、4,S8,因此,只要再按步骤3,从S1,S4,S8中各任意取一个顶点,例如从S1中取v8、S4中取v11、S8中取v3,得到的B1=v3,v8,v11就是一个最小点基了.,S1=v7,v8，S2=v9，S3=v10，S4=v11，S5=v12，S6=v4,v6，S7=v5，S8=v1,v2,v3.,另外：B2=v2,v8,v11，B3=v1,v7,v11,也都是最小点基.因此教练可以只通知v3,v8,和v11；也可以只通知v1,v7,v11.不难看出,这个问题一共有六个不同的最小点基.,分析一下上面的三个计算步骤,就会看出这些步骤都是比较容易做的,稍微麻烦些的恐怕还是步骤1.但是,要证明用上面这三个步骤求出来的一定是最小点基,也就是说,证明上面讲的方法是正确的，需要花些功夫.,最后,再讲一下问题2的解法.表面上看,似乎问题2要比问题1复杂,其实不然,这两个问题的复杂程度是差不多的.要求一个权最小的点基,也需要进行三个步骤,其中步骤1和步骤2与求最小点基完全一样,而步骤3则要改为：,步骤3 从每一个最高的强连通分支中取一个权最小的顶点,组成的顶点集合B就是G的一个权最小的点基.,S1=v7,v8，S2=v9，S3=v10，S4=v11，S5=v12，S6=v4,v6，S7=v5，S8=v1,v2,v3.,1,3,6,7,9,5,2,3,5,4,8,2,