分别用破圈法和避圈法求下图中的最小部分数。
分别用破圈法和避圈法求下图中的最小部分数。
参考答案和解析
(1)给图10．5．5(a)中的点和边分别加上名称如图10．5．6所示。 1)避圈法。开始选－条最小权的边其过程如图10．5．7所示以后每步中总从未被选取的边上选－条权最小的边并使之与已选取的边不构成圈(每－步中如果有两条或两条以上的边都是权最小的边则从中任选－条)。 按照此方法算法步骤如下①表示第i次的选取。则以{e 13 e 15 e 3 e 9 e 10 e 5 e 17 }构成的图正好就是一个支撑树。 支撑树的权为 1＋1＋2＋2＋3＋3＋4＝16对应的最小树如图10．5．8所示。 2)破圈法。任取一个圈从圈中去掉－条权最大的边。(如果两条或两条以上的边都是权最大的边则去掉任意其中－条)在余下的图中重复这个步骤－直得到一个不含圈的图为止这时的图便是最小树。 按照上述方法去边的具体过程如图10．5．9所示。 其中④表示第i次进行删除的边。 得到最小树如图10．5．10所示。 (2)给(b)中的点和边加上名称分别为v i e i 如图10．5．11所示。 1)避圈法。依次找不构成圈的最小边寻找过程如图10．5．12所示。 则由{e 3 e 4 e 5 e 9 e 8 e 2 }构成最小支撑树如图10．5．13所示。 树的权重为1＋1＋2＋2＋3＋2＝11。2)破圈法。其本质为依次从所构成的圈中去除最大边去除过程如图10．5．14所示。 最后剩下的边{e 2 e 3 e 4 e 5 e 8 e 9 }所构成的图为最小支撑树图。 总权重为1＋1＋2＋2＋2＋3＝11。 (3)给(c)中的点和边加上名称分别为v i e i 如图10．5．15所示。 1)避圈法。寻找最小边的过程如图10．5．16所示。 由{e 6 e 5 e 2 e 4 e 8 e 9 e 10 e 11 e 15 }构成最小支撑树。如图10．5．17所示。 总权重为 1＋2＋2＋2＋3＋3＋2＋2＋2＝19 2)破圈法。去除边的过程如图10．5．18所示。 最后剩下{e 1 e 2 e 5 e 6 e 8 e 9 e 10 e 11 e 15 }构成最小支撑树。如图10．5．19所示。 总权重为 2＋2＋2＋3＋1＋2＋3＋2＋2＝19(4)给(d)中的点和边加上名称分别为v i e i 如图10．5．20所示。 1)避圈法。寻找最小边的过程如图10．5．21所示。 最后找出(e 7 e 6 e 1 e 8 e 2 e 10 }构成最小支撑树。如图10．5．22所示。 总权重为 ω(T)＝3＋4＋4＋2＋1＋3＝17 2)破圈法。去除图中最大边的过程如图10．5．23所示。 最后剩下的{e 1 e 2 e 10 e 8 e 7 e 8 }构成最小支撑树。如图10．5．24所示。 总权重为 ω(T)＝3＋4＋4＋2＋1＋3＝17 (1)给图10．5．5(a)中的点和边分别加上名称,如图10．5．6所示。1)避圈法。开始选－条最小权的边,其过程如图10．5．7所示,以后每步中,总从未被选取的边上选－条权最小的边,并使之与已选取的边不构成圈(每－步中,如果有两条或两条以上的边都是权最小的边,则从中任选－条)。按照此方法,算法步骤如下,①表示第i次的选取。则以{e13,e15,e3,e9,e10,e5,e17}构成的图正好就是一个支撑树。支撑树的权为1＋1＋2＋2＋3＋3＋4＝16对应的最小树如图10．5．8所示。2)破圈法。任取一个圈,从圈中去掉－条权最大的边。(如果两条或两条以上的边都是权最大的边,则去掉任意其中－条),在余下的图中,重复这个步骤,－直得到一个不含圈的图为止,这时的图便是最小树。按照上述方法,去边的具体过程如图10．5．9所示。其中,④表示第i次进行删除的边。得到最小树如图10．5．10所示。(2)给(b)中的点和边加上名称分别为vi,ei,如图10．5．11所示。1)避圈法。依次找不构成圈的最小边,寻找过程如图10．5．12所示。则由{e3,e4,e5,e9,e8,e2}构成最小支撑树,如图10．5．13所示。树的权重为1＋1＋2＋2＋3＋2＝11。2)破圈法。其本质为依次从所构成的圈中去除最大边,去除过程如图10．5．14所示。最后剩下的边{e2,e3,e4,e5,e8,e9}所构成的图为最小支撑树图。总权重为1＋1＋2＋2＋2＋3＝11。(3)给(c)中的点和边加上名称分别为vi,ei,如图10．5．15所示。1)避圈法。寻找最小边的过程如图10．5．16所示。由{e6,e5,e2,e4,e8,e9,e10,e11,e15}构成最小支撑树。如图10．5．17所示。总权重为1＋2＋2＋2＋3＋3＋2＋2＋2＝192)破圈法。去除边的过程如图10．5．18所示。最后剩下{e1,e2,e5,e6,e8,e9,e10,e11,e15}构成最小支撑树。如图10．5．19所示。总权重为2＋2＋2＋3＋1＋2＋3＋2＋2＝19(4)给(d)中的点和边加上名称分别为vi,ei,如图10．5．20所示。1)避圈法。寻找最小边的过程如图10．5．21所示。最后找出(e7,e6,e1,e8,e2,e10}构成最小支撑树。如图10．5．22所示。总权重为ω(T)＝3＋4＋4＋2＋1＋3＝172)破圈法。去除图中最大边的过程如图10．5．23所示。最后剩下的{e1,e2,e10,e8,e7,e8}构成最小支撑树。如图10．5．24所示。总权重为ω(T)＝3＋4＋4＋2＋1＋3＝17
相关考题：
单选题（）通常用于分离筛选氨基酸、核苷酸和维生素等的产生菌。工具菌是一些相对应的营养缺陷型菌株。A透明圈法B变色圈法C生长圈法D抑菌圈法