第七章 特 殊 图 类
习题7.1
1. 设树T 有6条边，试问T 有多少个结点？
2．若无向图G 中有n 个结点，n-1条边，G 为树。这个命题正确吗？为什么？ 3．设无向图G 有n 个结点，n-1条边，则G 为连通图当且仅当G 中无回路。 4. 设G 是一个森林，由3个连通分支组成，若它有15个结点，试问G 有多少条边？ 5. 画出具有6个结点的所有不同构的树。 6. 任何一棵非平凡树中，至少有两片树叶。
7．在图7-2中，⑴，⑵所示的连通图中各有几棵非同构的生成树？
8．在图7-4中所示的带权图G 共有多少棵生成树，它们的权各为多少？其中哪些是图中的最小生成树？ 9．用Kruskal 算法，求图7-6的最小生成树，并计算出该生成树的权。
图
7-6
⑵
⑴ 图
7-2
图7-4
习题7.2
1. 一个有向图G ，仅有的一个结点入度为0，其余所有结点的入度均为1，G 一定是根树吗？
2. 五个结点可以形成多少棵根树？并指出这些根树都是几元树。 3．根树中最长路径的端点都是树叶吗？为什么？ 4．证明本节定理4（完全二元树有奇数个结点）。
5．对图7-10给出的二元树分别进行先根遍历、中根遍历、后根遍历并写出结果。 6．求带权2、3、5、7、8、11的最优树。 习题7.3
1．在图7-12所示的三个图中，哪几个是偶图？哪几个不是偶图？是偶图的，请给出互补结点子集；不是偶图的，请说明理由。
2. 试证明树是一个偶图。
3. 一次舞会，共有n 位男士和n 位女士参加，已知每位男士至少认识两位女士，而每位女士至多认识两位男士，问能否将男士和女士分配为n 对，使得每对中的男士和女士彼此都认识？
4. 今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周三人只熟悉数学、物理两门课程。问能否安排他们五人每人只上一门自己熟悉的课程，使得每门课程都有人教。说明理由。
习题7.4
1．试证明图7-13所示的两个图均为平面图。
图7-12
a
(2) (3)
图7-10
a
b c d
e f
g
h
i
2．指出图7-15所示的两个图各有几个面；写出每个面的边界和秩。
3．试证明：在有6个结点、12条边的连通简单图中，每个面均由3条边围成。 4．指出图7-16所示的图为非面图。
图
7-16
(1)
(2)
图7-15
(1)
(2)
图
7-14
(1)
(2)
图7-13
5．在简单平面图G 中，至少有一个度数小于等于5的结点。
6．证明小于30条边的简单平面图G 中至少有一个度数小于等于4的结点。
复习题7
1．一棵树T 有5个2度结点，3个3度结点，4个4度结点，2个5度结点，其余都是1度结点，问T 有多少个1度结点？
2．设无向
3．设无向
5．设无向图G 是有)2(,≥k k 棵构成的森林，至少在G 中添加多少条边才能使G 成为一棵树？
6. 用Kruskal 算法求图7-18(a)的一棵最小生成树。
7．图7-19⑴给出的赋权图表示7个城市a,b,c,d,e,f,g 及架起城市间直接通讯线路的预测造价，试给出一个设计方案使得各城市之间能够通信且总造价最小，要求计算出最小总造价。
(a)
13 图
7-18
8．画出所有不同构的高为2的二元树，其中有多少棵完全二元树？有多少棵满二元树？
9．设T 为任意一棵完全二元树，m 为边数，t 为树叶数，试证明：22-=t m 。其中2≥t 。
10．证明：若T 是有n 个结点的完全二元树，则T 有2/)1(+n 片树叶。 11．分别用先根、中根和后根的次序遍历如图7-21`所示的二元树。 12．根据图7-22中所示的两棵二元树，产生两个前缀码。
13．⑴求带权2，3，5，7，8的最优二元树T 。 ⑵求T 对应的二元前缀码。
⑴
⑵
图7-22
图7-19
a b
⑴
14．在通信中要传输八进制数字0，1，2，…，7。这些数字出现的频率为： 0：30﹪；1：20﹪；2：15﹪；3：10﹪；4：10﹪；5：60﹪；6：5﹪；7：4﹪。 如何编一个二元前缀码，使通讯中出现的二进制数字尽可能地少。具体要求如下：
⑴ 画出相应的二元树；
⑵ 写出每个数字对应的前缀码；
⑶ 传输按上述比例出现的数字10000个时，至少要用多少二进制数字？
15．证明如果G 是二部图，它有n 个顶点，m 条边，则4/2
n m 。
16．某单位按编制有7个空缺P 1，P 2，…，P 7。有10个申请者a 1，a 2，…，a 10，他们的合格工作岗位集合依次是：{ P 1, P 5, P 6}，{ P 2, P 6, P 7}，{ P 3, P 4}，{ P 1, P 5}，{P 6, P 7}，{ P 3}，{ P 2, P 3}，{ P 1, P 3}，{P 1}，{P 5}。如何安排他们工作使得无工作的人最少？
17．在某单位有6个未婚女青年L 1，L 2，L 3，L 4，L 5，L 6，有6个未婚男青年G 1，G 2，G 3，G 4，G 5，G 6，他们都想结婚，但也不是随便哪一个都可以，他们心中都有一张表，只愿意和表上的人结婚，现在知道L 1，L 2…，L 6的表分别是：
L 1: { G 1, G 2, G 4}; L 2: { G 3, G 5}; L 3: { G 1, G 2, G 4}; L 4: { G 2, G 5, G 6}; L 5: { G 3, G 6}; L 6: { G 2, G 5, G 6} G 1, G 2…，G 6的表分别是：
G 1: { L 1, L 3, L 6} G 2: { L 2, L 4, L 6} G 3: { L 2, L 5}
G 4: { L 1, L 3} G 5: { L 2, L 6} G 6: { L 3，L 4，L 5} 请问如何分配，使得男女双方都满意且结婚的对象最多。
2
3
5 ⑴
⑶ 8 15
7
⑷
图7-24