第九章 图与网络分析

–44v16–1vT22v10587vT3vS1–2vS–13v3v3v23v2(e)

L(f(2)) (f) f(3)

–16–44vv11vT32vv110487vT4vS–1–2vS3v3v2(g)

v24v3 L(f(3)) (h) f(4)

图9-47

9.19 解：求解过程如图9-48所示。f(4)即为最大流，也为最小费用最大流。

d(f(4))?7?2?10?10?7?7?5?1?5?4?12?9?5?5?321。

v127v39v150v3055vS103175vTvS055v2(a)

4v4v20v4 L(f(0)) (b) f(1)

7v1–22v39v172v3255vS10–3–1–77vT–5vS055vTv2

4v449

v20v4

(c)L(f(1)) (d) f(2)

–7v1–27v39-9v177v3755vS10–3–1–77vS–5505vTv24v4(e)

v20v4

L(f(2)) (f) f(3)

–99v1–2–7v3v177v31205vS103–1–77vT–5vS1005vT–10v24v4v25v4

(g)

L(f(3)) (h) f(4)

v1–2–7–1v39–9vS1037vT–5–10v24v4(4)

(i) L(f)

图9-48

9.20 解：首先用Floyd算法可求得各点之间的最短路矩阵为

50

??v?1?v2??v3?v4??v5?v?6??v7v1035v2302v3520644v4v5v69.36.34.56.33.31.56034302.54.81.809.36.36.33.3634.51.52.54.81.86.33.31.5v7?6??3??4? 6.3??3.3?1.5??0???max??9.3????6.3???6?? ?9.3???6.3???4.8*?????6.3??(1) 设置一个售票处，使最大服务距离为最小，相当于求居民点网络中每一顶点到其他顶点的最短路，并求出到其他各顶点最大距离最小的顶点。从上面的矩阵可以看出，顶点v6到其他顶点的最大距离最小，因此设置一个售票处应该设在v6。

(2) 设置两个售票处，为使最大服务距离最小。应该考虑减少v6到其他顶点的最大距离，可以搜索到v6到v4的最短路为4.8，v5到v4的最短路为3；继续考虑v6到其他点的最大距离，该点为v1，但是不存在其他点到v1和v4的距离小于4.5。因此设置两个售票处应该设在v5和v6。

9.21解： 以A1,A2,A3为起点，B1,B2,B3,B4为终点，可得一网络图，虚增始发点S，收点T，见图9-49，弧上记号为最大容量，表示仓库可供给量和零售店最大销售量。Ai?Bj上的最大容量没有标注。原问题化为最大流问题。

A120S12A3B412A2B298B310TB114

图9-49

使用标号算法从零流出发，过程如下： 步骤1：标号过程

将S标号为(—,??)，?S???；

51

检查S的邻接点A1，A1满足(S,A1)?E，fSA1?cSA1，令?A1?mni(cSA1?fSA1,?S)

?min(20?0,??)?20，将A1标号为(?S,20)。

检查A1的邻接点B1，B1满足(A1,B1)?E，fA1B1?cA1B1，令

?B?min(cAB?fAB,?A) ?min(???0,20)?20，将B1标号为(?A1,20)。

111111检查B1的邻接点T，T满足(B1,T)?E，fB1T?cB1T，令

?T?min(cBT?fBT,?B) ?min(14?0,20)?14，将T标号为(?B1,14)。

111得到可增广链S?A1?B1?T，?T?14。 步骤2：调整过程 由fij??fij??T

?1T?fB1T??T?0?14?14 fB?1B1?fA1B1??T?0?14?14 fA?1?fSA1??T?0?14?14 fSA结果如图9-50(a)所示。

经过5轮标号调整，(S,A1),(S,A2),(S,A3)已经达到最大容量，算法结束，

?(S,A1),(S,A2),(S,A3)?就是一个最小割集，W?c(S,A1)?c(S,A2)?c(S,A3)?41，

即最大总货量为41，调运方案见图9-50(f)。

(?S,20)(?A1,20)A1(20,14)(?,??)(??,14)B1(14,14)B2(9,0)(8,0)T(?B1,14)A1(20,14)(?,??)(?S,12)(??,14)B1(14,14)(?A2,12)S(12,0)A2S(12,9)A2(12,0)(??,9)B2(9,9)T(?B2,9)(8,0)B3(10,0)A3B4(12,0)A3B3(10,0)B4(a)第一次标号、调整(SA1B1T,?T?14) (b)第二次标号、调整(SA2B2T,?T?9)

52