主主页页上一页上一页下一页下一页最小生成树算法最小生成树算法参考书:参考书:《《数学实验数学实验》》《《语言版语言版》》中国电力出版社中国电力出版社主讲:龚主讲:龚劬劬制作:龚制作:龚劬劬主主页页上一页上一页下一页下一页PrimPrim算法算法KruskalKruskal算法算法主要内容主要内容最小生成树问题的最小生成树问题的0-10-1规划模型规划模型一个例子一个例子基本概念与结论基本概念与结论主主页页上一页上一页下一页下一页赵根赵明赵亮赵丽赵雷赵虹赵雨赵霞赵云赵梅赵松树图树图————直观形象的表示工具直观形象的表示工具类似于自然界中的树形象地表示家族主主页页上一页上一页下一页下一页树:树:没有圈的连通图没有圈的连通图??树中任意两点间有唯一路径。树中任意两点间有唯一路径。??树的边数恰好为顶点数减树的边数恰好为顶点数减11。。树图树图————直观形象的表示工具直观形象的表示工具主主页页上一页上一页下一页下一页城市电信局有许多业务如收费,城市电信局有许多业务如收费,营业,营业,112112,,114114等,希望在全市范围等,希望在全市范围实现计算机联网服务,共享各种资源。实现计算机联网服务,共享各种资源。一个主要关心的问题是:用数据通讯一个主要关心的问题是:用数据通讯线把一组站点联结起来,而不允许通线把一组站点联结起来,而不允许通讯线在非站点处相交,如何连接可使讯线在非站点处相交,如何连接可使通讯线的花费最小?通讯线的花费最小?引例:计算机网络的引例:计算机网络的线路设计线路设计主主页页上一页上一页下一页下一页12345869157103引例:计算机网络的线路设计引例:计算机网络的线路设计最经济的网络不应该有任何封闭的最经济的网络不应该有任何封闭的回路。回路。主主页页上一页上一页下一页下一页引例:计算机网络的线路设计引例:计算机网络的线路设计生成树或支撑树((spanning treespanning tree))::GG的子的子图且是树,其顶点集等于图且是树,其顶点集等于GG的顶点集;的顶点集;12345869157103如何简便地得到左图的生成树?它应有几条边??主主页页上一页上一页下一页下一页确定应在哪些站点之间铺设通讯线路,是否可看作是在相应的加权图中构造最小费用的生成树的问题?引例:计算机网络的线路设计引例:计算机网络的线路设计主主页页上一页上一页下一页下一页最小生成树最大生成树引例:计算机网络的线路设计引例:计算机网络的线路设计?1) 1) 一个完全图一个完全图KKnn有多少不同有多少不同的生成树?的生成树?2) 2) 如何求其最小生成树如何求其最小生成树??主主页页上一页上一页下一页下一页1010个顶点的完全图,其不同的生成树就有个顶点的完全图,其不同的生成树就有一亿棵。一亿棵。一般地,一般地,nn个顶点的完全图,其不同的生成个顶点的完全图,其不同的生成树个数为树个数为nnn-2n-2。。3030个顶点的完全图就有个顶点的完全图就有30302828个生成树,求个生成树,求最小生成树时用穷举法是无效的。最小生成树时用穷举法是无效的。引例:计算机网络的线路设计引例:计算机网络的线路设计返返回回
最小生成树 来自淘豆网m.daumloan.com转载请标明出处.
