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
又归纳法可证，GK是有向树。
按如上做法便可得到G中以r为根的支撑树。 20 能否对图7-14的边指定方向，使其成为欧拉图？
解 G可以，如图7-15（a）所示，由于G1中的每一个点都是平衡点。
G2不可以，图7-15（b）中所有点的度都是3，因此不论怎样指定边的方向，G2中的每个点都不是平衡点。因此不可能适当地指定G2中各边的方向，使其成欧拉图。
(a) (b) 图7-15
21 下列图形是否可以一笔画出？如可以的话画出欧拉图，否则说明原因。
G1 G 2 图7-16
解 不可以。因为中有8个度为奇数的顶点。
可以。按照边上的标号依次读下来，便可以一笔画出。见图7-17
9
1
5 6 16
4
12 13
11
10 9 14
7
2
8
3
图7-17
21 举出满足下列要求的具有5个点的图。
（1）没有哈密顿回路，也不能适当指定各边的方向使其具有欧拉路； （2）有哈密顿回路，但是不能适当指定各边的方向使其具有欧拉路； （3）没有哈密顿回路，但是能适当指定各边的方向使其具有欧拉路； （4）有哈密顿回路，也能适当指定各边的方向使其具有欧拉路。 解 见图7-18（a）～（d），它们分别满足条件（1）～（4）
（a） （b）
（c） （d）
图7-8
23 使用平面图定义及Jordan曲线性质证明K3..3是非平面图。
证 用反证法。K3..3如图7-19（a）所示，假设可以把K3..3画成一个平面图。
10
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库tulun(2)在线全文阅读。
相关推荐：