离散数学及其应用--第2版第9章部分习题答案.docx

第9章部分习题解答

设：这棵树有n片树叶

4*2+3*3+n=2(2+3+n-1),解得：n=9

3.（3）

4.（2）

6、设一个树中度为k的结点数是nk（2≤k），求它的叶的数目。

解：设T的节点总数为n，叶节点数目为t，根据题意及握手定理有：

t+n2+n3+…+nk=n (1)

t+2n2+3n3+…k(nk)=2(n-1) (2)握手定理

(1),(2)联立求解得：

t=n3+2n4+…(k-2)nk+2■

7、证明:完全二元树必有奇数个结点。

证明：因为完全二元树的边数ｍ与分支点数ｉ的关系为：ｍ＝２ｉ，又因为是树，因此结点数ｎ满足：ｎ＝ｍ－１＝２ｉ－１，必为奇数。

8.证明：任何无向树都是二部图。

证明：以树Ｔ中任意结点ｕ为起点，将与ｕ最短距离为偶数的结点放入ｖ１结点集合，将与ｕ最短距离为奇数的结点放入ｖ２结点集合，那么这两个结点集合中，显然不存在公共点，同时两个结点集合组成了树的全部结点，因此是数Ｔ的结点集合的一个分化。假设在Ｖｉ集合中存在两个结点ｕ１，ｕ２是邻结点，那么就存在如下道路：ｐ＝ｕ．．．ｕ１ｕ２．．．．ｕ，其中ｐ１＝ｕ．．．ｕ１代表ｕ到ｕ１的最短路径，ｐ２＝ｕ２．．．ｕ代表ｕ到ｕ２的最短路径，且ｕ１ｕ２边不在最短路径上，否则他们的最短路径不是同奇偶的；因此，Ｐ中包含圈，这与树中无圈相矛盾，所以Ｔ中的边，只能存在于两个点集合之间，所以是二部图■

10、解：该图最多有4种非同构的生成树。由于该图有6个顶点，生成树有5条边，总度数为5*2。在生成树中最大度为5，最小度为1。因为该无向图最大度为4，故此不存在度为5的顶点。因此只可能有以下的非同构生成树：

1：4，2，1，1，1，1

2：3，3，1，1，1，1

3：3，2，2，1，1，1

4：2，2，2，2，1，1

11.设e是连通图G的一条边。证明：e是G的桥当且仅当e含于G的每个生成树中。

证明：

1）充分性：e是G的桥则e含于G的每个生成树中

假设e不包含在某棵生成树T中，那么e一定在T的余树边集中，那么G-{e}中依然包含树T,因此G-{e}连通，与e是桥矛盾，因此e含于G的每个生成树中；

2)必要性：e含于G的每个生成树中则e是G的桥

假设ｅ不是Ｇ的桥，那么Ｇ－｛ｅ｝依然连通，具有生成树，这些生成树也是Ｇ的生成树，且不包含ｅ，与e含于G的每个生成树中前提矛盾，因此e是G的桥。

综上所述，题设结论：e是G的桥当且仅当e含于G的每个生成树中成立

12.证明:简单连通无向图G的任何一条边，都是G的某一棵生成树的边。

证明：简单连通无向图G的任何一条边，要么是割边，要么是非割边。如果是割边，那么此边是所有生成树的树枝；如果不是割边，设边为ｅ，那么G-{e}连通，可以求出生成树Ｔ，此Ｔ也是Ｇ的生成树，且不包含ｅ，那么ｅ是Ｔ的余树的边。则Ｔ+{e},有唯一一个圈Ｃ，删除圈上任意一条非ｅ边，便得到一棵包含ｅ边的生成树■

14

.

15.设T1和T2是连通图G的两个不同的生成树，a是在T1中但不在T2中的一条边。证明：T2中存在一条边b，使得（T1-a）+b和（T2-b）+a也是G的两个不同的生成树。

证明：从T1中删除边a，得树T11和T12，我们用V1和V2分别表示T11和T12的结点集合。设Sa={e|e的两端点分别属于V1和V2}，显然a∈Sa。因为a不在T2中，所以a是T2的弦。设C(a)为在T2中增加边a后得到的基本回路，则在C(a)中必存在T2的树枝b不在T1中，但在Sa中。否则C(a)中T2的树枝都在T1中，或都不在Sa中。若C(a)中T2的树枝都在T1中，则C(a)中所有边都在T1中，和T1是树矛盾。若C(a)中T2的树枝都不在Sa中，则C(a)中除a外所有边的端点均在V1中或均在V2中，这与C(a)是基本回路矛盾。所以C(a)中必存在不在T1中但在Sa中的T2的树枝。设b是其中的一条，则(T1-{a})∪{b}连通无回路，又是G的生成子图，所以它是G的生成树。同理，(T2-{b})∪{a}也是G的生成树。■

16.证明:在完全二又树中,边的数目等于2(t-1)，式中t是树叶数目。

证明：设Ｔ中的结点数为ｎ，枝点数为ｉ；根据完全二叉树的定义，有下面的等式成立。n=i+t,m=2i,m=n-1.解方程组，得到m=2(t-1)

17.不一定

20.先根遍历：abdhinecfjkglmo

中根遍历：hdnibeajfkclgom

后根遍历：hnidebjkflomgca

波兰式：即前序遍历表示。

逆波兰式：即后序遍历表示。

22.（1）（3）（4）是

25、解：如下图。

将给定节点按出现频率排序