首页 最小支撑树问题与最大匹配问题

最小支撑树问题与最大匹配问题

举报
开通vip

最小支撑树问题与最大匹配问题最小支撑树问题与最大匹配问题 第7章 最小支撑树问题与最大匹配问题 1 树及其基本性质 割集合:在一个无向连通图中割去若干个,以使得图不再连通的边的集合 割边:割集合只有一个边 定理7.1 在连通图中有一个割集合和一个圈,则它们的交集合的基数是零或者是偶数 树:无圈的连通图 定理7.2 (1)一棵树中任意两个顶点之间均有唯一的路相连 (2)任意删去一个边就不再连通 定理7.3 树T(V,E)的边数等于顶点数减1 定理7.4 顶点数大于1的树至少有两个度数为1的顶点 2 最小支撑树问题 支撑树:...

最小支撑树问题与最大匹配问题
最小支撑树问题与最大匹配问题 第7章 最小支撑树问题与最大匹配问题 1 树及其基本性质 割集合:在一个无向连通图中割去若干个,以使得图不再连通的边的集合 割边:割集合只有一个边 定理7.1 在连通图中有一个割集合和一个圈,则它们的交集合的基数是零或者是偶数 树:无圈的连通图 定理7.2 (1)一棵树中任意两个顶点之间均有唯一的路相连 (2)任意删去一个边就不再连通 定理7.3 树T(V,E)的边数等于顶点数减1 定理7.4 顶点数大于1的树至少有两个度数为1的顶点 2 最小支撑树问题 支撑树:边为N的图中选出边数为N-1的导出子图是树。叫图的支撑树 最小支撑树问题:在每个赋权连通简单图中求解值为最小的支撑树。 定理7.5 在赋权连通图G=G(V,E)中 (1)如果e 是边集合中的一条最小边,则它一定属于某一个最小支撑树 (2)在赋权连通图G中,f是某个圈中的的最长边,则有一个最小支撑树不含它 *T 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 :(1)设图G有一个最小支撑树,它不含有那条最小边,我们把 *,T它添加到中,此时图中含有唯一一个圈C,C中每条边的权都大于e的 *T权,将权数大于它的边换掉,也是支撑树,权数就比小,矛盾产生。 *Tf,uv(2)设图G有一个最小支撑树,它含有圈C中的一条最长边, *TT,T(V.E)作,它是由两个连通分支和组成,,,\fT,T(V.E)222211111连接这两个分之的边的集合记作U,U是图G的一个割集合,f也在其中,因为割集合与图的交集的基数或者是0或者是偶数,因此至少还有一条割 ,,ffw(f),w(f)边,而是圈中的最长边,所以,如果是小于,支撑树 **,T,,的值比更小,矛盾 T\f:(f) 3 求解最小支撑树的四个算法 一、破圈算法
本文档为【最小支撑树问题与最大匹配问题】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_321635
暂无简介~
格式:doc
大小:11KB
软件:Word
页数:2
分类:法学
上传时间:2017-12-02
浏览量:40