《运筹学》 第八章图与网络分析习题及 答案

1.思考题

(１)解释下列名词，并说明相互之间的区别与联系：①顶点，相邻，关联边；

②环，多重边，简单图；③链，初等链；④圈，初等圈，简单拳；⑤ 回 路，初等路；⑥节点的次，悬挂点，孤立点；⑦）连通图，连同分图， 支 撑子图；⑧有向图，基础图，赋权图。⑨子图，部分图，真子图．

(２)通常用记号Ｇ＝（Ｖ，Ｅ）表示一个图，解释Ｖ及Ｅ的涵义及这个表达式 的涵义．

(３)通常用记号Ｄ＝（Ｖ，Ａ）表示一个有向图，解释Ｖ及Ａ的涵义及这个表 达式的涵义．

(４) 图论中的图与一般几何图形的主要区别是什么？ (５) 试述树与图的区别与联系．

(６) 试述 求最短路问题的Ｄijkstra算法的基本思想及其计算步骤． (７) 试述寻求最大流的标号法的步骤与方法．

(８) 简述最小费用最大流的概念及其求解的基本思想和方法．

(９) 通常用记号Ｎ＝（Ｖ，Ａ，Ｃ）表示一个网络，试解释这个表达式的涵义． (10) 在最大流问题中，为什么当存在增广链时，可行流不是最大流？ (11) 试叙述最小支撑树、最大流、最短路等问题能解决那些实际问题。 2.判断下列说法是否正确

(1) 图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何

形状无关。

(2) 一个图G 是树的充分必要条件是边数最少的无孤立点的图。

(3) 如果一个图G从V1到各点的最短路是唯一的，则连接V1到各点的最短路，再去掉重

复边，得到的图即为最小支撑树。

(4 )图G的最小支撑树中从V1到Vn的通路一定是图G从V1到Vn的最短路。 (5) {fij=0}总是最大流问题的一个可行流。 (6 )无孤立点的图一定是连通图。

(7) 图中任意两点之间都有一条简单链，则该图是一棵树。 (8) 求网络最大流的问题总可以归结为求解一个线性规划问题。

(9)在图中求一点Ｖ１到另一点Ｖn的最短路问题总可以归结为一个整数规划问题 (10) 图G中的一个点V1总可以看成是G的一个子图。

3.证明：在人数超过2的人群中，总有两个人在这群人中恰有相同的朋友数。

v4.已知九个人1,v2,,v9，v1和两个人握过手，v2,v3各和四个人握过手，

v4,v5,v6,v7各和五个人握过手，v8,v9各和六个人握过手。证明这九个人中，一定可

以找出三个人互相握过手。

V2 C1 C3 C2 V3

C5

C8 C7

V6 C9 C4 V4

V1 C6

V5 C10 C11

V7

C12 V8

C14

C13

V9

5．用破圈法和避圈法求下图的部分树

V1

V6 V4 V5 V2

V3 (1)

（３）

V2 V1 V3

V5 V4

(2)

８ ６ ３ ７ ４ ４ ２ ５

２

４

７ ５ ３ ２ １ ４

３

２

５ １

９ ４

２

３

７ （１）

２ ４

６

３

（２）

6．写出下面各图中的顶点数、边数及顶点的次数，哪些是简单图。

7．完全图Ｋn 有多少条边？ 8．求下列各图的最小树

（３）

v9.用标号法求下图中从1到各顶点的最短距离

５ ３ ３ ２

６ ８

１ ２ ７ ５ ４ ３

１

V2 5 V5 2 2 V1

2 5 3 1 V6 1 V8

6

8

6 V3

3 7

4

3 7

4

V9 7

3

V11

4 3

V4 V7

1

V10

10．在下图中用标号法求

V3

3 V2 3 V6

8 4 1 3 4 V1

2

V4

V7 2

V9

2 1

3

3

V5

V8

vvv（１）从1到各顶点的最短距离；（２）若从1到9，走哪一条路最短。

11．已知8个村镇，相互间距离如下表所示,已知1号村镇离水源最近，为5公里，问从水

源经1号村镇铺设输水管道将各村镇连接起来，应如何铺设使输水管道最短（为便于管理和维修，水管要求在各村镇处分开）。

各村镇间距离 （单位：公里） 到 2 3 4 5 6 7 8 从 1 2 3 4 5 6 7 1.5 2.5 1.0 2.0 2.5 3.5 1.5 1.0 2.0 1.0 3.0 2.5 1.8 2.5 2.0 2.5 2.0 1.0 2.5 1.5 1.5 1.0 3.0 1.8 1.5 0.8 1.0 0.5

4 10 V1

10 8 9

10 12

15 8

6

12

14

18 13 15 6 Vt

8

12.用标号法求下面网络的最大流.

13. 用标号法求下面网络的最大流.

2 4 V1 5 3 3 8 3 2 3 5 5 Vt

4

4

(6,6) V1 (5,1) (7,4) (2,3) (5,6) Vt

(3,2) (3,4)

(10,5) (1)

(8,2) V1 (9,2)

(4,19) (1,1)

(4,1)

(2,3)

(2)

Vt

14.求下列网络的最小费用最大流.括号内的两个数字,前一个是单位流量的费用,后一个是该弧的流量.

《运筹学》第八章图与网络分析习题解答

2．（1）√ （2）X（3）√ （4）X（5）√ （6）X（7）X（8）√（9）√（10）√ 6．解：图（１）顶点数６个；边数１２条；每个顶点的次数都为４次，是简单图。

图（２）顶点数５个；边数９条；每个顶点的次数v4 ,v5 ３次，其它各顶点都为４次，是简单图。

n(n1)2条。 7．解：完全图的边数为

(v1,2) V2

(v1,6) V3

(v2,7) V5 (v9,14) V8

5,8) (v V9 （o,0）

V1

(V9,12)

V6

V10

(v 7,11)

(v10,15)

V11

V4 (v1,3)

9．解：

10．解：

V7 (v4,10)

(v,7)

V3 2

(v1,4) V2 (V2,7) V6

(V7,8) V9

（o,0） V1

V4 (V 2,6)

1

V7

(V5,6)

V5 (V 1,3)

(V7,8) V8

vv5v7v9。 vv从1到9的最短路为1⑦

① ④ ⑧ ③ ② ⑤

⑥

11．解：此为最短路问题。铺设路线由下图给出，最短输水管道为6.5公里。

12．最大流为32。 13．最大流为10。 14．解：（1）最大流量为6，最小费用为84；

（2）最大流量为3，最小费用为27。