第十章 (图与网络分析)

第十章 图与网络分析

精典习题

10.1 证明如下序列不可能是某个简单图的次的序列：

（1）7,6,5,4,3,2 （2）6,6,5,4,3,2,1 （3）6,5,5,4,3,2,1

10.2 已知9个人921,,,v v v 中，1v 和两个人握过手， 32,v v 各和四个人握过手，

7654,,,v v v v 各和五个人握过手，98,v v 各和六个人握过手，证明这九个人中一定可以找出

三个人互相握过手。

10.3 有八种化学药品A 、B 、C 、D 、P 、R 、S 、T 要放进储藏室保管。出于安全原因，下列各组药品不能储存在同一室内：A-R 、A-C 、A-T 、R-P 、P-S 、S-T 、T-B 、T-D 、B-D 、D-C 、R-S 、R-B 、P-D 、S-C 、S-D 问储存这八种药品至少需要多少间储藏室。

10.4 已知有十六个城市及他们之间的道路联系（见图10-1）。某旅行者从城市A 出发，沿途依次经过J 、N 、H 、K 、G 、B 、M 、I 、E 、P 、F 、C 、L 、D 、O 、C 、G 、N 、H 、K 、O 、D 、L 、P 、E 、I 、F 、B 、J 、A ，最后到达城市M 。由于疏忽，该旅行者忘了在图上标明各城市的位置，请应用图的基本概念及理论，在图10—1中标明各城市A~P 的位置。

10.5 十名研究生参加六门课程的考试。由于选修的课程不同，考试门数也不一样。表10—1给出了每个研究生应参加考试的课程（打Δ号的）。规定考试应在三天内结束，每天上下午各安排一门。研究生们提出希望每人每天最多考一门，又课程A 必须安排在每一天上午考，课程F 安排在最后一门，课程B 只能安排在中午考，试列出一张满足各方面要求的考试日程表。

图10-1

e 1 v 1

v 2

v 3 v 4

v 5

v 6

v 7

v 8 v 9

v 10

e 2

e 3 e 7

e 4

e 5

e 6

e 8

e 9

e 10 e 11

e 12

e 13

e 14

e 15

图10-2

表10-1

10.6 用破圈法和避圈法找出图10-2的一个支撑树。

10.7 用破圈法和避圈法求图10—3中各图的最小树。

(a)

7 2

8

2

3 2 4

4

3

6 1

3

6

5

4 1

7 4

3

1

2

2

2

3

4

2 5

(b)

10.8 已知世界6大城市：（Pe ）、（N ）、（Pa ）、（L ）、（T ）、（M ）。试在由表10—1所示交通网络的数据中确定最小树。

表10-2

10.9 有九个城市921,,,v v v ,其公路网如图10—4所示。弧旁数字是该段公路的长度，有一批货物从1v 运到9v ，问走那条路最短？

2

2

3 2

2

1

5

3

3

5 2

2

4

2

2

5

3

6

4

7

4

5

3

6 3 2

1

(c)

(d)

图10-3

3

4 3 3

2 3 1

2 2.5

5 4

2 V 1

V 2 V 3

V 4 V 5

V 6

V 7 V 8

V 9

3

图10-4

10.10 用标号法求图10—5中V1到各点的最短路。

10.11 用Dijksrea 方法求图10—6中V1到各点的最短距离。

10.12 求图10-7中从V1到各点的最短路。

10.13 在图10—8中

(1) 用Dijkstra 方法求从V1到各点的最短路； (2) 指出对V1来说那些顶点是不可到达的。

V1

2

8 4 7

6 1 5 1

2

9

1

4 3

2 1 6 3

1

7 9 2

4

V2 V3

V4

V5

V6

V7 V8

V9

V10

V11

图

10-6

1(a)

(b)

图10-5

V 1

9

8 5

2

1

8

3

7 4

3

10

7

3 图10-7

10.14 已知八口海上油井，相互间距离如表10-2所示。已知1号井离海岸最近，位5浬。问从海岸经1号井铺设油管将各油井连接起来，应如何铺设使输油管线长度为最短（为便于计算和检修，油管只准在各井位处分叉）。

10.15 设某公司在六个城市c1, …, c6 有分公司，从c i 到c j 的直达航线票价记在下面矩阵的（i ，j ）位置上（∞表明无直达航线，需经其他城市中转）。请帮助该公司设计一张任意两城市的票价最便宜的路线表。

??

?

???

???

?

??????????∞∞∞∞∞∞

055252510

550102025251001020402010015252015050102540500

