最小树问题的求解方法
常用的求最小树的算法有:破圈法、避圈法、边割法和Dijkstra算法等等。
基本概念
最小树问题是网络最优化问题之一，是指如何从网络的支撑树中求出最小树的问题。求解最小树问题常用破圈法和贪婪算法。最小生成树问题是组合优化中的一个重要的问题。
自五十年代后期Rosenstiehl,Prim和Kruskal先后给出求解这一问题的算法以来，人们对这个问题的研究兴趣一直未断，相关的理论被应用到很多领域。这个问题己经得到了很好的解决，其中经典的算法有破圈法、边割法、还有避圈法。
研究背景及意义
随着网络通信技术的日益成熟，互联网在人们生活中发挥着越来越重要的作用，基于网络的应用和服务也是层出不穷。其中一些应用如视频会议、网络教学、多人游戏等，传输时间长、数据量大、要求网络延迟小，对网络的传输和处理能力要求很高。
对于这样的应用如果使用单播或广播方式进行通信，数据需要不断的复制，传输的数据量太大，传输的效率很低。同时在数据传输时需要使用大量的带宽，对带宽的要求很高，带宽较低时很容易使网络阻塞。多播能够有效的解决这些网络应用。多播(multicast)也称为组播，是一种从源节点向多个目的节点传输同一信息的通信方式。所有的目的节点组成的集合被称为多播组，多播组中的每个成员被称为多播组成员。多播通信有多种方法进行路由，其中最简单的也是最常用的方法是沿树状结构进行路由。
多播树(multicasting tree)}'〕是一棵根为源节点的生成树，它包含了所有的目的节点。利用多播树进行数据传输的优点在于，从根节点开始数据以并行方式沿树干传输，最终到达所有的目的节点，这样能够加快传输速度。
此外，在数据传输过程中，只在树权处进行数据信息的复制，这样网络中传输的信息最少，能够减少占用的带宽，提高网络利用率。由于多播路由是根据多播树进行路由的，因此如果能够找到费用最小的多播树，多播路由问题就得到了解决。
寻找费用最小的多播树可以概括为寻找给定节点集的最小生成树，这就是Steiner最小树问题，得到的最小生成树称为Steiner最小树。Steiner最小树问题根据不同情况又可以细分为垂直距离的、欧几里得距离的、图的等。由于图的Steiner最小树问题应用最为广泛。
杨雪心神： 1、破圈法 2、避圈法 3、顺序生枝法
方山县15838167088： 离散数学 最小生成树 不太懂 求解 - ？
杨雪心神： 1) 树是无回路的连通图.2)对于某个图,求它的最小生成树,比较简单的方法,先画出图中所有节点,从权值最小的边开始依次连接顶点,注意不要形成回路,最后得到的图就是最小生成树.
方山县15838167088： 离散数学中求最小生成树的方法中点集法是怎么操作的 - ？
杨雪心神：[答案] 1) 树是无回路的连通图. 2)对于某个图,求它的最小生成树,比较简单的方法,先画出图中所有节点,从权值最小的边开始依次连接顶点,注意不要形成回路,最后得到的图就是最小生成树.
方山县15838167088： 求最小生成树 - ？
杨雪心神： 最小生成树 1、 最小生成树 对于连通的带权图(连通网)G,其生成树也是带权的.生成树T各边的权值总和称为该树的权,记作: 这里: TE表示T的边集 w(u,v)表示边(u,v)的权. 权最小的生成树称为G的最小生成树(Minimum SpannirngTree...
方山县15838167088： 普里姆算法到底是怎么算的? - ？
杨雪心神： )生成树一个连通图的生成树是它的极小连通子图,在n个顶点的情形下,有n-1条边.生成树是对连通图而言的,是连通图的极小连通子图,包含图中的所有顶点,有且仅有n-1条边.非连通图的生成树则组成一个生成森林;若图中有n个顶点,...
方山县15838167088： 关于最小树,以下叙述()正确 - 上学吧普法考试？
杨雪心神： 最小生成树算法.可以用PRIM算法....你简单看看 普里姆(Prim)算法 (1)算法思想 通过每次添加一个新节点加入集合,直到所有点加入停止的最小生成树的算法原理:每次连出该集合到其他所有点的最短边保证生成树的边权总和最小1. 首先...
方山县15838167088： 如何用动态规划法解决最小生成树问题 - ？
杨雪心神： 标题: 最小生成树 时 限: 1000 ms 内存限制: 10000 K 总时限: 3000 ms 描述: 有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特...
