小点基问题课件

1、第六章第六章 最小点基问题最小点基问题 先看一个例子先看一个例子. .图图6.1.16.1.1中画了一个有向图中画了一个有向图, ,它它的每一个顶点的每一个顶点v vi i代表篮球队的一个队员代表篮球队的一个队员, ,它的弧代它的弧代表的意思是：如果有一条从表的意思是：如果有一条从v vi i出发而指向出发而指向v vj j的弧的弧,就表示队员就表示队员v vi iv vj j. .现在教练想要通知全体队现在教练想要通知全体队员都来练球员都来练球. .请你帮教练考虑一下请你帮教练考虑一下, ,他至少要通知他至少要通知几个队员几个队员( (然后由这些队员再转告其他队员然后由这些队员再转告其他队员

2、),),才能才能使所有队员都被通知到使所有队员都被通知到. .6.1 什么是最小点基问题什么是最小点基问题 小点基问题小点基问题 小点基问题 小点基问题小点基问题 前面我们学习过强连通分支的概念前面我们学习过强连通分支的概念.显然，我们有显然，我们有如下求强连通分支的方法：首先任意取一个顶点如下求强连通分支的方法：首先任意取一个顶点vi，然后把所有与然后把所有与vi互相可达的顶点互相可达的顶点vj都找出来都找出来,这些顶点这些顶点的集合的集合S1(注意注意vi也属于也属于S1)生成的子图生成的子图S1(就是就是S1和所和所有起点和终点都属于有起点和终点都属于S1的弧组成的那个子图的弧组成的那个

3、子图)就是包含就是包含vi的强连通分支的强连通分支,然后再取一个不属于然后再取一个不属于S1的顶点的顶点vk,再求再求出与出与vk互相可达的顶点集合互相可达的顶点集合S2,再生成一个强连通分支再生成一个强连通分支S2,.,最后就可以把所有强连通分支都求出来了最后就可以把所有强连通分支都求出来了.6.2 求强连通分支的方法求强连通分支的方法 但是怎样从但是怎样从vi求求S1呢？呢？小点基问题小点基问题小点基问题小点基问题小点基问题小点基问题 小点基问题 小点基问题小点基问题 例如在图例如在图6.2.3中中,取不属于取不属于S1的顶点的顶点v9,不难算出不难算出,v9的的后代集合后代集合R=v9,

4、前代集合前代集合P=v7,v8,v9,v10,v11,所以所以S2=v9,当然它生成的子图也只包含当然它生成的子图也只包含v9一个顶点一个顶点,而不包而不包含任何弧含任何弧.继续做下去继续做下去,最后可看出最后可看出,图图6.2.3中的有向图共中的有向图共有八个强连通分支有八个强连通分支,它们分别是由：它们分别是由：S1=v7,v8,S2=v9,S3=v10,S4=v11,S5=v12,S6=v4,v6,S7=v5,S8=v1,v2,v3生成的生成的.小点基问题6.3 问题问题1与问题与问题2的解的解 定义定义6.3.1 6.3.1 设设SSi i 是有向图是有向图G G的一个强连通分支的一个

5、强连通分支, ,如如果在果在G G中中, ,不存在终点属于不存在终点属于SSi i 而起点不属于而起点不属于SSi i 的弧的弧, ,就就称称SSi i 为最高的强连通分支为最高的强连通分支. .小点基问题S1=v7,v8，S2=v9，S3=v10，S4=v11，S5=v12，S6=v4,v6，S7=v5，S8=v1,v2,v3. 现在就用这个定义来判断一下现在就用这个定义来判断一下. .图图6.3.16.3.1的八个强的八个强连通分支中连通分支中, ,哪几个是最高的哪几个是最高的. .小点基问题 小点基问题 按照上面讲的三个步骤来解决前面讲的教练下通按照上面讲的三个步骤来解决前面讲的教练下通

6、知问题就很容易了知问题就很容易了. .由前面已经求出来的结果可知：图由前面已经求出来的结果可知：图6.1.16.1.1中的图的所有强连通分支：中的图的所有强连通分支：S1=v7,v8，S2=v9，S3=v10，S4=v11，S5=v12，S6=v4,v6，S7=v5，S8=v1,v2,v3. 又已知：最高的强连通分支有三个：又已知：最高的强连通分支有三个：SS1 1,S,S4 4,S,S8 8 因此因此, ,只要再按步骤只要再按步骤3,3,从从SS1 1,S,S4 4,S,S8 8 中各任意取中各任意取一个顶点一个顶点, ,例如从例如从SS1 1 中取中取v v8 8、SS4 4 中取中取v

7、v1111、SS8 8 中取中取v v3 3, ,得到的得到的B1=vB1=v3 3,v,v8 8,v,v1111 就是一个最小点基了就是一个最小点基了. .小点基问题S1=v7,v8，S2=v9，S3=v10，S4=v11，S5=v12，S6=v4,v6，S7=v5，S8=v1,v2,v3.另外：另外：B B2 2=v=v2 2,v,v8 8,v,v1111 ，B B3 3=v=v1 1,v,v7 7,v,v1111,也都是最小点也都是最小点基基. .因此教练可以只通知因此教练可以只通知v v3 3,v,v8 8, , 和和v v1111；也可以只通知；也可以只通知v v1 1,v,v7 7

8、,v,v1111. .不难看出不难看出, ,这个问题一共有六个不同的最小点这个问题一共有六个不同的最小点基基. . 分析一下上面的三个计算步骤分析一下上面的三个计算步骤, ,就会看出这些步骤就会看出这些步骤都是比较容易做的都是比较容易做的, ,稍微麻烦些的恐怕还是步骤稍微麻烦些的恐怕还是步骤1.1.但是但是, ,要证明用上面这三个步骤求出来的一定是最小点基要证明用上面这三个步骤求出来的一定是最小点基, ,也也就是说就是说, ,证明上面讲的方法是正确的，需要花些功夫证明上面讲的方法是正确的，需要花些功夫. .小点基问题 最后最后, ,再讲一下问题再讲一下问题2 2的解法的解法. .表面上看表面上看, ,似乎问题似乎问题2 2要比问题要比问题1 1复杂复杂, ,其实不然其实不然, ,这两个问题的复杂程度是差这两个问题的复杂程度是差不多的不多的. .要求一个权最小的点基要求一个权最小的点基, ,也需要进行三个步骤也需要进行三个步骤, ,其中步骤其中步骤1 1和步骤和步骤2 2与求最小点基完全一样与求最小点基完全一样, ,而步骤而步骤3 3则要则要改为：改为： 步骤步骤3 3 从每一个最高的强连通分支中取一个权最从每一个最