《运筹学》第八章图与网络分析习题
1.思考题
(１)解释下列名词，并说明相互之间的区别与联系：①顶点，相邻，关联边；
②环，多重边，简单图；③链，初等链；④圈，初等圈，简单拳；⑤ 回 路，初等路；⑥节点的次，悬挂点，孤立点；⑦）连通图，连同分图， 支 撑子图；⑧有向图，基础图，赋权图。
⑨子图，部分图，真子图．
(２)通常用记号Ｇ＝（Ｖ，Ｅ）表示一个图，解释Ｖ及Ｅ的涵义及这个表达式 的涵义．
(３)通常用记号Ｄ＝（Ｖ，Ａ）表示一个有向图，解释Ｖ及Ａ的涵义及这个表 达式的涵义．
(４) 图论中的图与一般几何图形的主要区别是什么？ (５) 试述树与图的区别与联系．
(６) 试述 求最短路问题的Ｄijkstra 算法的基本思想及其计算步骤． (７) 试述寻求最大流的标号法的步骤与方法．
(８) 简述最小费用最大流的概念及其求解的基本思想和方法．
(９) 通常用记号Ｎ＝（Ｖ，Ａ，Ｃ）表示一个网络，试解释这个表达式的涵义． (10) 在最大流问题中，为什么当存在增广链时，可行流不是最大流？ (11) 试叙述最小支撑树、最大流、最短路等问题能解决那些实际问题。
2.判断下列说法是否正确
(1) 图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何
形状无关。
(2) 一个图G 是树的充分必要条件是边数最少的无孤立点的图。
(3) 如果一个图G 从V 1到各点的最短路是唯一的，则连接V 1到各点的最短路，再去掉重
复边，得到的图即为最小支撑树。
(4 )图G 的最小支撑树中从V 1到V n 的通路一定是图G 从V 1到V n 的最短路。
(5) {f ij =0}总是最大流问题的一个可行流。
(6 )无孤立点的图一定是连通图。
(7) 图中任意两点之间都有一条简单链，则该图是一棵树。
(8) 求网络最大流的问题总可以归结为求解一个线性规划问题。
(9)在图中求一点Ｖ１到另一点Ｖn 的最短路问题总可以归结为一个整数规划问题 (10) 图G 中的一个点V 1总可以看成是G 的一个子图。
3.证明：在人数超过2的人群中，总有两个人在这群人中恰有相同的朋友数。
4.已知九个人921,,,v v v ，1v 和两个人握过手，32,v v 各和四个人握过手，
7654,,,v v v v 各和五个人握过手，98,v v 各和六个人握过手。
证明这九个人中，一定可
以找出三个人互相握过手。
5．用破圈法和避圈法求下图的部分树
C7
V 1
V 2 V 3
V 4
V 5
V 6
V 7
V 8
V 9
C 1 C 2
C 3
C 4 C 5
C 6
C 8
C 9
C 10
C 11
C 12 C 13
C 14
１ ７ ３
２ ５
３
２
６ ８
５ ４
３
１
6．写出下面各图中的顶点数、边数及顶点的次数，哪些是简单图。
7．完全图Ｋn 有多少条边？ 8．求下列各图的最小树
（３）
9.用标号法求下图中从1v 到各顶点的最短距离
V 1
V 2
V 3
V 4
V 5
V 6
(1)
V 2
3
(2)
５ １
３
７
４
２
５
２
８
６
２
７
４
３
７
４ ３
（１）
５
２
３
４
２
４
６
１
２
４
３
９
（２）
（３）
10．在下图中用标号法求
（１）从1v 到各顶点的最短距离；（２）若从1v 到9v ，走哪一条路最短。
11．已知8个村镇，相互间距离如下表所示,已知1号村镇离水源最近，为5公里，问从水
源经1号村镇铺设输水管道将各村镇连接起来，应如何铺设使输水管道最短（为便于管理和维修，水管要求在各村镇处分开）。
V 1
V 2
V 3
V 4
V 5
V 6
V 7
V 8
V9
V 10
V 11
2
6 3
5
7
5
2
1 3
7
2
3
4
1
4
3
1
6
7
3
8
4
V 1
V 2
V 3
V 4
V 5
V 6
V 7
8
V 9
4
3
3
2
4
3
8
3
1
2
3
2
1
12.用标号法求下面网络的最大流.
13. 用标号法求下面网络的最大流.
14.求下列网络的最小费用最大流.括号内的两个数字,前一个是单位流量的费用,后一个是该弧的流量.
《运筹学》第八章图与网络分析习题解答
2．（1）√ （2）X （3）√ （4）X （5）√ （6）X （7）X （8）√（9）√（10）√ 6．解：图（１）顶点数６个；边数１２条；每个顶点的次数都为４次，是简单图。
图（２）顶点数５个；边数９条；每个顶点的次数v 4 ,v 5 ３次，其它各顶点都为４次，是简单图。
7．解：完全图的边数为
2)
1( n n 条。
V
V t
12
15 V 1
V t
8
10
6
10
8
4
9
10
14
18 12
8
13
15
6
V 1
V t
(5,6)
(9,2)
(3,2)
(4,1)
(3,4)
(4,19)
(2,3)
(1,1)
(2)
V
t
(1)
9．解：
10．解：
从1v 到9v 的最短路为9751
v v v v →→→。
11．解：此为最短路问题。
铺设路线由下图给出，最短输水管道为6.5公里。
12．最大流为32。
13．最大流为10。
14．解：（1）最大流量为6，最小费用为84；
（2）最大流量为3，最小费用为27。
V 1
V 2 V 3
V 4
V 5 V 6
V 7
V 8
V9
V 10
V 11
（o,0）
(v 1,2) (v 1,6) (v 1,3)
(v 2,7) (v 5,8)
(v 9,14) (V 9,12) (v 4,10) (v 7,11)
(v 10,15)
V 1
V 2
V 3 V 4 V 5 V 6
V 7
V 8
V 9
1
（o,0）
(v 1,4) (v 2
,7)
(V 1,3)
(V 2,6)
(V 2,7) (V 5,6) (V 7,8) (V 7,8) ①
④
⑧
②
③
⑤
⑥
⑦。