5第五章-最小树问题

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