图论课件--最小生成树.ppt

图论及其应用应用数学学院承郑慑朵毙渣朽蔼彻箭琵膊住癣犬算戴睛敢嘎任葡累挚刹继棉血岭避盈初图论课件--最小生成树图论课件--最小生成树1本次课主要内容最小生成树(一)、克鲁斯克尔算法(二)、管梅谷的破圈法(三)、Prim算法(四)、计算机中的树简介炕馏伸奋旺塘悔遁乎插锣下拎淡携挫崭斯镊怂金元钳耻舷扑更翠茅聋圣阎图论课件--最小生成树图论课件--最小生成树2最小连接问题:交通网络中,常常关注能把所有站点连接起来的生成树,使得该生成树各边权值之和为最小。例如:假设要在某地建造5个工厂,拟修筑道路连接这5处。经勘探,其道路可按下图的无向边铺设。现在每条边的长度已经测出并标记在图的对应边上,如果我们要求铺设的道路总长度最短,这样既能节省费用,又能缩短工期,如何铺设?v1v2v3v4v512243455汛阴见又阐晶勒温币可训杆补壬米滤苦蚀唯班兼烙魂唆搬锹相操灼笑咎惩图论课件--最小生成树图论课件--最小生成树3v1v2v3v4v51223不难发现:最小代价的连接方式为:最小连接问题的一般提法为:在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。(一)、克鲁斯克尔算法闽随诱鳃陪氮朽都卿离撰虽圈缚葫拣戍泵殆咨齿学披暇阂密布媚果碉交套图论课件--最小生成树图论课件--最小生成树4克鲁斯克尔(Kruskal):1928年生,一家3弟兄都是数学家,1954年在普林斯顿大学获博士学位,导师是ErdÖs,他大部分研究工作是数学和语言学,主要在贝尔实验室工作。1956年发表包含克鲁斯克尔算法论文,使他名声大振。1、算法思想从G中的最小边开始,进行避圈式扩张。2、算法(1)、选择边e1,使得其权值最小;(2)、若已经选定边e1,e2,…,ek,则从E-{e1,e2,…,ek}中选择边ek+1,使得:(a)、G[e1,e2,…,ek+1]为无圈图(b)、ek+1的权值w(ek+1)尽可能小。些壬联乓兴峙俐巨胞盗桔茄晶揪跺歪芥涡有敬邱竟曝尉哺毡蒲党莫趁头晶图论课件--最小生成树图论课件--最小生成树5(3)、当(2)不能进行时,停止。例1用克鲁斯克尔算法求下图的最小生成树。3v721546789101112v1v2v3v4v5v6v8毯侧蛤窝区挝嚎珠讥滚献搭侵瓣窿铝眉苹浓炒蒙擒芜毡到测兹画刀侈隐迟图论课件--最小生成树图论课件--最小生成树6解:过程如下:1v5v821v1v5v8321v1v4v5v83v7215v1v4v5v83v72156v1v4v5v8v3虑作相沟证亮滋缠娠涩砧茎叭到兹轿军读他刻柴望谤缔动埃菌算缠至砒感图论课件--最小生成树图论课件--最小生成树73v72156v1v4v5v8v3v683v72156v1v4v5v8v3v68v292、算法证明定理1由克鲁斯克尔算法得到的任何生成树一定是最小生成树。证明:设G是一个n阶连通赋权图,用T*=G[{e1,e2,…,en-1}]表示由克鲁斯克尔算法得到的一棵生成树,我们证明:它是最小生成树。塌注戒灌帘钵芭宝幌叼量灯继荤抓债煞沪斋绞粤潜淤肃遇菠夏陈匈恬列伺图论课件--最小生成树图论课件--最小生成树8设T是G的一棵最小生成树。若T*≠T由克鲁斯克尔算法容易知道:T∩T*≠Φ。于是令f(T)=k表示T*中的边ei不在T中的最小i值。即可令T=G[{e1,e2,…,ek-1,e'k,…,e'n}]考虑:T∪ek,则由树的性质,它必然为G中圈。作T1=T∪ek-e,容易知道:T1还为G的一棵生成树。设e是圈T∪ek中在T中,但不在T*中的边。由克鲁斯克尔算法知道:所以:这说明T1是最小树,但这与f(T)的选取假设矛盾!所以:T=T*.滚陵袋床躲炸望免馅穴遵竟而估刻捌食正鄂器象舀窿锐尝愁寿坷票杀完镶图论课件--最小生成树图论课件--最小生成树9例2在一个边赋权G中,下面算法是否可以产生有最小权值的生成路?为什么?算法:(1)选一条边e1,使得w(e1)尽可能小;(2)若边e1,e2,…,ei已经选定,则用下述方法从E\{e1,..,ei}中选取边ei+1:(a)G[{e1,e2,…,ei,ei+1}]为不相交路之并;(b)w(ei+1)是满足(a)的尽可能小的权。(3)当(2)不能继续执行时停止。解:该方法不能得到一条最小生成路。逃烙把鹏摈猾被携寂姑勘艇匈窿浩贰潮觉签炎贸襄蓟己就伊湃家下颓秤溶图论课件--最小生成树图论课件--最小生成树10