石油输送管道铺设最优方案的选择问题：如图所示，其中A为出发点，E为目的地，B、C、D分别为三个必须建立油泵加压站的地区，其中的B1、B2、B3;C1、C2、C3;D1、D2分别为可供选择的各站站点。图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道才使总费用最小？
6 2 C B 3 3 D5 5 3
3 E 5 2 7 4 A BC 4 4 4 D 4 1 5 4 B 5 C
解：
第四阶段：D1—E 3；D2—E 4； 第三阶段：C1—D1—E 5；C2—D2—E 8；C3—D1—E 8；C3—D2—E 8； 第二阶段：B1—C1—D1—E 11；B1—C2—D2—E 11；B2—C1—D1—E 8； B3—C1—D1—E 9 ；B3—C2—D2—E 9；
第一阶段：A—B1—C1—D1—E 14；A—B1—C2—D2—E 14； A—B2—C1—D1—E 13；A—B3—C1—D1—E 13；
A—B3—C2—D2—E 13；
最优解：A―B2―C1―D1―E；A―B3―C1―D1―E；A―B3―C2―D2―E 最优值：13
（12）最小生成树问题
某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中V1，……，V7表示7个学院办公室，图中的边为可能联网的途径，边上的所赋权数为这条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。
V2 3 V1 10 V6 3 3 4 V7 5 8 4 V5 2 1 V3 7 V1 V4 3 3 V2 3 4 V7 5 8 V5 2 1 V3 7 V4 G V6 4 G1 解：①在G中找到一个圈（V1，V7，V6，V1）,并知在此圈上边[V1，V6]的权
数10为最大，在G中去掉边[V1，V6]得图G1 ，如上图所示
V2 3 V1 1 V6 3 3 4 1 V3 7 V2 3 V1 V4 1 3 V6 3 1 V3 7 4 V7 5 2 4 V7 2 V4
②在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 V5 4 V7 2 1 V3 7 V1 V4 1 3 V6 V5 3 V2 3 V7 2 1 V3 7 V5 G2 4 V5 G3 V4 G4 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） V2 （0,S） 4V1 （配送中心） 18162V4 7856V5 （24,3） V6 （25,4） 612V7 （27,5） （快餐店） （16,2） V3 解：①给起始点V1标号为（0，S） ②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两点中一点属于I,而另一点属于J}={ [ V4，V6]，[ V4，V5]，[ V3，V5]}，并有
S46=L4+C46=18+7=25 ； S45=L4+C45=18+8=26 ；min (S46,S45 ,S35)= S35 =24 给边[ V3，V5]中的未标号的点V5 标以（24，3）
⑥这时I={V1 ，V2 ，V3 ，V4 ，V5 },J={ V6 ，V7}，边的集合{[Vi，Vj] ︳Vi，Vj两点中一点属于I,而另一点属于J}={[ V5，V7]，[ V4，V6] }，并有
S57=L5+C57=22+5=27 ；min (S57,S46)= S46 =25 给边[ V4，V6]中的未标号的点V6 标以（25，4）
⑦这时I={V1 ，V2 ，V3 ，V4 ，V5 ，V6 },J={ V7}，边的集合{[Vi，Vj] ︳Vi，Vj两点中一点属于I,而另一点属于J}={[ V5，V7]，[ V6，V7] }，并有
S67=L6+C67=25+6=31 ；min (S57,S67)= S57 =27 给边[ V5，V7]中的未标号的点V7 标以（27，5）
⑧此时I={V1 ，V2 ，V3 ，V4 ，V5 ，V6 ，V7},J=空集，边集合{[Vi，Vj] ︳Vi，Vj两点中一点属于I,而另一点属于J}=空集，计算结束。
⑨得到最短路。从V7 的标号可知从V1 到V7 的最短时间为27分钟。 即：配送路线为： V1 →V2 →V3 →V5 →V7 （14）最小生成树问题
某电力公司要沿道路为8个居民点架设输电网络，连接8个居民点的道路图如图所示，其中V1，……，V8表示8个居民点，图中的边表示可架设输电网络的道路，边上的赋权数为这条道路的长度，单位为公里，请设计一个输电网络，联通这8个居民点，并使总的输电线路长度为最短 。
V2 4 V1 2 V3 G V4 2 4 6 V5 7 5 V8
2 3 2 5 V6 3 V7 ①在图中找到一个圈（V1，V2，V5，V3）,并知在此圈上边[V1，V2]和 [V3，V5]的权数4为最大，在图中去掉边[V1，V2] ； ②在图中找到一个圈（V3，V4，V8 ，V5 ，V3, V1），去掉其中权数最大的边 [V4，V8]；
③在图中找到一个圈（V3，V4， V5，V3），去掉其中权数最大的边 [V4，V5]； ④在图中找到一个圈（V5，V2，V6，V7 ，V5），去掉其中权数最大的边 [V2，V6]；
⑤在图中找到一个圈（V5，V7， V8，V5），去掉其中权数最大的边 [V5，V8]。 ⑥在图中已找不到任何一个圈了，可知此即为图G的最小生成树。 这个最小生成树的所有边的总权数为2+2+4+2+3+3+2=18
（15）最大流问题
某地区的公路网如图所示，图中V1，……，V6为地点，边为公路，边上所赋的 权数为该段公路的流量（单位为千辆/小时），请求出V1 到V6 的最大流量。
V2 8 4 V5 12 5 6 V1 6 10 6 5 V4 6 V6 V3
解：第一次迭代：
选择路为V1 →V3 →V6 。弧（V3 ，V6）的顺流流量为5，决定了pf=5，改进的网
络流量图如图所示：
V2 0 6 8 4 0 6 10 5 5 0 6 5 0 0 0 5 0 0 V5 12 0 5→ V4 V1 6 0 5 0 V6 →5 第一次迭代 后的总流量 V3 第二次迭代：