第五章最小树问题.pptx
《第五章最小树问题.pptx》由会员分享,可在线阅读,更多相关《第五章最小树问题.pptx(25页珍藏版)》请在咨信网上搜索。
1、 图图图图5.1.1(a)5.1.1(a)5.1.1(a)5.1.1(a)、(b)(b)(b)(b)中画的都是树的例子中画的都是树的例子中画的都是树的例子中画的都是树的例子.(a)G(a)G1 1(b)G(b)G2 2图图图图5.1.15.1.1 注:树中度为注:树中度为注:树中度为注:树中度为1 1 1 1的顶点称为树叶,度大于的顶点称为树叶,度大于的顶点称为树叶,度大于的顶点称为树叶,度大于1 1 1 1的顶点的顶点的顶点的顶点称为枝点或分支点称为枝点或分支点称为枝点或分支点称为枝点或分支点.前面已经讲过,所谓图前面已经讲过,所谓图前面已经讲过,所谓图前面已经讲过,所谓图G=(V,E)G=
2、(V,E)G=(V,E)G=(V,E)的支撑子图,指的的支撑子图,指的的支撑子图,指的的支撑子图,指的是是是是G G G G的一个子图的一个子图的一个子图的一个子图G G G G1 1 1 1=(V=(V=(V=(V1 1 1 1,E,E,E,E1 1 1 1),其中,其中,其中,其中V V V V1 1 1 1=V=V=V=V,即,即,即,即G G G G1 1 1 1是由是由是由是由G G G G的全的全的全的全部顶点及一部分边组成的部顶点及一部分边组成的部顶点及一部分边组成的部顶点及一部分边组成的.对于我们来说,特别重要对于我们来说,特别重要对于我们来说,特别重要对于我们来说,特别重要的
3、是图的是图的是图的是图G(GG(GG(GG(G本身不一定是树本身不一定是树本身不一定是树本身不一定是树)的那些形成树的支撑子图的那些形成树的支撑子图的那些形成树的支撑子图的那些形成树的支撑子图.定义定义定义定义5.1.2 5.1.2 5.1.2 5.1.2 设设设设G=(V,E)G=(V,E)G=(V,E)G=(V,E)是一个无向图,如果是一个无向图,如果是一个无向图,如果是一个无向图,如果T=(V,ET=(V,ET=(V,ET=(V,E1 1 1 1)是是是是G G G G的支撑子图并且的支撑子图并且的支撑子图并且的支撑子图并且T T T T是树,则称是树,则称是树,则称是树,则称T T T
4、 T是是是是G G G G的一个的一个的一个的一个支撑树支撑树支撑树支撑树.图图图图5.1.25.1.2 是不是每个图是不是每个图是不是每个图是不是每个图G G G G都有支撑树呢?不见得都有支撑树呢?不见得都有支撑树呢?不见得都有支撑树呢?不见得.很显然,很显然,很显然,很显然,如果如果如果如果G G G G不连通,不连通,不连通,不连通,G G G G就一定不会有支撑树就一定不会有支撑树就一定不会有支撑树就一定不会有支撑树.反过来,我们反过来,我们反过来,我们反过来,我们有有有有:定理定理定理定理5.1.1 5.1.1 5.1.1 5.1.1 连通图一定有支撑树连通图一定有支撑树连通图一定
5、有支撑树连通图一定有支撑树.证明:设证明:设证明:设证明:设G G G G是一个连通图,如果是一个连通图,如果是一个连通图,如果是一个连通图,如果G G G G没有圈,那么没有圈,那么没有圈,那么没有圈,那么G G G G本身就是一个支撑树,如果本身就是一个支撑树,如果本身就是一个支撑树,如果本身就是一个支撑树,如果G G G G有圈,那么任取有圈,那么任取有圈,那么任取有圈,那么任取G G G G的一个的一个的一个的一个圈,并且从这个圈中任意去掉一条边,得到圈,并且从这个圈中任意去掉一条边,得到圈,并且从这个圈中任意去掉一条边,得到圈,并且从这个圈中任意去掉一条边,得到G G G G的一个的
6、一个的一个的一个支撑子图支撑子图支撑子图支撑子图G G G G1 1 1 1,易见易见易见易见G G G G1 1 1 1仍是连通的,如果仍是连通的,如果仍是连通的,如果仍是连通的,如果G G G G1 1 1 1还有圈,就再还有圈,就再还有圈,就再还有圈,就再从某一个圈中去掉一条边,得到从某一个圈中去掉一条边,得到从某一个圈中去掉一条边,得到从某一个圈中去掉一条边,得到G G G G2 2 2 2,G G G G2 2 2 2仍是连通的,仍是连通的,仍是连通的,仍是连通的,这样做下去,直至得到一个不含圈的连通支撑子,这样做下去,直至得到一个不含圈的连通支撑子,这样做下去,直至得到一个不含圈的
7、连通支撑子,这样做下去,直至得到一个不含圈的连通支撑子图图图图G G G Gs s s s为止,为止,为止,为止,G G G Gs s s s就是就是就是就是G G G G的一个支撑树了的一个支撑树了的一个支撑树了的一个支撑树了.按定理按定理按定理按定理5.1.15.1.15.1.15.1.1的证明方法得到一个支撑树的过程的证明方法得到一个支撑树的过程的证明方法得到一个支撑树的过程的证明方法得到一个支撑树的过程成为成为成为成为“破圈法破圈法破圈法破圈法”。从破圈的过程可以看出,一个连通图从破圈的过程可以看出,一个连通图从破圈的过程可以看出,一个连通图从破圈的过程可以看出,一个连通图G G G
8、G一般有许多一般有许多一般有许多一般有许多支撑树支撑树支撑树支撑树.因为取定一个圈后,可以从这个圈上任意去因为取定一个圈后,可以从这个圈上任意去因为取定一个圈后,可以从这个圈上任意去因为取定一个圈后,可以从这个圈上任意去掉一条边掉一条边掉一条边掉一条边.去掉的边不一样,得到的支撑树就不同去掉的边不一样,得到的支撑树就不同去掉的边不一样,得到的支撑树就不同去掉的边不一样,得到的支撑树就不同.现在考虑一个连通图现在考虑一个连通图现在考虑一个连通图现在考虑一个连通图G=(V,E)G=(V,E)G=(V,E)G=(V,E),它的每一条边,它的每一条边,它的每一条边,它的每一条边e e e ej j j
9、 j有有有有一个长度一个长度一个长度一个长度l(el(el(el(ej j j j)0.)0.)0.)0.这时,对于这时,对于这时,对于这时,对于G G G G的任意一个支撑树的任意一个支撑树的任意一个支撑树的任意一个支撑树T T T T,我们把属于我们把属于我们把属于我们把属于T T T T的各条边的长度加起来的和叫做树的各条边的长度加起来的和叫做树的各条边的长度加起来的和叫做树的各条边的长度加起来的和叫做树T T T T的长的长的长的长度,记作度,记作度,记作度,记作l(T).l(T).l(T).l(T).如下图:如下图:如下图:如下图:l(Tl(Tl(Tl(T1 1 1 1)=22,l(
10、T)=22,l(T)=22,l(T)=22,l(T2 2 2 2)=17.)=17.)=17.)=17.v v1 1v v2 2v v3 3v v4 4v v5 55 58 86 62 23 36 65 5v v1 1v v2 2v v3 3v v4 4v v5 55 58 86 62 23 36 65 5v v1 1v v2 2v v3 3v v4 4v v5 55 58 86 62 23 36 65 5a:Ga:Gb:Tb:T1 1c:Tc:T2 2图图图图5.1.35.1.3 现在的问题是如何从现在的问题是如何从现在的问题是如何从现在的问题是如何从G G G G的所有支撑树中,把长度最的
11、所有支撑树中,把长度最的所有支撑树中,把长度最的所有支撑树中,把长度最小的支撑树找出来?小的支撑树找出来?小的支撑树找出来?小的支撑树找出来?.通常,我们把长度最小的支撑树叫做最小树通常,我们把长度最小的支撑树叫做最小树通常,我们把长度最小的支撑树叫做最小树通常,我们把长度最小的支撑树叫做最小树.所所所所以上面的问题实际上就是如何把一个图以上面的问题实际上就是如何把一个图以上面的问题实际上就是如何把一个图以上面的问题实际上就是如何把一个图G G G G的最小树找的最小树找的最小树找的最小树找出来出来出来出来.因此这个问题就叫做最小树问题因此这个问题就叫做最小树问题因此这个问题就叫做最小树问题因
12、此这个问题就叫做最小树问题.最小树问题有很多很广泛的应用最小树问题有很多很广泛的应用最小树问题有很多很广泛的应用最小树问题有很多很广泛的应用.例如,我们把例如,我们把例如,我们把例如,我们把图图图图5.1.3(a)5.1.3(a)5.1.3(a)5.1.3(a)的图的图的图的图G G G G中的五个顶点看成某个镇的中的五个顶点看成某个镇的中的五个顶点看成某个镇的中的五个顶点看成某个镇的5 5 5 5个村,个村,个村,个村,G G G G的边看成是公路,现在要假设电线的边看成是公路,现在要假设电线的边看成是公路,现在要假设电线的边看成是公路,现在要假设电线(电线必须沿着公电线必须沿着公电线必须沿
13、着公电线必须沿着公路假设路假设路假设路假设),使各村之间都能通电话,使各村之间都能通电话,使各村之间都能通电话,使各村之间都能通电话,问应该怎样架线,问应该怎样架线,问应该怎样架线,问应该怎样架线,才能使所用的电线最少?才能使所用的电线最少?才能使所用的电线最少?才能使所用的电线最少?考虑一下,就可以看出,这个问题的关键是决定图考虑一下,就可以看出,这个问题的关键是决定图考虑一下,就可以看出,这个问题的关键是决定图考虑一下,就可以看出,这个问题的关键是决定图上哪些边上架线,哪些边上不架线上哪些边上架线,哪些边上不架线上哪些边上架线,哪些边上不架线上哪些边上架线,哪些边上不架线.设架线的边的集合
14、设架线的边的集合设架线的边的集合设架线的边的集合是是是是E E E E1 1 1 1,那么那么那么那么G G G G1 1 1 1=(V,E=(V,E=(V,E=(V,E1 1 1 1)就是就是就是就是G G G G的一个支撑子图的一个支撑子图的一个支撑子图的一个支撑子图.因为架线后因为架线后因为架线后因为架线后各个村之间都能通话,所以各个村之间都能通话,所以各个村之间都能通话,所以各个村之间都能通话,所以G G G G1 1 1 1必须是连通的必须是连通的必须是连通的必须是连通的.因此要使因此要使因此要使因此要使电线最节约,就是要从电线最节约,就是要从电线最节约,就是要从电线最节约,就是要从
15、G G G G的所有连通的支撑子图中,把的所有连通的支撑子图中,把的所有连通的支撑子图中,把的所有连通的支撑子图中,把总边长最小的找出来,但是不难看出,总边长最小的连总边长最小的找出来,但是不难看出,总边长最小的连总边长最小的找出来,但是不难看出,总边长最小的连总边长最小的找出来,但是不难看出,总边长最小的连通支撑子图一定不会含圈,从而必定是一个支撑树通支撑子图一定不会含圈,从而必定是一个支撑树通支撑子图一定不会含圈,从而必定是一个支撑树通支撑子图一定不会含圈,从而必定是一个支撑树.因因因因此假设电线的问题就归结为最小树问题此假设电线的问题就归结为最小树问题此假设电线的问题就归结为最小树问题此
16、假设电线的问题就归结为最小树问题.类似的问题还有很多,例如修公路把一些城镇连类似的问题还有很多,例如修公路把一些城镇连类似的问题还有很多,例如修公路把一些城镇连类似的问题还有很多,例如修公路把一些城镇连接起来,修渠道使水源和各块地连接起来,等等,都接起来,修渠道使水源和各块地连接起来,等等,都接起来,修渠道使水源和各块地连接起来,等等,都接起来,修渠道使水源和各块地连接起来,等等,都可以归结为最小树问题可以归结为最小树问题可以归结为最小树问题可以归结为最小树问题.同时,最小树问题还是图论同时,最小树问题还是图论同时,最小树问题还是图论同时,最小树问题还是图论中其它很多问题的基础,也就是说,有不
17、少的问题在中其它很多问题的基础,也就是说,有不少的问题在中其它很多问题的基础,也就是说,有不少的问题在中其它很多问题的基础,也就是说,有不少的问题在计算时,往往首先必须求出一个最小树,这也是最小计算时,往往首先必须求出一个最小树,这也是最小计算时,往往首先必须求出一个最小树,这也是最小计算时,往往首先必须求出一个最小树,这也是最小树问题显得特别重要的一个原因树问题显得特别重要的一个原因树问题显得特别重要的一个原因树问题显得特别重要的一个原因.本节我们来看看关于树的一些等价定义本节我们来看看关于树的一些等价定义.定理定理5.2.1设设T=(V,E)是一个树,设是一个树,设T有有m条边,条边,n个
18、个顶点,则顶点,则m=n-1.5.2树的等价定义树的等价定义 在证明这个定理之前,我们先看一些引理在证明这个定理之前,我们先看一些引理.引理引理5.2.1设设G=(V,E)是一个图,它的每一个顶点的是一个图,它的每一个顶点的度数都满足度数都满足deg(vi)2,那么,那么G一定有圈一定有圈.证明:证明的方法是:从任意一证明:证明的方法是:从任意一个顶点开始,来构造个顶点开始,来构造G的一条简单的一条简单了了p,开始时,开始时,p只含一个顶点,以只含一个顶点,以后逐步扩大,然后证明,扩大若干后逐步扩大,然后证明,扩大若干次后,次后,p中一定会出现圈中一定会出现圈,当然,这当然,这就证明了就证明了
19、G中一定有圈中一定有圈.我们结合图我们结合图5.2.1来证明来证明.v v1 1v v3 3v v2 2v v4 4v v5 5e e1 1e e3 3e e4 4e e5 5e e6 6e e2 2图图图图5.2.15.2.1 这个图的每个顶点的度数都大这个图的每个顶点的度数都大这个图的每个顶点的度数都大这个图的每个顶点的度数都大于等于于等于于等于于等于2.2.2.2.先任意取一个顶点,例如先任意取一个顶点,例如先任意取一个顶点,例如先任意取一个顶点,例如取取取取v v v v4 4 4 4,并且令,并且令,并且令,并且令p=vp=vp=vp=v4 4 4 4.因为因为因为因为deg(vde
20、g(vdeg(vdeg(v4 4 4 4)2 2,所以一定有与,所以一定有与,所以一定有与,所以一定有与v v v v4 4 4 4关联关联关联关联的边,任取一条这样的边,例如取的边,任取一条这样的边,例如取的边,任取一条这样的边,例如取的边,任取一条这样的边,例如取e e e e4 4 4 4,把,把,把,把e e e e4 4 4 4及它的另一个端点及它的另一个端点及它的另一个端点及它的另一个端点v v v v2 2 2 2加到加到加到加到p p p p中去,使中去,使中去,使中去,使p p p p扩大成扩大成扩大成扩大成p=vp=vp=vp=v4 4 4 4,e,e,e,e4 4 4 4
21、,v,v,v,v2 2 2 2.然后然后然后然后再取一条与再取一条与再取一条与再取一条与v v v v2 2 2 2关联,而不属于关联,而不属于关联,而不属于关联,而不属于p p p p的边的边的边的边.因为因为因为因为deg(vdeg(vdeg(vdeg(v2 2 2 2)2 2,这样的边是一,这样的边是一,这样的边是一,这样的边是一v v1 1v v3 3v v2 2v v4 4v v5 5e e1 1e e3 3e e4 4e e5 5e e6 6e e2 2图图图图5.2.15.2.1定存在的,例如可以取定存在的,例如可以取定存在的,例如可以取定存在的,例如可以取e e e e1 1
22、1 1,把,把,把,把e e e e1 1 1 1及它的另一个端点及它的另一个端点及它的另一个端点及它的另一个端点v v v v1 1 1 1再加入再加入再加入再加入p p p p,使,使,使,使p p p p扩大成扩大成扩大成扩大成p=vp=vp=vp=v4 4 4 4,e,e,e,e4 4 4 4,v,v,v,v2 2 2 2,e,e,e,e1 1 1 1,v,v,v,v1 1 1 1 ,这样做,这样做,这样做,这样做下去,下去,下去,下去,p p p p中每增加一条边中每增加一条边中每增加一条边中每增加一条边e e e ej j j j 与一个顶点与一个顶点与一个顶点与一个顶点v v v
23、 vi i i i 后,就应后,就应后,就应后,就应该看一看,它属于下面两种情况中的哪一种:该看一看,它属于下面两种情况中的哪一种:该看一看,它属于下面两种情况中的哪一种:该看一看,它属于下面两种情况中的哪一种:情况情况情况情况1 1 1 1:v v v vi i i i 是第一次出现在是第一次出现在是第一次出现在是第一次出现在p p p p中中中中.这时,因为这时,因为这时,因为这时,因为deg(vdeg(vdeg(vdeg(vi i i i)2 2,所以一定还有与,所以一定还有与,所以一定还有与,所以一定还有与v v v vi i i i 关联而不属于关联而不属于关联而不属于关联而不属于p
24、 p p p的边,取的边,取的边,取的边,取一条这样的边,把它及它的不同于一条这样的边,把它及它的不同于一条这样的边,把它及它的不同于一条这样的边,把它及它的不同于v vi i 的另一个端点加入的另一个端点加入的另一个端点加入的另一个端点加入p p p p,p p p p就可以扩大了就可以扩大了就可以扩大了就可以扩大了.情况情况情况情况2 2 2 2:v v v vi i i i 是第二次出现在是第二次出现在是第二次出现在是第二次出现在p p p p中中中中.这时不必再扩大这时不必再扩大这时不必再扩大这时不必再扩大p p p p了了了了.因为因为因为因为p p p p中从上一次出现中从上一次出
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 小树 问题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。