运筹学 北京邮电大学
§7.2 最小支撑树问题
Minimum Spanning Tree Problem
Ch7 Graph and Network
2013-9-13 Page 2 of 5
求最小树的方法：破圈法和避圈法 破圈法：任取一圈，去掉圈中最长边，直到无圈。 避圈法：即选边法；加边的原则：从最短边开始选择，每次 都从未选边中取最短者，但已选边中不能形成圈，直习
作业：P283 10.4 10.5
最短路问题
运筹学 北京邮电大学
Exit
§7.2 最小支撑树问题
Minimum Spanning Tree Problem
Ch7 Graph and Network
2013-9-13 Page 1 of 5
定义：设G＝[V,E]是一个无向图，对每一条边ei∈E有一个长 度C(ei) ≥0,G的任意支撑树T各条边的长度之和称为树T的长度， 记为C（T）。长度最小的支撑树称为最小树。 求最小树是在一个无向连通图G中求一棵最小支撑树。 求最小树问题的应用： • 电信网络（计算机网络、电话专用线网络、有线电视网络等等） 的设计 • 低负荷运输网络的设计，使得网络中提供链接的部分（如铁路、 公路等 等）的总成本最小 • 高压输电线路网络的设计 电器设备线路网络（如数字计算机系统）的设计，使得线路总长 度最短 • 连接多个场所的管道网络设计