tulun

对于城市C2，----，C6，可以用类似于C1的方法得到最短路线 。

9 设G是图，＆是G 中最小度，K 是一个正整数，若k≤＆，试证明G 中有一

条长为k的简单路。

证明 不妨设＆≥0，当＆=0时，命题显然成立。以下设＆≠0，任取一点v0,显然d(v0)≥＆, 故可找到一相邻点v1。

设已找到vi, i＜＆. 由 d(vi)≥＆, 看vi 的相邻点，至少有一个不同于v0，v1，---，是vi –1取这样一个点设为vi+1；如此下去可一直找到v﹠，而（v0，v1，---，v﹠）正是

一条长为﹠的简单路。因此，若k≤＆,则必有一条长为k的简单路。

10 设G为图（可能无限），无回路，但若外加任意一边于G 后就形成一回路，试7证明G必为树。

证 按树的定义可知，只需证G为连通即可。任取不相领两点v,v1,由已知，加上边vv1后就形成一回路。于是去掉边vv1，从v到v1仍有路v,…,v1,即v,v1相连。由v,v1 的任意性可知G是连通的。因此，G必为树。 证毕。 11 在具有n个顶点的完全图kn中需删去多少条边才能得到树？

解 n个点的完全图kn中共有Cn2条边，而n个点中的树中共有n-1条边。因此需要 删除cn-(n-1)=.(n-1)(n-2)/2条边后方可得到树。

12 分别用三种不同的遍历方式写出图7-8中二叉树点的访问次序。 A

B C G D

E J

H I

K L

F

2

图7-8 解 先根次序：ABDEHKLCFGIJ; 中根次序：DBEKHLAFCIGJ; 后根次序：DKLHEBFIJGCA. 13 分别写出下列表达式的后缀表示： （1） （a+b）*c;

(2) ln(a+b)-c+e*f.

解 （1）首先将表达式化成二叉树如图7-9（a）,由此可知表达式的后缀表示为：ab+c*.

5

C C E F 1N A B

图7-9

（2）首先将表达式化为二叉树，如图7-9（b）,从而表达式的后缀表示为： ab+㏑c-ef*+.

14 设有5个城市v1,…,v5,任意两城市之间铁路造价如下（以百万元为单位）： W(v1,v2)=4, W(v1,v3)=7, W(v1,v4)=16, W(v1,v5)=10, W(v2,v3)=13, W(v2,v4)=8, W(v2,v5)=17, W(v3,v4 )=3, W(v3 ,v 5)=10, W(v 4,v 5)=12.

试求出连接5个城市而且造价最低的铁路网。

解 首先将本题用一权图来描述，于是求解此题便成为求权图中的最优支撑树问题。

按克鲁斯卡尔算法，图7-10中（b）～ (e) 就是求解最优支撑树的过程。

V1 7

4

V3 16 13 V2

10 8 10 17 3

V4 12 V5

（a）

V3 3 V4

(b)

6

V1 V1 V1 7 7 4

V3 V2 V1 V2 V3 V2

3 3 3 10

(c) (d) (e)

15 试用克鲁斯卡尔算法求图7-11所示权图中的最优支撑树。

1

7

3 4

9 2

5

5 6

8 7 3

图7-11

解 图7-12（a）～ (e) 表示图7-11的最优支撑树。

1

1

1 2

3

(a) (b) (c)

1

3

1

3

2

3

5

2

3

7

2

(d) (e) 16 举出满足下列要求的具有5个点的有向图： （1）G有根，但是 不是强连通的；

（2）G存在一棵有向支撑子树，并标出这棵有向树； （3）G 是强连通的（将 G漠视为于是强连通的），但 G无根。 解 （1）如图7-13（a）, A是根，但是不存在从 B到D 的有向路。 （2）如图7-13（b），图7-13（c）是7-13（b）的一棵有向支撑树。 （3）如图7-13（d）。

(a) (b) (c) (d)

17 设 G（P,A）是有向图，G中任意两个不同点之间至多有一条弧，G中没有指向自身的弧，若不考虑G中弧的方向，把弧看成边，则 G是连通的。问 G是否有根？若能肯定 G有根，试给出证明，否则举出反例。

解 回答是否定的。举例如图7-13（d），将此有向图漠视为图以后，它是连通的，但它却无根。

18 设G=(P,A)为有向图，若G与根r，且无有向回路，问G是否是有向树？ 解 回答是否定的，举反例如图7-13中（a）。

19 证明：若r是有向图G的根，则G必含有一个以r为根的有向支撑树。

G1 G 2

图7-14 证 用如下方法来构造的支撑树：

令G0={r}，设已得GK是有向树，做GK+1如下：

选取P(G)中的某顶点v，使得v∈P(Gk)。设从v到r的有向路进入Gk后第一个顶点v’，进入Gk前的最后一个顶点是v”，再在GK中加入弧v”v’，及顶点v”。

8