-
运
筹
学
教
程
（
第
二
版
）
习
题
解
答
8.1
证明在
9
座工厂之间，不可能每座工厂只与其他
3
座工厂有业务
联系，也不可能只有
4
座工厂与偶数个工厂 有业务联系。
解：将有联系的工厂做一条连线。
如果仅有
9
座工厂只与其他
3
座工 厂有业务联系，
说明顶点次数之和为
27
，
矛盾。
如果只有
4
座工厂与偶数个工厂有业务联系，其他
5
个工厂一定与奇数个工厂有
业务联系，说明顶点次数之和还是奇数，矛盾。
8.2
有八种化学药品
A
、
B
、
C
、
D
、
E
、
F
、
G
、
H
要 放进贮藏室。从
安全角度考虑，
下列各组药品不能贮存在同一室内：
A
—
C
，
A
—
F
，
A
—
H
，
B
—
D
，
B
—
F
，
B
—
H
，
C
—
D
，
C
—
G
，
D
—
E
，
D
—
G
，
E
—
G
，
E
—
F
，
F
—
G
，
G
—
H
， 问
至少需要几间贮藏室存放这些药品。
解：能贮存在同一室内的两种药品之间作一条连线。 贮存在同一室内的药品应
该构成一个完全图。
ABG
，< /p>
CFH
，
DE
构成完全图。故，存放这些药品最少需 要
3
间储藏室。
8.3
6
个人围成圆圈就座，
每个人恰好只与相邻者不相识，
是否可
以重新就座，使每
个人都与邻座认识
?
解：两个人认识作一条连线。
8.4
判定图
8-50
中的两个图能否一笔画出，若能，则用图形表示其
画法。
解：
(a)
图都是偶点，可以一笔画出。
(b)
图只有两个奇点，
一个奇点为起点，
另一
个奇点为终点。
8.5
求解如图
8-51
所示的中国邮路问题，
A
点是邮局。
8.6
分别用深探法、广探法、破圈法找出图
8-52
所示图的一个生成
树。
8.7
设计如图
5-53
所示 的锅炉房到各座楼铺设暖气管道的路线，使
管道总长度最
(
单位：
m)
。
8.8
分别用避圈法和破圈法求图
8-54
所示各图的最小树。
8.9
给定权数
1
，
4
，
9
，
16
，
25
，
36
，
49
，
64
，
81
，构造
—
棵霍夫曼
树。
8.10
如图
8-55
，
v
0
是一仓库，
v
< br>9
是商店，求一条从
v
0
到
v
9
的最短路。
8.11
< /p>
求图
8-56
中
v
1
到各点的最短路。