最优化计算方法课后习题答案----高等教育出版社。施光燕

6,7题解如下 第六题答案

1.与v1点相邻接的顶点有v2、v3两点，l2=1，l3=2，取Min{l2、l3}=1，于是连接v1、v2两点，令顶点集S={v1、v2}；图示如下：

V2 V1

2.与S={v1、v2}相邻接的顶点有v3、v4、v5三点，l5=l2+d25=1+3=4，l4=l2+d24=1+3=4，

Min{l2+d23、l3}=1，取Min{l3、l4、l5}=1，于是连接v1、v3两点，令顶点集S={v1、v2、v3}；图示如下：

V2 V1 V3

3.与S={v1、v2、v3}相邻接的点有v4、v5、v7三点，l5=l2+d25=1+3=4，l4=l2+d24=1+3=4， l7=l3+d37=2+8=10，取Min{l4、l5、l7}=4,于是连接v2、v4、v5三点，令顶点集S={v1、v2、v3、v4、v5}；图示如下：

V5

V2

V4

V1

V3

4.与S={v1、v2、v3、v4、v5}相邻接的点有v6、v7两点，l6=Min{l5+d56、l4+d46}=6，l7=min{ l3+d37、l4+d47、l5+d57}=7，取min={ l6、l7}=6，于是连接v4、v6两点，令顶点集S={v1、v2、v3、v4、v5、v6}；图示如下：

V2

V6 V4

V1

5.与S={v1、v2、v3、v4、v5、v6}相邻接的点有v7、v8两点，l7=min{ l3+d37、l4+d47、l5+d57、

V3 v5、v7和v6、v7这两组点，令顶点集S={v1、v2、l6+d67}=7，l8=l6+d68=11，min={ l7、l8}=7，于是连接V5 v3、v4、v5、v6、v7}；图示如下

V5 V2

V6

V4

V1

V3 V7

6.与S={v1、v2、v3、v4、v5、v6、v7}相邻接的点有v8，l7= l5+d57=l6+d67=7，连接v7、v8两点，得到l8=10，如图所示：

V5

V2

V6

V4

V1

V3 V7 V8

从图上可以看出从v1到v8的最短路有两条，一条是：

V1 另一条是：

V2 V5 V7 V8

V1 V2 V4 V6 V7 V8

这两条路径均是最短路，最短路的长度是10.

第七题答案

人选一个初始方案，如下图所示：

通过分析，我们发现有的链并未饱和，即没有达到最大流，通过寻找增广链的方法来求最大流，增广链有

将增广链与初始方案结合后即可得到最大流为9，最大流方案如下图所示：