5第五章 最小树问题课件.pptVIP

第五章 最小树问题; 图5.1.1(a)、(b)中画的都是树的例子.; 前面已经讲过，所谓图G=(V,E)的支撑子图，指的是G的一个子图G1=(V1,E1)，其中V1=V，即G1是由G的全部顶点及一部分边组成的.对于我们来说，特别重要的是图G(G本身不一定是树)的那些形成树的支撑子图.; 是不是每个图G都有支撑树呢？不见得.很显然，如果G不连通，G就一定不会有支撑树.反过来，我们有:; 从破圈的过程可以看出，一个连通图G一般有许多支撑树.因为取定一个圈后，可以从这个圈上任意去掉一条边.去掉的边不一样，得到的支撑树就不同..; 现在的问题是如何从G的所有支撑树中，把长度最小的支撑树找出来？.; 考虑一下，就可以看出，这个问题的关键是决定图上哪些边上架线，哪些边上不架线.设架线的边的集合是E1,那么G1=(V,E1)就是G的一个支撑子图.因为架线后各个村之间都能通话，所以G1必须是连通的.因此要使电线最节约，就是要从G的所有连通的支撑子图中，把总边长最小的找出来，但是不难看出，总边长最小的连通支撑子图一定不会含圈，从而必定是一个支撑树.因此假设电线的问题就归结为最小树问题.; 本节我们来看看关于树的一些等价定义.; 这个图的每个顶点的度数都大于等于2.先任意取一个顶点，例如取v4，并且令p={v4}.因为deg(v4)≥2，所以一定有与v4关联的边，任取一条这样的边，例如取e4，把e4及它的另一个端点v2加到p中去，使p扩大成p={v4,e4,v2}.然后再取一条与v2关联，而不属于p的边.因为deg(v2)≥2，这样的边是一; 情况1：vi′是第一次出现在p中.这时，因为deg(vi′)≥2，所以一定还有与vi′关联而不属于p的边，取一条这样的边，把它及它的不同于vi′的另一个端点加入p，p就可以扩大了.; 例如，前面已扩大到p={v4,e4,v2,e1,v1}了.看一下v1，因为v1是第一次出现在p中，属于情况1，故可以继续扩大，例如可以把e2与v3加到p中去.再看v3，仍是第一次出现，再扩大p，例如取e3与v2，即扩大成：; 引理5.2.2 设T=(V,E)为一个树，并且T至少有两个顶点，那么T一定有树叶.; 证明：设T=(V,E)是树，如果T只有两个顶点，定理显然成立，现设T有不止两个顶点.由引理5.2.2知，T有树叶.设vi是一个树叶，根据树叶的定义,应只有一条边与vi关联,设这条边是ej,不难看出,由于T中有不止两个顶点,从T中去掉vi与ej,剩下的仍是一个树T1.因为T1的边数和顶点数比G的边数和顶点数都小1.所以只要能够证明T1的边数比顶点数少1，也就证明了T的边数比顶点数少1,从而也就证明了定理.; 重要的是，我们还可以证明： 定理5.2.2 设图G是连通的，并且边数比顶点数少1，那么G是树. 定理5.2.3 设图G没有圈，并且边数等于顶点数减1，则G是树.; 在树的定义中，我们把具有上述性质(1)(2)的图叫做树，在证明了前面几个定理以后，我们就可以把树定义为具有性质(1)(3)或具有性质(2)(3)的图了.也就是说，树这个概念可以有三种不同的方法来下定义.这三种定义当然本质上是一样的，在数学中，一般称之为等价的定义.; 求连通图的最小树的方法很多，我们只讲其中的两种.第一种叫做破圈法.这个方法可以用一句口诀来概括，就是： 任取一个圈，去掉圈上最长的边.; G有好几个圈，现在任取一个，例如就取： P1={v1,v2,v4,v1}. 这个圈上有三条边，最长的是(v1,v4),长度是5，我们就把这条边去掉，从而也就把p1破掉了.; 接下去,再看看剩下的图中还有没有圈.如果没有,那么计算就结束了；如果有，就再任意取一个圈，再去掉圈上的最长边，把这个圈破掉，，直到剩下的图上没有圈(或图上的边数等于顶点数减1)时为止.;v1; 再介绍一种求最小树的方法，叫做加边法.它与破圈法的做法正好相反.破圈法是从原来的图中逐步去掉边，每次删边的时候，要保持住图的连通性(从圈上去掉边，余下的图一定仍旧是连通的)，直到图中没有圈为止.加边法正好相反，它一开始先把图中的边去掉，只留下孤立的顶点，然后逐步的把边加上去，每次加的时候，要保持住“没有圈”这一性质，在加了n-1条边(n是顶点个数)后，就得到要求的最小树了.; 步骤1 把图G的m条边按从短到长的次序重新编号,即把最短的边叫做e1,次短的边叫做e2, …,最长的叫做em.;开始：对G的边重新编号，使l(e1) ≤l(e2) ≤…≤l(em);例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，