运筹学 operations research 第三章图与网络分析 ③、最小支撑树问题 问题:求网络的支撑树,使其权和最小。 算法1(避圈法):把边按权从小到大依次75 添入图中,若出现圈,则删去其中最大 边,直至填满n1条边为止(n为结点数)。55 [例7]求上例中的最小支撑树 v3.5 解: 3 v v v3.5 v4http://www.tju.edu.cn 第三章 图与网络分析 问题：求网络的支撑树，使其权和最小。 3、最小支撑树问题 5 5.5 v1 v2 v3 v4 v5 3.5 7.5 4 2 3 算法 1（避圈法）：把边按权从小到大依次 添入图中，若出现圈，则删去其中最大 边，直至填满n-1条边为止（ n为结点数） 。 [ 例7] 求上例中的最小支撑树 解： 3 v1 2 v4 4 v5 5 v2 v3 3.5