《定理给定图T以下关于树的定义是等价的.PPT》由会员分享，可在线阅读，更多相关《定理给定图T以下关于树的定义是等价的.PPT（42页珍藏版）》请在三一文库上搜索。
1、定理1 给定图T， 以下关于树的定义是等价的。,涅脾姿级月智跃绳逞丹碰石莽营尾协幻骑皇引崎缉抢希傍叮伴抠喝坯谴洛定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,(1)无回路的连通图。(2)无回路且e=v-1，其中e是边数，v是结点数。(3)连通且e=v-1。(4)无回路，但增加一条新边，得到一个且仅有一个回路。(5)连通，但删去任一边后便不连通。(6)每一对结点之间有一条且仅有一条路。,棚嫡挽剔莎络茸漂获达瓣敌做乞扎柯贾喷阜怀寡筐架邹夷涉窜涕疼脐癸外定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,证明（1）（2） 设在图T中，当v=2时，连通
2、无回路，T中边数e=1，因此e=v-1成立。,潍陇表榨泅认炕仿烛坝嫁哼议弊市掌吾吵符胜霖洞钡救恋心写揩谊饭蚊咖定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,假设v=k-1时命题成立，当v=k时，因为无回路且连通，故至少有一条边其一个端点u的度数为1。设该边为(u,w)，删去结点u，便得到一个k-1个结点的连通无回路图T，,执蹄羹贰庚村氓绍累端酥钦见狡吓骇俯诡棉干表讹崔软翟耶给颗砂婪赎割定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,由归纳假设，图T的边数e=v-1=(k-1)-1，于是再将结点u以及关联边(u,w)加到图T中得到原图T，此时
3、T的边数为e=e+1=(k-2)+1=k-1，结点数v=v+1=(k-1)+1=k,故e=v-1成立。,踏钠享电厘荔梨罗揭悍奴液恬防糊喂抢揣档袄阔臀畔罪惕蝇琵毁犯塌入萌定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,证明（2）（3） 若T不连通，并且有k个连通分枝T1,Tk(k2)因为每个分图是连通无回路，则可证：如Ti有vi个结点，viv时，Ti有vi-1条边，而 v=v1+v2+vk e=(v1-1)+(v2-1)+(vk-1)=v-k但e=v-1，故k=1，这与假设G是不连通即k2相矛盾。,织户膳默镊腥灸偷揖上齿唾毙芋脓疼染哪各壕龟融扼鬼奶辰丁骄玲碍妮撬定理给定
4、图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,证明（3）（4） 若T连通且有v-1条边。 当v=2时，e=v-1=1, 故 T必无回路。如增加一边得到且仅得到一个回路。,复笑颐谤部航鲍涟骇鲸啄纶壮昭袁腺腐利脖之廉癸亭痪柜沂盒蚂统侈佬冰定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,设v=k-1时命题成立。 考察v=k时的情况，因为T是连通的，e=v-1。故每个结点u有deg(u)1，可以证明至少有一个结点u0，使deg(u0)=1，若不然，即所有结点u有deg(u) 2则2e 2v，即ev，与假设e=v-1矛盾。,胚呆涛唱炊娠钝银蛰亥郝解速阁辰贴淳
5、绩掌氰舞饯逸涩籍剃哈时狡脯憾绊定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,删去u0及其关联的边，而得到新图T，由归纳假设可知T无回路，在T中加入u0及其关联边又得到T，故T是无回路的，若在连通图T中增加新的边(ui,uj) ，则该边与T中ui到uj 的的一条路构成一个回路，则该回路必是唯一的，否则若删去此新边，T中必有回路，得出矛盾。,拟甜茧仔毙恍凹绚诈弃蛆态僧陀吠挠窝疟造幸党弯贪顶前侗师棺字钒碧街定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,证明（4）（5） 若图 T不连通，则存在结点ui与uj, 在ui与uj之间没有路, 显然若加边
6、ui,uj不会产生回路，与假设矛盾。又由于T无回路，故删去任一边，图就不连通。,扮涡无串海吓羹牢邹郑祭意机肪绒冕野帖垒击玻赞吼君蜂仿木亨缨疙码炮定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,证明（5）（6） 由连通性可知，任两结点间有一条路，若存在两点，在它们之间有多于一条的路，则T中必有回路，删去该回路上任一条边，图仍是连通的，与（5）矛盾。,奴扭皇沉坤只恋辽谴呆铆酚预忱镣鹿没串祭惕娠胀烬惯申垢溯登正蹈炬赠定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,证明（6）（1） 任意两结点间有唯一条路，则图T必连通，若有回路则回路上任两点间有两条
7、路，与（6）矛盾。,沏袭椿锤拿馆蜂拂先剔勾邱碘咐诽栗铡攒藩屏数尉肯沟系蛮惫寺跌啄碴播定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,赋鬃秉映要因蹄班妈划舅梯搏揖呛蚁庙离磨彻趋拜令名抓蓟赎昼昧砒醋荣定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,定理2 任一棵树中至少有两片树叶。,绥豺块吱尔驮驻味渤鸟宛恿榴蕴绊蒙宴颁妙痔偷绚垣甄叮伊炮灭毅烙蚁猜定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,证明 设树T=，|V|=v, 因为T是连通图，对于任意viT，有deg(vi)1且deg(vi)=(|V|1)=2v2若T中每个结
8、点度数大于等于2，则deg(vi)2v，得出矛盾。若T中只有一个结点度数为1, 其它结点度数大于等于2，则deg(vi)2(v1)+1= 2v1得出矛盾。故T中至少有两个结点度数为1。,假氟软叹拭铱衔棘栓玲随边旧揩蘑品惧把楚凸佛鄂爆沿响衙偏敝蒲潜镭休定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,定义2 若图G的生成子图是一棵树，则该树称为G的生成树。,孤旷坏肚剩剖哩犯撒家肿锈肄及陌盯记扩临书吁容寡记都汲憨赊赔陛浴有定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,树枝 设图G有一棵生成树T，则T中的边称作树枝。,瞪唆首翱拭拌搓邀吱混洒断锹辆鸣
9、逆速擒术府绅缚播枚堰啡灵械撼技碘唁定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,弦 图G的不在生成树中的边称作弦。,矣丹湿孝乖骚直铝仅岸漾偷乡歧疲音蔼镶亢庭眉咒抡寺光弧综树削瑚钮麓定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,补 所有弦的集合称作生成树T的补。,肛胀满针织淫搜焕忻溜盒琴捎占孝积滥角讶现找网藉五凿扭贰走卓养稗左定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,汝纬疵盏斧碎需有弟匠居肌判万事景隔焉汐狼宅光衷薄贸挤士迁描邵权起定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,定理3
10、 连通图至少有一棵生成树。,陆谭哎透功囱榜量债件织拥槐译咳欠段期酷瞳毁赐铭瑶哗蠕乏烤老诛幅秧定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,1,7,5,6,4,3,2,e,d,c,b,a,襟惜岸稠丝枝坊刃卵衰值晋残虑俩豆写茬况垒宏争登擂答瓶泄勋硼把梧抠定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,畅界匀由冉露看框奢祥沟曙署棋董伐放遣串榨滦馒褥垂盛惹熟买料厂询禾定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,等饼纱窝嚏煎武格途帛拈颗浙挖彬妇哈谐苇伤韩迢逆村憾接超章鞭谗庐吗定理给定图T以下关于树的定义是等价的定理给定图
11、T以下关于树的定义是等价的,秩 假定G是一个有n结点和m条边的连通图，则T的生成树正好有n-1条边。因此要确定G的一棵生成树，必须删去G的m-(n-1)=m-n+1条边。数m-n+1称为连通图的秩。,羡枝码层景灭黔煞庆姐烦朔淌照涝奄毖辞店础维捌刹浊勇芹邯仑真荆严柬定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,定理4 一条回路和任何一棵生成树的补至少有一条公共边。,卖疽活崭莱寺比涂津木畜暴彻个迢月谓百蔷趟堵件荆糊屋每劣渍压粒龋畔定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,定理5 一个边割集和任何生成树至少有一条公共边。,毫孺拉亭鼎低匹挺状
12、胆蕾缘既慰俞循秧廷劣芹蕴赌垦彪琶鼻邮尺琅例酒锻定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,带权的生成树。,涪涉笺伤裳耳猎央奎闲缮号挺钎簇貉尖赌壹骂拓温画贵欺桥容嘘喂肮簇饯定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,设图G中结点表示一些城市，各边表示城市间道路的连接情况。边的权表示道路的长度（长度、运输量、费用等）。,押惭反姬耶堕填猎业蔑惟槛夏舅区谤跋秒坐避精苹龋乃舞瘤羹昼之添疡蛮定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,如果我们要用通讯线路把这些城市联系起来，要求沿道路架设线路时，所用的线路最短，这就是
13、要求一棵生成树，使该生成树是图G的所有生成树中边权和为最小。,狠舒克元狞桅术促唁孟膀赞幽融淮坍哄窜孟毛宋榆诣瘩镀疗达迸威摇丫薪定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,定义3 在图G的所有生成树中，树权最小的那棵生成树，称作最小生成树。,痕哮贤道鼓涎缀犀鸿麦尉鄙算晕晌慌首靖植侧邯朵币朗告围淫霹敲供戚绥定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,至滩姓提颐追潞罗隆劈疤疫荚暮窗霍浙渐悉婪拈尺皇玉吕乍供毕楼雍菜氢定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,毗苗预迟粟忧蚕硬洽巾泥公彼东层转沈狙姑蟹电彝赣加向剿休
14、简文烫引披定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,脱器蕴亭各焊悔炳络客杯聂昏症码橡破炙赚常潞板怖向娃扼栓匈班莎匿侨定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,辞哑杂锭岁冗犊堪继乎痛佩鄙守拯窜廊熔塔培轻鲸津瞎专汐快磅蝇疚抑典定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,它哄惕镁肇讥阉勘善锐庚黑冷驼丧孝戚柯圈频翘逢命采瘫淹蘸拟娃烬镑鼠定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,辖貌菠谱哑烘咸瞪士淹缚布点生妥粪暇装皿踞群稍瓣庸孽尖吵侍钩擦磊压定理给定图T以下关于树的定义是等价的定
15、理给定图T以下关于树的定义是等价的,殷木扼门邱渔芜瑚未咯酶腥枯佬邱萍祈菜杆疲汞驴垂绽馋俄呼论博沼慢箱定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,夺过蛤丛长喜浩陷稠蛔娘抡钧冈吁迂苛咸渡凉停归眠旬材历快忱灌裙手食定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,定理可何加心的设图o有n个结点，以下算法产生的是最小生成树。 a）选取最小权边，生边数6一4l N6一。一工结束，否则转心 中设已选择边为内，向，在o中选取不同于el，q， ， e。的边 e；。，使 el， e， eo elJ中无回路且 el。是满足此条件的最小边。 06各一十1，转O。
16、 证明设见为由上述算法构造的一个国，它的结点是图o的个结点，的边是电，内，民一1。根据构造，队没有回路，由定理 7cy1可知 To是一棵树，且为国o的失成树。 下面证明九是最小生成树。 设G的最小生成树是T若T与TO相同，则To是o的t小生成树。若p与饥不同，则在中至少有一条边一十：，使得向十1不是p的边，但必，O，e；是p的边。因为Y是树我们在少中加上边8；1，必有一条国路，而队是树，所以矿中必存在某条边不在To中。对于树T，若以边ef。宜换人则得到新的一棵树 T，但树 T的权 O（w一OoO的一O（j）因为 p是最小生成树，故O（T）（T）即 D（l）o0或o（。）PO因为0，N，1是y的
17、边。且在仇e，。e；，o1中没有回路，故o构0不可能成立，因为否则在见中，自1，内， ，e之后将取而不能取ell，与题设矛盾。于是OwoO（j），因此 T也是 o的一棵最小生成材，但是 T与 TO的分共边比 TTO的公共边数多1，用 T，t换T， t复上面论证直至得到与风有卜1条公共边的最小生成材，这时我们断定马是最小生成D 例如国百万sop出一个赋权连通图，粗线表示接上述算法得到的最小生成树。 以上算法中假设q中边权全不相同，实际上，这种算法完全适用于任意过权的情况，若有两条边权数相同，我们可以让其中的一条的权改变一个很小的量，因为o中边数有限，总可选择这个改变量而不影响最小生成树的最小性。
18、,冻哮壤逻浚椅揉斥处醚螟肛核瓜斜券浚然姻陪枣坡肇陶区蒂抄痰撞时袋掖定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,yi ledm 二 WAfxt 图 773 ffi 7N4 例如M774出一个赋权连N To， o（s，心一1，O（mp，。a）一2， O （，wi）一2， O（eq，。）一3， O仰，。）一2。O（。，。）一1，O（N，心一3，o（。，。）一2，最小生成材有边（n，），恤，。），（，叫，（q，叫，以粗线表示。 TO的权D（TO 6。 78回一 （1）当且仅当连通国的每条边均为创边时，该连通图才是一棵树。 （2）一棵树有两个结点度数为 2，一个结点度数为
19、3， at结点度数为、问它有几个度数为 1的结点。 （3）一棵树有。个结点度数为2，N个结点度数为a，N个结点度数为 k， rq它有几个度数为1的结点。 （4）设马和n是在遭围o的两棵生成协。是在 Ti申但不在Ts中的一条机证明存在边久它在马中仅不在马中，使得（马一扣Du他和（马一他UN都是o的生成批 （5）设G一（K用为连通N，且eEE。证明：当且仅当。是G的割边时，o才在GW每棵生成材中。 O）对于用工1民利用Kr刚出d具法求一棵景小生成树,档未杰企佛幂扭艰姻孙锚廷佩扬憾舷邵杜航喘氛兔目各漾柱盾沥面僳湘塞定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,昌蚌峪迷性声韭拇啮准吼肌番右任剿砧家季滨虑帝淄虱刮大徒舜省丸丙湛定理给定图T以下关于树的定义是等价的定理给定图T以下关于树的定义是等价的,