六最小点基问题.ppt

第六章 最小点基问题 先看一个例子.图6.1.1中画了一个有向图,它的每一个顶点vi代表篮球队的一个队员,它的弧代表的意思是：如果有一条从vi出发而指向vj的弧i,j,就表示队员vi能够通知vj.现在教练想要通知全体队员都来练球.请你帮教练考虑一下,他至少要通知几个队员(然后由这些队员再转告其他队员),才能使所有队员都被通知到. §6.1 什么是最小点基问题 例如教练通知了v1,那么v1可以再通知v3,v3又能转告v2,v5….不难看出,如果教练通知了v1,v6,v7,v11,那么只要按图6.1.2画的那样做,全部队员就都能接到通知了. 图6.1.1 v8 v7 v6 v5 v4 v3 v2 v1 v12 v10 v9 v11 但是,是不是至少通知四个队员呢？能不能再少通知几个呢？ 图6.1.2 v1 v7 v6 v3 v2 v5 v4 v8 v12 v11 v10 v9 教练 大家试一下就可以知道,通知三个人就够了,例如可以只通知v1,v7,v11,而且再少就不可能了. 上面这个例子很简单,通过简单的分析,试验就知道至少要通知三个人.但是如果遇到一个类似的问题,但是图中的顶点很多,那么仅仅靠试验就不行了.必须要有系统的方法. 本章的主要目的就是介绍解决这类问题的一种方法. 前面已经学习过可达的概念：由vi可达vj是指如果存在一条从顶点vi到顶点vj的有向路. 再引入一个概念： 定义6.1.1 设G=(V,A)是一个有向图,vi与vj是G的两个顶点,如果由vi可达vj,就称vi是vj的前代,而称vj是vi的后代. 这个概念在我们刚才考虑的下通知问题中是很重要的,因为如果教练通知了vi,那么所有vi的后代vj就都可以间接的得到通知了,而要保证所有队员都得到通知,由教练直接通知的队员的集合B必须具有下面的性质：“对于任意个队员vj，一定存在B中的一个vi,使得vi是vj的前代.”或者说,B的所有后代包括了G的所有顶点.按照上面的分析,可以给出下面的定义： 定义6.1.2 设G=(V,A)是一个有向图,B是若干个顶点的集合,或者说B是V的子集.如果对于任意的vj∈V,都存在一个vi∈B,使得vi是vj的前代,则称B是一个点基. 例如刚才讲的，在图6.1.1的图G中,B1={v1,v6,v7,v11}及B2={v1,v7,v11}都是点基.有了点基这个概念，便可以提出我们要解决的问题了. 问题1 求一个包含顶点最少的点基(这样的点基今后叫最小点基). 问题2 设图G的每一个顶点vi都对应一个非负数ai(ai叫做vi的权),现在要求一个点基,使得它所包含的顶点对应的ai之和最小(这样的点基今后叫权最小的点基). 显然,前面讲的下通知问题可以归结为问题1.另外如果教练通知队员vi时必须付出一定的代价ai(例如ai可以代表教练给vi打电话所需的时间),那么,如果教练考虑如何以最小的代价使所有队员都能得到通知,就会遇到求权最小的点基问题,即问题2. 前面我们学习过强连通分支的概念.显然，我们有如下求强连通分支的方法：首先任意取一个顶点vi，然后把所有与vi互相可达的顶点vj都找出来,这些顶点的集合S1(注意vi也属于S1)生成的子图[S1](就是S1和所有起点和终点都属于S1的弧组成的那个子图)就是包含vi的强连通分支,然后再取一个不属于S1的顶点vk,再求出与vk互相可达的顶点集合S2,再生成一个强连通分支[S2],...,最后就可以把所有强连通分支都求出来了. §6.2 求强连通分支的方法 但是怎样从vi求S1呢？ 由定义6.1.1不难看出,如果顶点vi与vj互相可达,那么vj既是vi的后代(因为由vi可达vj),又是vi的前代(因为由vj可达vi).因此,要求所有与vi互相可达的顶点集合S1,只要先求出vi的所有后代的集合R,再求出vi的所有前代的集合P.然后找出所有既属于R又属于P的顶点,这些顶点就组成了集合S1. 为了求出vi的所有后代的集合R,也可以采用一种标号法,在这种标号法中,一旦能确定一个顶点是vi的后代,就给它一个标号“+”.具体计算时,首先给vi以标号“+”,这是因为vi可达vi自己,因此vi本身也是vi的后代.然后逐步扩大已标号的范围,办法是：如果发现一个顶点vk是已标号的,而又存在一条以vk为起点的弧(k,j),这时,如果vj还没有得到标号,就可以给vj以标号“+”. 这样做的道理很简单,因为vk有标号,说明它是vi的后代,即存在一条从vi到vk的有向路,这条有向路接上弧k,j就是一条从vi到vj的有向路(如图6.2.1