最小宝就影苎参考书:1、傅鹂龚劬刘琼荪何中市《数学实验》《数据结构教程C语言版》中国电力出版社主讲:龚劬制作:龚劬上一页下一页主页主要容□一个例子基本概念与结论Kruskal1算法Prim算法最小生成树问题的0-1规划模型上一页下一页主页树图直观形象的表示工具类似于自赵根然界中的赵亮赵丽树赵雷赵雨赵虹赵云赵霞赵松赵梅形象地表示家族上一页下一页主页树图直观形象的表示工具树:了的连通图树中任意两京间有唯一路径。0树的边数恰好为顶点数减1。上一页下一页主页引例:计算机网络的线路设计城可电信局有许多业豸如收费,营业,112,114等,希望在全市范围实现计机联服分,共享各种资源。主要天心的问题是:用数据通线把一组站京联结起米,听不允许通讯线在非站点处相交,如何连接可使通讯线的花费最小?上一页下一页主页引例:计算机网络的线路设计量经济的不应该任何封的回路上一页下一页主页引例:计算机网络的线路设计生成树或支撑树(spanningtree):G的子图且是树,其顶点票等手的顶点集;★6如何简便地得到10左图的生成树?③它应有几条边?上一页下一页主页引例:计算机网络的线路设计确定应在哪些站点之间铺设通讯线路,是否可看作是在相应的力权图中构造最小费用的生成树的问题?上一页下一页主页引例:计算机网络的线路设计最小生成树最大生成树★想1)一个完金幽民有参少不周的生成树?2)如何求其最小些成?上一页下一页主页引例:计算机网络的线路设计入10个项京的完全图,其不同的生成树就有般地,个顶京的完全图,其不同的生成树个数为n230个顶点的完全图就有0个生成树,求最小生成树时用罗举法是元效的。
最小生成树-数学建模 来自淘豆网m.daumloan.com转载请标明出处.
