x12216?13y114x1?0(50,0)y1y2(70,60)(50,30)(50,30)(50,0)(60,60)?0x201919022y20x2(60,0)(60,0)(50,0)x0y(60,60)(30,30)x32023230y?30x(40,0)x3(40,0)(40,0)y?3(30,0)y(40,0)(50,30)?0(30,30)(30,0)x40?y?3x4(30,30)?y?3
(a) L(f(2)) (b)f(3)
图9-15
4、作长度网络L(f(3))如图9-16(a)，最短路为x?x1?y1?y。在网络中相应的可增广链上用最大流算法进行流的调整：
Q??{(x,x1),(x1,y1),(y1,y)}，Q???
?4?min{min(cij?fij(3)),minfij(3)}?{20,50,10}?10
Q?Q?f(4)(3)??fij??4??(3)f?ij?(vi,vj)?Q?，W(f(4))?W(f(3))??4?130
其他d(f(4))?1390
f(4)的结果见图9-16(b)。
x12216?13y1?14x1?0(50,40)(50,0)(50,10)y1y2(70,70)(50,30)?0x201919022y2(60,60)0x2(60,0)(60,0)(50,0)x0x32023230y?3y0(60,60)(30,30)x(40,0)x3(40,0)(40,0)y?3y(30,0)?0(30,30)(40,0)(50,30)(30,0)x40?y?3(a) L(f(3)x4(30,30)?y?3
) (b)f(4)
图9-16
5、作长度网络L(f(4))如图9-17(a)，最短路为x?x1?y1?x2?y?3?y
?5?min{min(cij?fij(4)),minfij(4)}?10
Q?Q? 25
f(5)(4)??fij??5??(4)??fij(vi,vj)?Q?，W(f(5))?W(f(4))??5?140
其他d(f(5))?1600
f(5)的结果见图9-17(b)。
x122?16?13y1?14x100(50,20)(50,30)(60,50)(50,0)y1y2(70,70)?0x201919022y2(50,50)(50,0)x2(60,10)(60,0)x0x32023230y?3y0(60,60)(30,30)x(40,0)x3(40,0)(40,0)y?3(30,10)y(40,0)(50,30)?0(30,30)(30,0)0x4?y?3x4(30,30)?y?3
(a) L(f(4)) (b)f(5)
图9-17
?6、作长度网络L(f(5))如图9-18(a)，最短路为x?x3?y?3?y
?6?min{min(cij?fij(5)),minfij(5)}?20
Q?Q?f(6)(5)??fij??6??(5)f?ij?(vi,vj)?Q?，W(f(6))?W(f(5))??6?160
其他d(f(6))?2060
f(6)的结果见图9-18(b)。
x122?16?13y1?14x100(50,20)(50,30)(60,50)(50,0)y1y2(70,70)(50,50)(50,0)0x2019?192022y2x2(60,10)(60,0)(60,60)(30,30)x00x323230y?3?0yx(40,40)x3(40,0)(40,20)y?3y(30,30)(40,20)(50,50)?0(30,30)(30,0)0x4?y?3x4(5)(30,30)?y?3
(a) L(f
) (b)f(6)
26
图9-18
7、作长度网络L(f(6))如图9-19(a)，最短路为x?x3?y?3?y
?7?min{min(cij?fij(6)),minfij(6)}?20
Q?Q?f(7)(6)??fij??7??(6)f?ij?(vi,vj)?Q?，W(f(7))?W(f(6))??7?180
其他d(f(7))?2520
f(7)的结果见图9-19(b)。
x122?16?13y1?14x100(50,20)(50,30)(60,50)(50,0)y1y2(70,70)(50,50)(50,0)0x20?1919?022y2x2(60,10)(60,0)(60,60)(30,30)x0x32023?230y?3?0yx(40,40)x3(40,0)(40,20)y?3y(30,30)(40,20)(50,50)0(30,30)(30,0)0x4?y?3x4(30,30)?y?3
(a) L(f(6)) (b)f(7)
图9-19
由于W(f(7))?180，f(7)就是所求的最小费用最大流，最小费用为2520。
27
§9.3 习题
9.1 判断下列说法是否正确：
(1) 图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直都要严格注意。
(2) 在任一连通图G中，当点集V确定后，树是G中边数最少的连通子图。 (3) 如果图中从v1至其他各点的最短路在去掉重复部分后，则恰好构成该图的最小支撑树。
(4) 求网络最大流问题可归结为求解一个线性规划问题。
9.2 证明：在一个简单图G中，n为顶点个数，m为边的条数，如果
m?(n?1)(n?2)，则G中不存在孤立点。
29.3 n个企业之间，每个企业都与其它若干企业有业务往来，且n为奇数。证明：
(1) 至少有一个企业与其他偶数个企业有业务往来； (2) 不可能有偶数个企业与其他偶数个企业有业务往来。
9.4简单图与某顶点关联的边的数量称为该顶点的次，次为奇数的顶点称为奇点。证明：
(1) 简单图中所有顶点次的和一定为偶数，且为图中边的数量的2倍； (2) 简单图中奇点的个数一定为偶数。
9.5 设G?(V,E)是一个简单图，令?(G)?min{d(v)}（称?(G)为G的最小
v?V次）。证明：
(1)若?(G)?2，则G中必有圈；
(2)若?(G)?2，则G中必有包含至少?(G)+1条边的圈。 9.6设G是一个连通图，不含奇点。证明：G中不含割边。
9.7 设D?(V,A,C)是一个有向网络，证明：如果D中所有弧的容量cij都是整数，那么必存在一个最大流f?{fij}，使所有fij都是整数。
9.8 求图 9-20所示的无向图的关联矩阵和邻接矩阵。
28