图8 图8中(b)就是(a)的生成树。 图G=(VE)有生成树的充要条件是G为连通图 三、最小树问题 在给定连通赋权无向图G=(V,E,W)中,求G的生成树T=(VE),使E 各边权WC0)的总和最小的问题称为最小树问题。其数学模型为: W(T=min > w (v,v)∈T 其中T*称为最小树。 许多网络问题都可归结为最小树问题,如设计长度最小的公路网把若 干城市联通;设计用料最省的电话线网把有关单位联系起来。求最小树有 以下两种方法: (1)用“避圈法”(Kπ rusal算法)求最小树。其基本思想是:开始选 条权最小的边,以后每步从未选的边中选取一条权最小的边,使它与已选 边不构成圈,直至选够q-1条边止 (2)用“破圈法”(管梅谷算法)求最小树。其方法步骤是: 1°先从图G任取一个圈,并从圈中去掉一条权最大的边。若在同 圈中有几条都是权最大边,则任选其中一边去掉。 2°在余下的子圈中,重复上述步骤,直至没有圈止。 例27 (a) (b) 图 8 图 8 中(b)就是(a)的生成树。 图 G=(V,E)有生成树的充要条件是 G 为连通图。 三、最小树问题 在给定连通赋权无向图 G=(V,E,W)中，求 G 的生成树 T=(V,E)，使 E 各边权 Wij(0)的总和最小的问题称为最小树问题。其数学模型为： W T = min Wij ( ) * (vi,vj)T 其中 T*称为最小树。 许多网络问题都可归结为最小树问题，如设计长度最小的公路网把若 干城市联通；设计用料最省的电话线网把有关单位联系起来。求最小树有 以下两种方法： （1）用“避圈法”(Kruskal 算法)求最小树。其基本思想是：开始选一 条权最小的边，以后每步从未选的边中选取一条权最小的边，使它与已选 边不构成圈，直至选够 q－1 条边止。 （2）用“破圈法”(管梅谷算法)求最小树。其方法步骤是： 1°先从图 G 任取一个圈，并从圈中去掉一条权最大的边。若在同一 圈中有几条都是权最大边，则任选其中一边去掉。 2°在余下的子圈中，重复上述步骤，直至没有圈止。 例 ° ° ° ° ° ° ° ° ° e1 l1 l6 e6 l7 e7 e2 e4 l2 e3