10.16 在如图10-9 所示的网格中，每弧旁的数字是（c ij ，f ij ）。 (1) 确定所有的数集；

V4

4

1

3

3 4 1 6

2

4 3 6 7

V1

V2 V7

V5

V6 V8

V3 图10-8

(2) 求最小截集的容量； (3) 证明指出的流是最大流。

10.17求如图10-10 所示的网络的最大流（每弧旁的数字是（c ij ，f ij ）。

10.18用Ford-Fulkerson 的标号算法求图10-11中所示各容量网络中从Vs 到Vt 的最大流，并标出个网络的最小割集。图中各弧旁数字为容量，括弧中为流量。

s

v t

v 图10-10

t

t

v s v )

2(2(a)

(b)

s

v

t

v

(2,2)

(4,3)

(3,3)

(1,0)

(2,2) (5,2)

(3,1)

图 10-9

10.19 某单位招收懂俄、英、日、德、法文的翻译各一人。有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文。问最多有几人能得到招聘，有分别被聘任从事那一文种的翻译。

10.20求图10-12中从s →t 的最小费用最大流，各弧旁数字为（，

）。

10.21 图10-13中，A 、B 为出发点，分别有50 和40 单位物资往外发运，D 、E 为收点，分别需要物资30 和60 单位，C 为中转点，各弧旁数字为（，）。求满足上述收发量要求最小费用流。

图10-13

s

t

（a ）

（b ）

t

图10-12

t v

v

(c)

t

(d)

图10-11

10.22 设G=（V,E）是一个简单图，令δ（G）=(称δ（G）为G的最小次)。证明：

（1）若δ（G）2，则G必有图；

（2）若δ（G） 2，则G必有包含至少δ（G）+1条边的图。

10.23 设G是一个连通图，不含奇点。证明：G中不含割边。

10.24 给一个联通赋权图G，类似于求G的最小支撑树的Kruskal方法，给出一个求G 的最大支撑树的方法。

10.25 下述论断正确与否：可行流f的流量为零，即v(f)= 0，当且仅当f是零流。

习题答案及详解

10.1 证明

（1）由图的性质定理知，任一个图中，奇点的个数为偶数。7，6，5，4，3，2中存在3个奇数，所以不可能是某个图的次的序列，更不是某个简单图的次的序列。

【或者】假设7，6，5，4，3，2为某个简单图的次的序列，则图中有6个点，作为简单图点的最大次数为n-1，即最大次数为5，显然与存在点的次数为7矛盾。所以，7，6，5，4，3，2又是简单图的次的序列。

（2）由定理知，任一个图G=(V ，E)中，所有点的次数之和是边数的两倍，即图中点次的和为偶数。序列6，6，5，4，3，2，1的和为27，所以它不可能是一个图的次的序列，更不可能是某个简单图的次的序列。

【或者】假设6，6，5，4，3，2，1为某个简单图的次的序列，则图中存在7个点，不妨设为1V ，2V ，3V ，4V ，5V ，6V ，7V ，其中 1V ，2V 次为6，表明1V ，2V 与除自身外的剩余6个点均相连。即3V ，4V ，5V ，6V ，7V 的次不少于2，与7V 的次为1矛盾。所以，6，6，5，4，3，2，1不是某个简单图的次的序列。

（3）假设6，5，4，3，2，1为某个简单图的次的序列，则图中存在7个点，不妨设为1V ，2V ，3V ，4V ，5V ，6V ，7V ，

，因为1()d V =6, 7()d V =1,所以1V 与其他6个点相连，而7V 仅与1V 相连，又因为23()()5d V d V ==，则2V ，3V 与除7V 和自身之外的所有点相连，则6V 必须与2V ，3V 相连，所以6V 与1V ，2V ，3V 相连，与6()2d V =矛盾，所以6，6，5，4，3，2，1不是某个简单图的次的序列。

10.2 解：设9个人1V ，2V ，…9V 为9个点，两人握手设为两点之间存在相连边，握手问题转化为一个简单图，其中，1V ，2V ，…9V 次的序列为2，4，4，5，5，5，5，6，6。这9个人中一定可以找到3个互相握过手，转化为在图中一定存在3个点彼此相连。

因为，4567()()()()5d V d V d V d V ====，4V ，5V ，6V ，7V 之间一定存在两点相连。假如，4V ，5V ，6V ，7V 互相均不相连，因为次均为5，所以4V ，5V ，6V ，7V 均与剩余的4个点1V ，2V ，3V ，8V ，9V 相连，这与 1()d V =2矛盾。

不妨设4V ，5V ，6V ，7V ，中存在4V ，5V 之间相连。必可以找到第三点均与4V ，5V 相连。假设不存在第3点均与4V ，5V 相连，4V ，5V 分别与定义不同的4个点相连，即存在8个不同的点分别与4V 或5V 相连，加上4V ，5V 共计10个点，这与图中9个点矛盾。

所以在图中，必存在3个点彼此相连。 10.3 解：将8种化学药品A ，B ，C ，D ，P ，R ，S ，T 设定为8个点，两种药品不能贮存同一室内状态，设定为两点之间存在一边相连，画出药品关系图如下：（图10-3（a ））

在图（a ）中，两点之间相连的药品均不能存贮在一起。对于由点A ，B ，C ，D ，P ，R ，S ，T 的完全图，求图（a ）的补图，得图（b ）,在（b ）图中，彼此相连的药品均可以

为存贮庄点，因为()()2d S d D ==，从S ，D 开始搜索，（S ，A ，B ）彼此相连，（D ，R ）相连，（T ，C ，P ）彼此相连。

所以至少需要3间贮存室，存效组合为（S ，A ，B ），（T ，C ，P ），（D ，R ）。

10.4 解：依据旅行者的路线统计城市间的相互关系。

（a ）

（B ） 图10-3

由点的次可知，A ，D ，E ，H 为2，则为4个顶点；B ，C ，F ，G 的次为4，则为4个顶点；某系为边点，城市布局图为图10-4。

10.5 解：将课程A ，B ，C ，D ，E ，F 设定为6个点，同时学生选某课程认为存在相邻边。依据学生1-10的选课划分课程关系图10-5（a ），要求学生一天最多考1门，即图（a ）中相连的课程不能排在同一天。对于点ABCDEF 的关系图，求图（a ）的补图（b ）。

那么，图（b ）中相邻的课程可以安排在同一天，可保证学生一天最多考一门，所以（A ，E ），（F ，D ），（C ，B ）分别各为一天，安排如下：

A M I E

J P

C K

O D

图10-4

图10-5 （a ）

图10-5 （b ）

5

8v 10

(b)

e 1 v 1 v 2 v 3 v 4

v 5

v 6

v 7

v 8 v 9

v 10

e 2

e 3 e 7

e 4

e 5

e 6

e 8

e 9 e 10 e 11

e 12

e 13

e 14

e 15

(a)

5

8v 10 (b)

10.6 解：（破圈法）

寻找图中的圈，去掉圈中的一边。

（1）圈（1123321v e v e v e v ）去掉1e ；圈（2448562

v e v ev e v ）去掉4e ；圈（81391410158

v v v e v e v ）

去掉13v 。

（2）圈（123325571v e v e v e v e v ）去掉5e ；圈（48510694v e v e v e v ）去掉9e ， 得到支撑树(c)。

e 1 v 1

v 2

v 3 5

e 2

e 7 (d)

(e)

e 1 v 1

v 2

v 3 v 4

5

v 10

e 12

e 2

e 7

e 6

v 6

v 8

5

8v 10

(f)

(避圈法)

(1) 从1v 点出发，边相邻边增加边和点，保证不构成回路。1v 出发，增加

122375,;,;,e v e v e v 。

(2) 3v 相邻边6e ，增加4v ，5v 相邻边10e ，12e ，增加点6v ，8v 。 (3) 6v 相邻边11e ，增加7v ，8v 相邻边13e ，15e ，增加点9v ，10v 。 将1210...v v v 点均包含在图中，且不存在回路，构成一个支撑树（f ）。

10.7 解：a ）（破圈法）

在图中寻找圈，去除圈中权值最大的边

（V 1 ，V 2 ，V 3）去除（V 1 ,V 3 ）边；（V 1 ，V 4 ，V 7）去除（V 4 ,V 7 ）边；（V 2 ，V 5 ，V 8）去除（V 2 ,V 8 ）边；（V 6 ，V 8 ，V 9）去除（V 7 ,V 8 ）边，得到图（a 2）

（V 2 ，V 5 ，V 3）去除（V 2 ,V 5 ）边；（V 3 ，V 6 ，V 4）去除（V 3 ,V 6）边；（V 5 ，V 6 ，V 8）去除（V 5 ,V 6 ）边，得到图（a 3）

（V 1 ，V 2，V 3 ,V 4）去除（V 1 ,V 2）边，( V 3 ，V 4，V 6 ,V 8，V 5) 去除（V 4 ，V 6）边, 得到图（a4）。

( V 1 ，V 4，V 3 ,V 5，V 8，V 7)去掉（V 3 ,V 4）边，得到图（a5）,图中不再有回路，则为最小树，其权值和为16s =

(避圈法)

从V 1 出发，即V =｛V 1｝其余点为V ，V 与V 间有边（V 1 ，V 2），（V 1 ，V 3），（V 1 ，V 7），（V 1 ，V 4），权值分别为7，8，3，2，权值最短边为（V 1 ，V 4）。则加粗边（V 1 ，V 4），令{}4V V V ??。V 与V 间最短边为（V 1 ，V 7），加粗边（V 1 ，V 7），令{}7V V V ??。 依次按照上述规则操作，直到V =?。则得到最小树为图（a 3）, 其权值和为16。

(a2)

v v 4

v 7

8

(a3) v v 4 v 7

8

(a4) 8

v v v

v 4

v 7 (a5) v 1

v 8

v 2 v 5 v 4 v 7

v 3 v 6 2

1

2

4

3 1

3

图10-7 （1）

(a1) v v 2 v 5 v 4 v 7

8

1

2

2

2

3

2 图10-7 （b ）

3

4

2

1

3 3

4 图10-7 （d ）

（b ）依图（a ）中的步骤，得到图b ）的最小树图为10-4 （b ），其权值和为12s =

（c ）依图（a ）中的步骤，得到图c ）的最小树图为10-7 （c ），其权值和为18s =

（d ）依图（a ）中的步骤，得到图d ）的最小树图为10-7 （d ），其权值和为17s =

2 2

2 1

3 2

2

2

2 图10-7 （c ） (a1) v 2 v 5

8 (a2)

v 2

v 5 8 (a5) v 1 v 8 v 2 v 5 v 4 v 7

v 3 v 6 2

1 2

4

3 1

3 图10-7 （2）

10.8解：6城市（Pe ），（N ），（Pa ），（L ），（T ），（M ）对应6个点，依表中数据得到交通网络图为：

按照避圈法，V=｛Pe ｝，V =｛T ，L ，Pa ，M ，N ｝，V 与V 的最短边为（Pe ，T ），加粗（Pe ，T ）边，{}T V V ??，即V=｛Pe ，T ｝，V =｛L ，Pa ，M ，N ｝，依次推导。

逐次加入边（Pe ，L ），（L ，Pa ），（L ，N ），（N ，M ），得到最小树图：

10-9解：利用双标号法，求19V V →的最短路线。

（1）从1V 出发，1V 标号为（1V ，0），V =｛1V ｝，其余点为V 。

（2）V 中点1V 相邻的未标号的点有24,V V ，1121412min{,}min{3,4}3r L d d d ---====

则对2V 进行标号2V （1V ，3），令2{}V V V ??，2/{}V V V ?。 （3）V 中点1V ，2V 与未标号的3654V V V V ，，，，

11223122612251114min{,,,}p L L d L d L d L d =++++=

14min{33,33,32,04}4L ++++==，给4V 标号4V （1V ，4V ）

，令44{},/{}V V V V V V ???

(4) 依（3）中的原理，V 与V 相邻边累计最小为（2V ，5V ），

55{},/{}V V V V V V ???

（5）按照上述原则，依次标号顺序为：

给3V 标号3V （2V ，6），V =｛1243V V V V ，，，｝； 给6V 标号6V （2V ，6），V =｛1243V V V V ，，，，6V ｝； 给7V 标号7V （4V ，7），V =｛1243V V V V ，，，，6V ，7V ｝； 给9V 标号9V （6V ，8.5），V =｛1243V V V V ，，，，6V ，7V ，9V ｝；

9V 已标号，因此，1V ~9V 的最短路线为1269V V V V →→→，最短路长为8.5。

10.10解：（a ）

（1）从1V 出发，令V =｛1V ｝，其余点为V ，给1V 标号为（1V ，0）。

3

4

3 3

2 3

1

2 2.5

5 4

2 V 1 (V1,0)

(V1,3) V 2 (V2,6)

V 3

V 4 (V1,4) V 5 (V2,5)

(V2,6) V 6

V 7 (V4,7)

V 8

(V6,8.5) V 9

3 5 (V1,0)

V3 (V5,29)

(V1,20) (V6,24) (V8,33) (V9,34) V11 (V11,44)

（2）V 与V 相邻边有｛（12,V V ）,(16,V V )｝，

1111211161116m i n {,}m i n {300,20}r L L d L d

L d =++=+

+=+，给6V 标号6V （1V ，20），

令6{}V V V ??

（3）V 与V 相邻边有｛（12,V V ）,( 67,V V )，（65,V V ），（62,V V ）｝

11112166716651662min{,,,}p L L d L d L d L d =++++=min{030,204,207,2020}++++

=1667L d +，给7V 标号7V （64,V V ），令7{}V V V ??。 （4）依次标号：5V （6V ，27），5{}V V V ??

8V （7V ，28）

，8{}V V V ??；4V （5V ，29），4{}V V V ?? 2V （1V ，30）

，2{}V V V ??；3V （2V ，31），3{}V V V ?? 9V （8V ，33）

，9{}V V V ??； 10V (9V ，34)，11V （8V ，34）

，12V （11V ，44），至此，全部点都已标注。

1V 到各点的最短路只需从该点出发，逆向搜索标号就可得到，且该标号中第2组数字

就是1V 到该点的最短距离。

1V → V 2 : 1V → V 2 ，30S = 1V → V 3 : 123V V V →→，31S = 1V → V 4: 1654V V V V →→→ ，29S =

V11

5 V3

V1

(V1,0) V2(V1,9) V3(V1,8)

V4(V2,10) V5(V2,1) V6

V7 (V4,13)

9

8

5 2 1

8

3

7 4

3

10 7 1V → V 5: 165V V V →→ ，27S = 1V → V 6: 16V V → ，20S = 1V → V 7: 167V V V →→ ，24S = 1V → V 8: 1678V V V V →→→ ，28S = 1V → V 9: 16789V V V V V →→→→ ，33S = 1V → V 10: 1678910V V V V V V →→→→→ ，34S = 1V → V 11: 167811V V V V V →→→→ ，34S = 1V → V 12: 16781112V V V V V V →→→→→， 44S =

(b)

(1) 从1V 出发，令V =｛1V ｝，其余点为V ，给1V 标号为（1V ，0） （2）V 与V 相邻边有｛（12,V V ）,( 13,V V )｝，

累计距离111121113111313min{,}min{09,08}r L L d L d L d L =++=++=+=，给3V 标号3V （1V ，8）

，令3{}V V V ?? （3）按照以上规则，依次标号，直至所有的点均标号为止， 1V 到某点的最短距离为沿该点标号逆向追溯。

标号顺序为：V 3 (V 1，8)，V 2 (V 1，9)，V 4 (V 2，10)，V 1 (V 4，13)，V 5 (V 2，11)，V 6 (V 5，14)。

1V 到各点的最短路见图中粗线。

10.11 解：

(1) 从1V 出发，令V =｛1V ｝，其余各点集合为V 。给1V 标号为（1V ，0）,V V →的所有边为｛（12,V V ），（14,V V ）｝，累计距离最小为

1111211141112min{,}min{02,08}2p L L f L f L f =++=++==+，给2V 标号为（1V ，2），令2{}V V V ?? 2/{}V V V ?

（2）V V →的所有边为｛（25,V V ），（24,V V ），（14,V V ）｝，累计距离最小为

11225122411141225min{,,}min{21,26,08}3p L L f L f L f L f =+++=+++==+，令

5{}V V V ??，5/{}V V V ?

（3）按照标号规则，依次给未标号点标号，直到所有点均已标号，或者V V →不存在有向边为止。

标号顺序为：V 5 (V 2，8)，V 9 (V 5，9)，V 4 (V 1，8)，V 4 (V 1，8)，V 6 (V 9，10)，V 8 (V 9，11)，V 7 (V 6，14)，V 3 (V 4，15)，V 10 (V 1，15)，V 11 (V 10，19)。

则1V 到各点的最短路线按照标号进行逆向追索（结果见图中粗线）。

例如，111V V →最短路为，125971011V V V V V V V →→→→→→，权值和为19。 10.12解：

求解1V 到各点的最短路。

（1）从1V 出发，1V 标号为（1V ，0），令V =｛1V ｝，其余各点集合为V 。 （2）V V →的有向弧有｛（12,V V ），（14,V V ）｝，最小累计权值

1111211141112min{,}min{01,02}1p L L f L f L f =++=++==+，给2V 标号为（1V ，1）

，2

8

4 7 6

1 5

1 2

9

1

4

3 2

1 6 3

1

7 9

2

4

V1 (V1,0)

V2(V1,2) V3(V4,15) V4(V1,8) V5(V2,3)

V6(V9,10) V7(V6,14) V8(V9,11)

V9(V5,4) V10(V7,15)

V11(V10,19)