《小树问题》PPT课件.ppt
《《小树问题》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《小树问题》PPT课件.ppt(26页珍藏版)》请在三一办公上搜索。
1、第五章 最小树问题,这一章讲的最小树问题,是图论中有一个很重要的极值问题,它的重要性不亚于最短路问题.,5.1 什么是最小树问题,定义5.1.1 设G=(V,E)是一个无向图,如果它具有下述两个性质:(1)连通;(2)没有圈就称G是一个树(或一棵树).,图5.1.1(a)、(b)中画的都是树的例子.,图,注:树中度为1的顶点称为树叶,度大于1的顶点称为枝点或分支点.,前面已经讲过,所谓图G=(V,E)的支撑子图,指的是G的一个子图G1=(V1,E1),其中V1=V,即G1是由G的全部顶点及一部分边组成的.对于我们来说,特别重要的是图G(G本身不一定是树)的那些形成树的支撑子图.,定义5.1.2
2、 设G=(V,E)是一个无向图,如果T=(V,E1)是G的支撑子图并且T是树,则称T是G的一个支撑树.,图,是不是每个图G都有支撑树呢?不见得.很显然,如果G不连通,G就一定不会有支撑树.反过来,我们有:,定理5.1.1 连通图一定有支撑树.,证明:设G是一个连通图,如果G没有圈,那么G本身就是一个支撑树,如果G有圈,那么任取G的一个圈,并且从这个圈中任意去掉一条边,得到G的一个支撑子图G1,易见G1仍是连通的,如果G1还有圈,就再从某一个圈中去掉一条边,得到G2,G2仍是连通的,这样做下去,直至得到一个不含圈的连通支撑子图Gs为止,Gs就是G的一个支撑树了.,按定理的证明方法得到一个支撑树的
3、过程成为“破圈法”。,从破圈的过程可以看出,一个连通图G一般有许多支撑树.因为取定一个圈后,可以从这个圈上任意去掉一条边.去掉的边不一样,得到的支撑树就不同.,现在考虑一个连通图G=(V,E),它的每一条边ej有一个长度l(ej)0.这时,对于G的任意一个支撑树T,我们把属于T的各条边的长度加起来的和叫做树T的长度,记作l(T).如下图:l(T1)=22,l(T2)=17.,b:T1,c:T2,图,现在的问题是如何从G的所有支撑树中,把长度最小的支撑树找出来?.,通常,我们把长度最小的支撑树叫做最小树.所以上面的问题实际上就是如何把一个图G的最小树找出来.因此这个问题就叫做最小树问题.,最小树
4、问题有很多很广泛的应用.例如,我们把图5.1.3(a)的图G中的五个顶点看成某个镇的5个村,G的边看成是公路,现在要假设电线(电线必须沿着公路假设),使各村之间都能通电话,问应该怎样架线,才能使所用的电线最少?,考虑一下,就可以看出,这个问题的关键是决定图上哪些边上架线,哪些边上不架线.设架线的边的集合是E1,那么G1=(V,E1)就是G的一个支撑子图.因为架线后各个村之间都能通话,所以G1必须是连通的.因此要使电线最节约,就是要从G的所有连通的支撑子图中,把总边长最小的找出来,但是不难看出,总边长最小的连通支撑子图一定不会含圈,从而必定是一个支撑树.因此假设电线的问题就归结为最小树问题.,类
5、似的问题还有很多,例如修公路把一些城镇连接起来,修渠道使水源和各块地连接起来,等等,都可以归结为最小树问题.同时,最小树问题还是图论中其它很多问题的基础,也就是说,有不少的问题在计算时,往往首先必须求出一个最小树,这也是最小树问题显得特别重要的一个原因.,本节我们来看看关于树的一些等价定义.,定理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的一条简
6、单了p,开始时,p只含一个顶点,以后逐步扩大,然后证明,扩大若干次后,p中一定会出现圈,当然,这就证明了G中一定有圈.我们结合图来证明.,这个图的每个顶点的度数都大于等于2.先任意取一个顶点,例如取v4,并且令p=v4.因为deg(v4)2,所以一定有与v4关联的边,任取一条这样的边,例如取e4,把e4及它的另一个端点v2加到p中去,使p扩大成p=v4,e4,v2.然后再取一条与v2关联,而不属于p的边.因为deg(v2)2,这样的边是一,定存在的,例如可以取e1,把e1及它的另一个端点v1再加入p,使p扩大成p=v4,e4,v2,e1,v1,这样做下去,p中每增加一条边ej与一个顶点vi后,
7、就应该看一看,它属于下面两种情况中的哪一种:,情况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久可以不断地扩大下去.这个矛盾说明,经过若干次扩大后,一
8、定会出现情况2.,例如,前面已扩大到p=v4,e4,v2,e1,v1了.看一下v1,因为v1是第一次出现在p中,属于情况1,故可以继续扩大,例如可以把e2与v3加到p中去.再看v3,仍是第一次出现,再扩大p,例如取e3与v2,即扩大成:,p=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.如
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 小树问题 小树 问题 PPT 课件
链接地址:https://www.31ppt.com/p-5500200.html