《运筹学》课程教学资源（试卷习题）第8章 图与网络分析习题解答

《运筹学》第八章图与网络分析习题解答2. (1)/(2)x(3)/(4)×(5)/(6)×(7)x(8)y(9)/(10)y6.解：图（1）顶点数6个：边数12条：每个项点的次数都为4次，是简单图。图（2）顶点数5个：边数9条：每个顶点的次数V4，Vs3次，其它各顶点都为4次，是简单图。7. 解： 完全图的边数为"(Iμ-1) 条。29.解：(v1,2)(V2,7)(vg,14)VVNs(vi,6)(VgJ12)(vs,8)(o,0)(V10,15)VYv9V1V,V1V4V10VT(vi,3)(v4,10)(v,11)10.解：V,(v2,7)(v1,4)(V2,7)VV6(V7,8)V.(0.0)V4V.(V2,6)Vs.6Vs(V,8)V(Vi,3)从V到Vg的最短路为V→Vs→V→Vg。11.解：此为最短路间题。铺设路线由下图给出，最短输水管道为6.5公里

《运筹学》第八章图与网络分析习题解答 2．（1）√ （2）X（3）√ （4）X（5）√ （6）X（7）X（8）√（9）√（10）√ 6．解：图（１）顶点数６个；边数１２条；每个顶点的次数都为４次，是简单图。 图（２）顶点数５个；边数９条；每个顶点的次数 v4 ,v5 ３次，其它各顶点都为 ４次，是简单图。 7．解：完全图的边数为 2 n(n 1) 条。 9．解： 10．解： 从 1 v 到 9 v 的最短路为 1 5 7 9 v v v v 。 11．解：此为最短路问题。铺设路线由下图给出，最短输水管道为 6.5 公里。 V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 （o,0） (v1,2) (v1,6) (v1,3) (v2,7) (v5,8) (v9,14) (V9,12) (v4,10) (v7,11) (v10,15) V1 V2 V3 V4 V5 V6 V7 V8 V9 1 （o,0） (v1,4) (v2,7) (V1,3) (V2,6) (V2,7) (V5,6) (V7,8) (V7,8)

1→?+@+???Y?12.最大流为32。13.最大流为10。14.解：（1）最大流量为6，最小费用为84；（2）最大流量为3，最小费用为27

12．最大流为 32。 13．最大流为 10。 14．解：（1）最大流量为 6，最小费用为 84； （2）最大流量为 3，最小费用为 27。 ① ④ ⑧ ③ ② ⑤ ⑥ ⑦