5第五章-最小树问题课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 最小树问题,这一章讲的最小树问题，是图论中有一个很重要的极值问题，它的重要性不亚于最短路问题,.,5.1,什么是最小树问题,定义,5.1.1,设,G=(V,E),是一个无向图，如果它具有下述两个性质：,(1),连通；,(2),没有圈,就称,G,是一个树（或一棵树）,.,图,5.1.1(a),、,(b),中画的都是树的例子,.,(a)G,1,(b)G,2,图,注：树中度为,1,的顶点称为树叶，度大于,1,的顶点称为枝点或分支点,.,前面已经讲过，所谓图,G=(V,E),的支撑子图，指的是,G,的一个子图,G,1,=(V,1,E,1,),，其中,V,1,=V,，即,G,1,是由,G,的全部顶点及一部分边组成的,.,对于我们来说，特别重要的是图,G(G,本身不一定是树,),的那些形成树的支撑子图,.,定义,5.1.2,设,G=(V,E),是一个无向图，如果,T=(V,E,1,),是,G,的支撑子图并且,T,是树，则称,T,是,G,的一个支撑树,.,图,是不是每个图,G,都有支撑树呢？不见得,.,很显然，如果,G,不连通，,G,就一定不会有支撑树,.,反过来，我们有,:,定理,5.1.1,连通图一定有支撑树,.,证明：设,G,是一个连通图，如果,G,没有圈，那么,G,本身就是一个支撑树，如果,G,有圈，那么任取,G,的一个圈，并且从这个圈中任意去掉一条边，得到,G,的一个支撑子图,G,1,易见,G,1,仍是连通的，如果,G,1,还有圈，就再从某一个圈中去掉一条边，得到,G,2,，,G,2,仍是连通的，,，这样做下去，直至得到一个不含圈的连通支撑子图,G,s,为止，,G,s,就是,G,的一个支撑树了,.,按定理的证明方法得到一个支撑树的过程成为“破圈法”。,从破圈的过程可以看出，一个连通图,G,一般有许多支撑树,.,因为取定一个圈后，可以从这个圈上任意去掉一条边,.,去掉的边不一样，得到的支撑树就不同,.,现在考虑一个连通图,G=(V,E),，它的每一条边,e,j,有一个长度,l(e,j,)0.,这时，对于,G,的任意一个支撑树,T,，我们把属于,T,的各条边的长度加起来的和叫做树,T,的长度，记作,l(T).,如下图：,l(T,1,)=22,l(T,2,)=17.,v,1,v,2,v,3,v,4,v,5,5,8,6,2,3,6,5,v,1,v,2,v,3,v,4,v,5,5,8,6,2,3,6,5,v,1,v,2,v,3,v,4,v,5,5,8,6,2,3,6,5,a:G,b:T,1,c:T,2,图,现在的问题是如何从,G,的所有支撑树中，把长度最小的支撑树找出来？,.,通常，我们把长度最小的支撑树叫做最小树,.,所以上面的问题实际上就是如何把一个图,G,的最小树找出来,.,因此这个问题就叫做最小树问题,.,最小树问题有很多很广泛的应用,.,例如，我们把图,5.1.3(a),的图,G,中的五个顶点看成某个镇的,5,个村，,G,的边看成是公路，现在要假设电线,(,电线必须沿着公路假设,),，使各村之间都能通电话,问应该怎样架线，才能使所用的电线最少？,考虑一下，就可以看出，这个问题的关键是决定图上哪些边上架线，哪些边上不架线,.,设架线的边的集合是,E,1,那么,G,1,=(V,E,1,),就是,G,的一个支撑子图,.,因为架线后各个村之间都能通话，所以,G,1,必须是连通的,.,因此要使电线最节约，就是要从,G,的所有连通的支撑子图中，把总边长最小的找出来，但是不难看出，总边长最小的连通支撑子图一定不会含圈，从而必定是一个支撑树,.,因此假设电线的问题就归结为最小树问题,.,类似的问题还有很多，例如修公路把一些城镇连接起来，修渠道使水源和各块地连接起来，等等，都可以归结为最小树问题,.,同时，最小树问题还是图论中其它很多问题的基础，也就是说，有不少的问题在计算时，往往首先必须求出一个最小树，这也是最小树问题显得特别重要的一个原因,.,本节我们来看看关于树的一些等价定义,.,定理,5.2.1,设,T=(V,E),是一个树，设,T,有,m,条边，,n,个顶点，则,m=n-1.,5.2,树的等价定义,在证明这个定理之前，我们先看一些引理,.,引理,5.2.1,设,G=(V,E),是一个图，它的每一个顶点的度数都满足,deg(v,i,),2，那么,G,一定有圈,.,证明：证明的方法是：从任意一个顶点开始，来构造,G,的一条简单了,p,，开始时，,p,只含一个顶点，以后逐步扩大，然后证明，扩大若干次后，,p,中一定会出现圈,当然，这就证明了,G,中一定有圈,.,我们结合图来证明,.,v,1,v,3,v,2,v,4,v,5,e,1,e,3,e,4,e,5,e,6,e,2,图,5.2.1,这个图的每个顶点的度数都大于等于,2.,先任意取一个顶点，例如取,v,4,，并且令,p=v,4,.,因为,deg(v,4,),2,，所以一定有与,v,4,关联的边，任取一条这样的边，例如取,e,4,，把,e,4,及它的另一个端点,v,2,加到,p,中去，使,p,扩大成,p=v,4,e,4,v,2,.,然后再取一条与,v,2,关联，而不属于,p,的边,.,因为,deg(v,2,),2,，这样的边是一,v,1,v,3,v,2,v,4,v,5,e,1,e,3,e,4,e,5,e,6,e,2,图,5.2.1,定存在的，例如可以取,e,1,，把,e,1,及它的另一个端点,v,1,再加入,p,，使,p,扩大成,p=v,4,e,4,v,2,e,1,v,1,，,，这样做下去，,p,中每增加一条边,e,j,与一个顶点,v,i,后，就应该看一看，它属于下面两种情况中的哪一种：,情况,1,：,v,i,是第一次出现在,p,中,.,这时，因为,deg(v,i,),2,，所以一定还有与,v,i,关联而不属于,p,的边，取一条这样的边，把它及它的不同于,v,i,的另一个端点加入,p,，,p,就可以扩大了,.,情况,2,：,v,i,是第二次出现在,p,中,.,这时不必再扩大,p,了,.,因为,p,中从上一次出现,v,i,到这次出现,v,i,中的一段就是一个圈,.,因此，只要情况,2,一出现，就找到圈了,.,那么，情况,2,是不是一定会出现呢？一定会的,.,这是因为,p,是简单路,即每一条边在,p,中只出现一次，而图的总边数是有限的，因此，,p,不能无限的扩大,.,要是在扩大,p,的过程中只是出现情况,1,，那么,p,久可以不断地扩大下去,.,这个矛盾说明，经过若干次扩大后,一定会出现情况,2.,例如，前面已扩大到,p=v,4,e,4,v,2,e,1,v,1,了,.,看一下,v,1,，因为,v,1,是第一次出现在,p,中，属于情况,1,，故可以继续扩大，例如可以把,e,2,与,v,3,加到,p,中去,.,再看,v,3,，仍是第一次出现，再扩大,p,，例如取,e,3,与,v,2,，即扩大成：,v,1,v,3,v,2,v,4,v,5,e,1,e,3,e,4,e,5,e,6,e,2,图,5.2.1,p=v,4,e,4,v,2,e,1,v,1,e,2,v,3,e,3,v,2,检查,v,2,v,2,是第二次出现，这属于情况,2,，故不必再扩大了，因为,p,中已出现了圈,v,2,e,1,v,1,e,2,v,3,e,3,v,2,.,证毕,引理,5.2.2,设,T=(V,E),为一个树，并且,T,至少有两个顶点，那么,T,一定有树叶,.,证明：因为,T,是树，所以,T,是连通的，,T,不会有孤立顶点，即每一个顶点,v,i,的度数,deg(v,i,)0.,如果,T,没有树叶，即,T,的每个顶点的度数都大于等于,2,，那么，由引理知，,T,含有圈，这就与,T,是树矛盾,.,证毕,.,有了这些引理，下面可以来证明定理了,.,定理,5.2.1,设,T=(V,E),是一个树，设,T,有,m,条边，,n,个顶点，则,m=n-1.,证明：设,T=(V,E),是树，如果,T,只有两个顶点，定理显然成立，现设,T,有不止两个顶点,.,由引理知，,T,有树叶,.,设,v,i,是一个树叶，根据树叶的定义,应只有一条边与,v,i,关联,设这条边是,e,j,不难看出,由于,T,中有不止两个顶点,从,T,中去掉,v,i,与,e,j,剩下的仍是一个树,T,1,.,因为,T,1,的边数和顶点数比,G,的边数和顶点数都小,1.,所以只要能够证明,T,1,的边数比顶点数少,1,，也就证明了,T,的边数比顶点数少,1,从而也就证明了定理,.,同样,因为,T,1,是树,T,1,也一定有树叶,.,如果,T,1,的顶点数,2,则再去掉一个树叶和与它关联的唯一的边可以得到树,T,2,而且只要能证明,T,2,的边数比顶点数少,1,就能证明,T,1,从而,T,的边数比顶点数少,1,了, ,这样不断的去掉树叶和边,一直得到一个只含两个顶点的树,T,为止,.,显然,T,恰含一条边,因此,T,的边数比顶点数少,1,了，倒退回去，就可以证明,T,的边数比顶点数少,1,了,.,证毕,.,重要的是，我们还可以证明：,定理,5.2.2,设图,G,是连通的，并且边数比顶点数少,1,，那么,G,是树,.,定理,5.2.3,设图,G,没有圈，并且边数等于顶点数减,1,，则,G,是树,.,上面三个定理合在一起，可以简单的说成：对于一个图来说，下面三个性质只要有两个成立，第三个也一定成立,.,(1),连通,.,(2),没有圈,.,(3),边数等于顶点数减,1.,在树的定义中，我们把具有上述性质,(1)(2),的图叫做树，在证明了前面几个定理以后，我们就可以把树定义为具有性质,(1)(3),或具有性质,(2)(3),的图了,.,也就是说，树这个概念可以有三种不同的方法来下定义,.,这三种定义当然本质上是一样的，在数学中，一般称之为等价的定义,.,上面讲的树的等价定义，在求最小树时是很有用的,.,例如下一节讲的一个计算方法，求出的是满足,(2)(3),的支撑子图，由于树的等价定义，就可以肯定它是一个支撑树了,.,求连通图的最小树的方法很多，我们只讲其中的两种,.,第一种叫做破圈法,.,这个方法可以用一句口诀来概括，就是：,任取一个圈，去掉圈上最长的边,.,5.3,求最小树的两种计算方法,我们通过一个例子把这句口诀的用法解释一下,.,就拿图中连通图为例。,v,1,v,5,v,4,v,3,v,2,5,2,8,6,3,6,5,图,5.3.1,G,有好几个圈，现在任取一个，例如就取：,P,1,=v,1,v,2,v,4,v,1,.,这个圈上有三条边，最长的是,(v,1,v,4,),长度是,5,，我们就把这条边去掉，从而也就把,p,1,破掉了,.,v,1,v,5,v,4,v,3,v,2,5,2,8,6,3,6,5,v,1,v,5,v,4,v,3,v,2,5,2,8,6,3,6,5,p,1,接下去,再看看剩下的图中还有没有圈,.,如果没有,那么计算就结束了；如果有，就再任意取一个圈，再去掉圈上的最长边，把这个圈破掉，直到剩下的图上没有圈,(,或图上的边数等于顶点数减,1),时为止,.,v,1,v,5,v,4,v,3,v,2,5,2,8,6,3,6,5,p,1,v,1,v,5,v,4,v,3,v,2,2,8,6,3,6,5,v,1,v,5,v,4,v,3,v,2,2,8,3,6,5,v,1,v,5,v,4,v,3,v,2,2,3,6,5,再介绍一种求最小树的方法，叫做加边法,.,它与破圈法的做法正好相反,.,破圈法是从原来的图中逐步去掉边，每次删边的时候，要保持住图的连通性,(,从圈上去掉边，余下的图一定仍旧是连通的,),，直到图中没有圈为止,.,加边法正好相反，它一开始先把图中的边去掉，只留下孤立的顶点，然后逐步的把边加上去，每次加的时候，要保持住“没有圈”这一性质，在加了,n-1,条边,(n,是顶点个数,),后，就得到要求的最小树了,.,加边法的具体步骤是：,步骤,1,把图,G,的,m,条边按从短到长的次序重新编号,即把最短的边叫做,e,1,次短的边叫做,e,2,最长的叫做,e,m,.,加边法的计算框图：,步骤,2,首先把图,G,的边都去掉，得到一个只含,n,个孤立点的支撑子图,.,然后，按,e,1,e,2,e,m,的次序试着向支撑子图中加边,.,对于每一条边,e,j,，要先看一看它是否和已经加进去的边形成圈,.,如果不形成圈，就把,e,j,加进去，如果形成圈，,e,j,就不能加进去，而考虑下一条边,e,j+1,一直加到得到的支撑子图含有,n-1,条边时，计算结束,.,开始：对,G,的边重新编号，使,l(e,1,),l(e,2,),l(e,m,),令支撑子图的边集合,E,=,，令,i=1,e,i,加到,E,中去是否形成圈？,计算结束,把,e,i,加到,E,中去,E,中的边数是否等于,n-1,是,否,令,i=i+1,是,否,令,i=i+1,例,1,、城市公交网,问题描述,有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。,5.4,应用,举例,下面的图表示一个,5,个城市的地图，可以得到它的最小生成树的权和为,19.,例,2,、最优布线问题（,wire.?,）,学校有,n,台计算机，为了方便数据传输，现要将它们用数据线连接起来,.,两台计算机被连接是指它们之间有数据线连接,.,由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的,.,当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的,.,为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接,.,现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）,.,在要求费用最少的情况下，如何连接？,例,3,机器蛇,在未来的某次战争中,我军计划了一次军事行动，目的是劫持敌人的航母由于这个计划高度保密，你只知道你所负责的一部分：机器蛇的通信网络,.,计划中要将数百条机器蛇投放到航母的各个角落里由于航母内部舱室、管线错综复杂，且大部分由金属构成，因此屏蔽效应十分强烈，况且还要考虑敌人的大强度电子干扰，如何保持机器蛇间的联系，成了一大难题,.,每条机器蛇的战斗位置由作战计划部门制定，将会及时通知你每条机器蛇上都带有接收、发射系统，可以同时与多条机器蛇通讯由于整个系统承载的数据量庞大，需要一个固定的通讯网络情报部门提供了极其详尽的敌方航母图纸，使你对什么地方有屏蔽了如指掌,请你设计一个程序，根据以上信息构造通讯网络,要求信息可以在任意两条机器蛇间传递，同时为了避免干扰，通讯网络的总长度要尽可能的短,