最优生成树及其算法课件.ppt

最小生成树与管道铺设 树：树是不含回路的连通图。 2.树的性质（#） （1）树中任意两点间有且仅有一条路。 （2）树中任意去掉一条边，则树不再连通。 （3）树中任意两点间添上一条边，则构成一个回路。 （4）P个顶点的树有P-1条边。 （5）树中至少存在两个悬挂点。 （6） P个顶点P-1条边的连通图是树图。 最优生成树及其算法 一个连通的赋权图G，可能有很多生成树．设T 为图G的一个生成树，若把T中各边的权数相加所得的和数称之为生成树T的权数．G的所有生成树中，权数最小者称为G的最小生成树． 求最优生成树问题有很广泛的实际应用．例如把n个城市用高压电缆连接起来建立一个电网．如何能设计一个把n个城市联系起来的电网，使所用的电缆长度之和最短，即费用最小（因费用与长度正比），就是一个求最小生成树的问题． 克拉斯克（Kruskal）算法 设G为由n个节点组成的连通赋权图． （1）先把G中所有边按权数大小由小到大重新排列，并取权数最小的一条边作为T的一条边． （2）从剩下的边中按（1）的排列顺序取下一条边，若该边与前已取进T中的边没有形成回路，则把该边取入Ｔ中作为Ｔ的一条边，否则舍去，继续按（１）的排列顺序再取下一条边，…，如此下去直至有n-1条边组成G的最小生成树Ｔ． 练习 假设要建造一个连接若干城镇的铁路络，已知城镇和之间直线路的造价为（且已标注在下图中），试设计一个总造价最小的铁路网络。（说明所使用方法）  克罗斯克尔算法是1956年提出的，俗称“避圈法”． 由克罗斯克尔算法的步骤，顺次取边 ,舍去 ,得到最小生成树为T= 。 定理：由Kruskal算法构造的任何色生成树 都是G的最优生成树。 教材的P100有此算法的流程图。 还有一中求解方法为“破圈法”。 类似可定义最大生成树及其相应的算法． 最优二元树 定义：设T为一棵二元树，共 有t片树叶 分别带权 （w为实数），则称T为代权 二元树， 为二元树T的权，其中 是叶 的层数。 其中权最小的称为最优二元树。 给实数 ，且 ，求做一棵 带权 的最优二元树。 算法步骤如下： 〔1）初始：令S={ }. (2) 从S中取出两个最小的权 画顶点 带权 ：画顶点 带权 。 画 ， 的父亲v，连接 和V, 和v。 令v带权 。 （3〕令s (4)判S是否只含一个元素？若是则停止，否则转（2）。 练习： 1.求权为3，4，7，8，10，12的最优二元树。 2。求权为2，2，3，3的最优二元树。 最小覆盖 最优树 色数 * *