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

第9章部分习题解答设：这棵树有n片树叶4*2+3*3+n=2(2+3+n-1),解得：n=93.（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，12：3，3，1，1，1，13：3，2，2，1，1，14：2，2，2，2，1，111.设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、解：如下图。将给定节点按出现频率排序，从大到小，维护一个队列。（将频率当成节点权值）弹出最小的两个节点权值相加，再将相加的权值和作为一个新的节点加入队列中。重复1，2，直到队列中只剩下唯一节点。结果：按照左1右0编码：a:0b:110c:100d:1111e:101f:1110平均位数：1*0.35+3*0.15+3*0.2+4*0.1+3*0.15+4*0.05=2.45（位）证明：设e为无向连通图G中的一条边，e不在G的任何生成树中，则e一定是环。如果e不是环，那么e连接两个不同的结点u和v。由于G是连通的，若G是树且是生成树，连接两个不同的结点u和v的边只有1条，e在G的生成树中。若G不是树，它至少存在一个生成树T。生成树T包含G中的所有结点，且没有回路。在生成树T中添加边e。由于e连接u和v，且u和v在生成树T中，