线性规划习题(28)

（12）最小生成树问题 某大学准备对其所属的 7 个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图 中 V1，??，V7 表示 7 个学院办公室，图中的边为可能联网的途径，边上的所赋权数为这条 路线的长度，单位为百米。请设计一个网络能联通 7 个学院办公室，并使总的线路长度为最短。 V2 3 V1 10 V6 3 3 4 V7 5 8 4 V5 2 V4 3 1 V3 7 V1 3 V2 3 4 V7 5 8 V5 2 V4 1 V3 7

G

V6

4

G1

解：①在 G 中找到一个圈（V1，V7，V6，V1）,并知在此圈上边[V1，V6]的权 数 10 为最大，在 G 中去掉边[V1，V6]得图 G1 ，如上图所示

V2 3 V1 1 V6 3 3 4 4 V7 5 V5 2 V4 1 3 V6 4 V5 1 V3 7 V1 3 V2 3 4 V7 2 V4 1 V3 7

G2

G3

②在 G1 中找到一个圈（V3，V4，V5，V7，V3） ，去掉其中权数最大的边 [V4，V5]， 得图 G2 ，如上图所示 ③在 G2 中找到一个圈（V2，V3，V5，V7，V2） ，去掉其中权数最大的边 [V5，V7]，得图 G3 ，如上图所示

V2 3 V1 1 V6 3 3

1

V3 7 4

V2 3 V1 V4 1 3 V6 3

1

V3 7

V7

2

V7

2

V4

V5

G4

V5

G5

④在 G3 中找到一个圈（V3，V5，V6，V7，V3） ，去掉其中权数最大的边 [V5，V6]，得图 G4 ，如上图所示 ⑤在 G4 中找到一个圈（V2，V3， V7，V2） ，去掉其中权数最大的边 [V3，V7]，得图 G5 ，如上图所示 ⑥在 G5 中已找不到任何一个圈了，可知 G5 即为图 G 的最小生成树。 这个最小生成树的所有边的总权数为 3+3+3+1+2+7=19 (13)某一个配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短。下

图给出了配送中心到快餐店的交通图，图中 V1，??，V7 表示 7 个地名，其中 V1 表示配送中 心，V7 表示快餐店，点之间的联线表示两地之间的道路，边所赋的权数表示开车送原料通过这段 道路所需要的时间（单位：分钟） （18,3） （4,1） V 2 （0,S） 4 V1 V 12 （配送中心） 2 V2 18 V2 （16,2） V3 16 V2 2 V

2

V4

7 V 82 V

2

V6 （25,4） 6 V

2

解：①给起始点 V1 标号为（0，S） 2 ②I={V1},J={ V2，V3，V4，V5，V6 ,V7} ，边的集合{[Vi，Vj] ︳Vi，Vj 两点中一点属 于 I,而另一点属于 J}={[ V1，V2]，[ V1，V3]}，并有 S12=L1+C12=0+4=4 ； S13=L1+C13=0+18=18 min (S12,S13)= S12 =4 给边[ V1，V2]中的未标号的点 V2 标以（4，1） ，表示从 V1 到 V2 的距离为 4，并且在 V1 到 V2 的最短路径上 V2 的前面的点为 V1. ③这时 I={V1 ，V2},J={V3，V4，V5，V6 ,V7}，边的集合{[Vi，Vj] ︳Vi，Vj 两点中一 点属于 I,而另一点属于 J}={[ V1，V3]，[ V2，V3]，[ V2，V4]}，并有 S23=L2+C23=4+12=16 ；S24=L2+C24=4+16=20 ；min (S23,S24 , S13)= S23 =16 给边[ V2，V3]中的未标号的点 V3 标以（16，2） ④这时 I={V1 ，V2 ，V3},J={V4，V5，V6 ,V7}，边的集合{[Vi，Vj] ︳Vi，Vj 两点中一 点属于 I,而另一点属于 J}={[ V2，V4]，[ V3，V4]，[ V3，V5]}，并有 S34=L3+C34=16+2=18 ； S35=L3+C35=16+6=22 ； S24=L2+C24=4+16=20 min (S34,S35,S24)= S34 =18 给边[ V3，V4]中的未标号的点 V4 标以（18，3） ⑤这时 I={V1 ，V2 ，V3 ，V4},J={V5，V6 ,V7}，边的集合{[Vi，Vj] ︳Vi，Vj 两点中