下载文档原格式
运筹学最小生成树破圈法例题引言运筹学是一门研究如何优化决策的学科，它可以帮助我们在面对各种约束条件和目标函数的情况下，找到一个最优解。
其中一个重要的问题是最小生成树（Minimum Spanning Tree，MST）问题，它用于解决图论中的连通性问题。
在本文中，我们将重点讨论用破圈法（Cycle Breaking Algorithm）求解最小生成树问题的例题。
什么是最小生成树问题？最小生成树问题是在一个加权连通图中，找到一个边的子集，使得这个子集形成一棵树，并且这棵树上所有边的权重之和最小。
最小生成树问题常被用于网络设计、电力传输、通信网络等领域。
最小生成树破圈法为了解决最小生成树问题，我们介绍一种常用的算法——破圈法。
该算法的基本思想是不断将新的边加入到当前的生成树中，同时保证生成树中不会形成闭合的回路。
下面通过一个例题来详细介绍破圈法的具体步骤。
例题描述假设我们有一个无向连通图，共有6个顶点，边的权重如下表所示：边权重AB 4AD 6AC 5BC 1BD 2BE 3CE 7DE 8DF 9边权重EF 10我们的目标是找到这个图的最小生成树。
破圈法求解步骤以下是破圈法求解最小生成树问题的具体步骤：1.初始化：选择一个起始顶点作为生成树的根节点，将该顶点加入生成树的顶点集合V’中，将该顶点的所有相邻边加入到候选边集合E’中，并按权重从小到大排序。
2.迭代：从候选边集合E’中选择一条权重最小且不会形成回路的边e，将该边的两个顶点加入到顶点集合V’中，并将这条边加入生成树的边集合中。
同时更新候选边集合，将与新加入顶点有关的边加入候选边集合，并按权重排序。
3.终止条件：重复步骤2，直到生成树包含了全部的n-1个顶点，其中n为原图的顶点个数。
破圈法求解最小生成树例题解析根据以上步骤，我们逐步求解例题中给出的图的最小生成树。
Step 1: 初始化我们选择顶点A作为起始顶点，并将其加入生成树的顶点集合V’中。
最小树与最小树形图（数学建模）讲解一、最小树的定义及性质1. 定义：最小树，又称最小树，是指在给定的带权无向图中，包含图中所有顶点的一个树形结构，且树中所有边的权值之和最小。
2. 性质：（1）最小树中不存在回路；（2）对于最小树中的任意两个顶点，它们之间有且仅有一条路径；（3）最小树中边的数量等于顶点数量减一；（4）在最小树中添加任意一条边，都会形成一条回路；（5）最小树不唯一，但权值之和相同。
二、求解最小树的方法1. Prim算法Prim算法是一种贪心算法，其基本思想是从图中的一个顶点开始，逐步添加边和顶点，直到形成最小树。
具体步骤如下：（1）初始化：选择一个顶点作为最小树的起点，将其加入最小树集合；（2）迭代：在最小树集合和非最小树集合之间，寻找一条权值最小的边，将其加入最小树集合；（3）重复步骤2，直到所有顶点都加入最小树集合。
2. Kruskal算法Kruskal算法同样是一种贪心算法，其基本思想是将图中的所有边按权值从小到大排序，然后依次选择权值最小的边，判断是否形成回路，若不形成回路，则将其加入最小树集合。
具体步骤如下：（1）初始化：将所有顶点视为独立的树；（2）按权值从小到大排序所有边；（3）迭代：选择权值最小的边，判断其是否形成回路，若不形成回路，则将其加入最小树集合；（4）重复步骤3，直到所有顶点都在同一棵树中。
三、最小树形图的定义及求解方法1. 定义：最小树形图，又称最优树形图，是指在给定的有向图中，找到一个包含所有顶点的树形结构，使得树中所有边的权值之和最小。
2. 求解方法：朱刘算法（Edmonds' Algorithm）朱刘算法是一种用于求解最小树形图的算法，其基本思想是通过寻找图中的最小权值环，进行收缩和扩展操作，最终得到最小树形图。
具体步骤如下：（1）寻找最小权值环；（2）对最小权值环进行收缩操作，将环中的顶点合并为一个新顶点；（3）在新图中寻找最小树形图；（4）将新图中的最小树形图扩展回原图，得到原图的最小树形图。
6.3 图与网络规划问题图与网络规划问题归纳起来主要有最小树问题、最短路问题、最大流问题、最小费用最大流问题、指派问题、货郎担问题(TSP)、选址问题等，本节将基于图与网络给出描述这些问题的最优化模型，介绍问题求解的常用算法，给出实现算法的程序和应用它们解决实际问题的实例. 6.3.1 最小树问题最小树问题就是如何求一个网络),,(W E V G 的最小树. 在交通网、电力网、管道网等的设计中常涉及最小树问题, 如“已知n 个城市间的交通线建造费用, 如何建造一个联结这n 个城市的交通网, 使总的建造费用最小.”就是一个最小树问题.[Ⅰ] 最小树问题模型设连通网络)3)(,,( V n W E V G 的邻接矩阵为n n ij a A )(, 权矩阵为n n ij w W )(, 求(0, 1)矩阵n n ij t T )(, 使得11111min (),..0,0(,1,2,,),1,.n nij ij i jij ij n n ij i j i n i i W T w t s t t a i j n t n T当时不含非零元 (6.4) 邻接矩阵为n n ij t T )(的图T 即为网络G 的最小树, )(T W 为最小树T 的权.[Ⅱ] 求最小树的算法 i) Kruskal 算法[4]Kruskal 算法是Joseph Kruskal 于1956年首次提出的求最小树算法, 属贪心算法, 依据是定理6.7, 其基本思路是从连通网络),,(W E V G (记E m V n ,)的m 条边中选取1 n 条权尽量小的边, 并使所选边的导出子图没有回路, 从而构成G 的最小树T . 算法步骤可描述如下:Step1: 把网络),,(W E V G (记E m V n ,)的m 条边从小到大排序，即.,,,21m a a a置1,0, j i S .Step2: 若1 n i S 则停止, 这时T S G ][即为所求；否则转到Step3. Step3: 若][j a S G 不构成回路, 则置j i a e 1,}{1 i e S S , 1 i i ,1 j j , 转到Step2；否则置1 j j , 转到Step2.Step3中要判断][j a S G 是否构成回路, 需确定j a 的两个端点是否在][S G 的不同连通分支中, 这可用标号法实现, 即每一步都给G 的顶点标号, 当且仅当两个点有相同的标号时, 它们才属于][S G 中的同一连通分支中.标号方法: 开始时, 将点l v 赋以标号)1(n l l , 以后取边j a , 若j a 的两个端点标号不同, 则置j i a e 1, 并用两个标号的较小者对较大标号的端点及与之有相同标号的端点标号；否则就抛弃j a , 再取边1 j a 检查.例6.6 在图6.22的网络中求一个最小树, 首先对每个点标号, 如图6.23(a), 然后再取边和修改点的标号, 直至取出4条边为止, 如图6.23(b)～(d)的实线边.按Kruskal 算法, 用Matlab 语言编程求解模型(6.4)的程序见本书配套光盘中Textbook_programs 目录的子目录Chapter06下的M 文件：KRmintree.m .Kruskal 算法属避圈法之一, 计算量为)log (22n n O , 算法的效率不太高, 特42 3 44 221v 3v 2 v 4 v 1v 5图6.22别是当问题规模比较大时, 效率更低.(a) (b)(c) (d)图6.23ii) Prim 算法Prim 算法也称Dijkstra 算法[5], 其基本思路是从G 的1 n 个独立割集中的每一个都选取一条权最小的边, 所选取边的导出子图即是所求的最小树. 算法步骤可描述如下:Step1: 置),,2,1(1n j w u j j , S , }{1v P , },,{2n v v T . Step2: 取ik j Tj k w u u }{min , 置}{ik e S S (ik e 为权值ik w 对应的边),}{k v P P ,}{\k v T T .Step3: 若 T , 则停止；否则置},{min kj j Tv j w u u j , 返回Step2.按Prim 算法, 用标号方式求图6.22的网络的最小树过程如图6.24(a)～(d). 首先给第1个点1v 以0标号, 点T v j 以j u 标号, 如图6.24(a). 点2v 的标号最小, 取边],[21v v 加入S , 检查修改与2v 相邻点的标号, 如图6.24(b). 如此直到42 3 44 221(v 3, 1) (v 2, 1) (v 4, 4) (v 1, 1)(v 5, 4) 42 3 44 221(v 3, 1)(v 2, 1)(v 4, 1) (v 1, 1)(v 5, 1)42 3 44 2 21(v 3, 3) (v 2, 1)(v 4, 4) (v 1, 1)(v 5, 5)42 3 44 221(v 3, 3) (v 2, 2) (v 4, 4) (v 1, 1)(v 5, 5)图6.24(d), 剩最后一个点4v , 它标号为2, 为边],[45v v 的权值, 取它加入S 后,][S G 即为所小的最小树.(a) (b)(c) (d)图6.24(v 3, 2) (v 2, 1)(v 4, 4) (v 1, 0)(v 5, 3)42 3 44 2 21(v 3, 2) (v 2, 1) (v 4, ∞) (v 1, 0)(v 5, ∞) 423 44 221(v 3, 2)(v 2, 1)(v 4, 2) (v 1, 0)(v 5, 3)42 3 44 22 1(v 3, 2) (v 2, 1) (v 4, 4) (v 1, 0)(v 5, 3) 42 3 44 221。
