去找 http://www.7zhao.net SETP3： 转换为二叉树。
具体过程略■
21. 证明:正则二叉树必有奇数个结点，且树叶数t与结点数n之间有：t=（n-1）/2。
证明：因为正则二叉树的边数ｍ与分支点数ｉ的关系为：ｍ＝２ｉ，又因为是树，因此结点数ｎ满足：ｎ＝ｍ－１＝２ｉ－１，必为奇数。叶结点数ｔ和枝点数之和为ｎ，即：ｔ＋ｉ＝ｎ，因此t=（n-1）/2■
22. 遍历一棵树是指访问这个树的每个结点一次且仅一次。遍历二叉树有如下三种方式: (1)前序遍历:访问根, 遍历左子树,然后遍历右子树。 （2)中序遍历: 遍历左子树,访问根,然后遍历左子树。 （3)后序遍历: 遍历左子树, 遍历右子树,然后访问根。 根据三种不同遍历形式,分别写出图11.15中各结点被访问的顺序。
图11.15
解：
（１） 前序遍历结果：abdfjglmcehi （２） 中序遍历结果：jfdlgmbachei （３） 后序遍历结果：jflmgdbhieca■
23. 设英文字母b，d，g，o，y，e出现的频率分别是0.014，0.038，0.02，0.08，0.131,构造一个与它们对应的前缀码,并写出符号串dogbybed对应的编码。
解：构造最优树如下：
17
去找 http://www.7zhao.net 0.014，0.038，0.02，0.08，0.02，0.131 0.014，0.02， 0.02，0.038，0.08，0.131 ＝＝＝＝＝＝ 0.034 0.02，0.038，0.08，0.131 ＝＝＝＝＝＝＝＝ 0.0５2 0.038，0.08，0.131 ＝＝＝＝＝＝＝＝ 0.０９ 0.08，0.131 ＝＝＝＝＝＝＝＝ 0.283 0.131 ＝＝＝＝＝＝＝＝＝ ０．４１４ 0 0 1 1 1 0 0 1 0.08 (o) 0.038 (d) 0.131 (e) 0 1 0.0２ (y) 0.014 (b) 0.02 (g) 因此获得相应的前缀码：b=00000,g=00001,y=0001,d=001,o=01,e=1 所以dogbybed的编码为：0010100001000000001000001001■ 完成题目 [1，2，3,4，５，6，7，8，１０，１１，１２,14，１５,16，１７,18，19，20，２１，22,23] 勘误： １．２３题，［频率分别是0.014，0.038，0.02，0.08，0.131］改为［频率分别是0.014，0.038，0.02，0.08，0.02，0.131］ｐ２２３ ２．7题，［ 设G为n（n≥3）阶简单图，证明G或中必含圈］改为［设G为n（n≥５）阶简单图，证明G或中必含圈］p223
第十三题未证明
18
去找 http://www.7zhao.net
习题十二
1．证明下面3个图都是平面图。
证明：因为所给图都可以平面图的方式画出来，如下：
■ 2．下面3个图都是平面图，先给图中各边标定顺序，然后求出图中各面的边界和面度。 解：略■ 3. 设G是阶数不小于11的图。证明：G或中至少有一个是非平面图。 证明：假设G和都是平面图，因为，所以至少有一个图的边数，设，有因为是平面图，所以有，求解得ｎ≤１０．与题设G是阶数不小于11的图矛盾，因此G或中至少有一个是非平面图■ 4. 证明：具有6个结点、12条边的简单连通平面图，它的面的度数都是3。 证明：因为是简单连通平面图，因此根据欧拉公式有 ６－１２＋ｆ＝２，所以有８个面。根据面度和与边的关系有，Σｄ（ｆｉ）＝２ｍ＝２４；因为要在平面上围成一个面，至少需要３边，所以８个面，Σｄ（ｆｉ）≥２４。因此，不存在面度大于３的面，所有面的度数都是３■
5. 证明：少于30条边的简单平面图至少有一个顶点的度不大于4。
19
去找 http://www.7zhao.net 证明：假设图Ｇ（ｎ，ｍ）的每个结点的点度都大于等于５，根据握手定理及平面图的判定定理有： ５ｎ≤２ｍ＜６０ （１） 握手定理 ｍ≤３ｎ－６ （２） 根据（１）得到：ｎ<１２ 结合（１）（２）得到：５ｎ／２≤３ｎ－６，所以ｎ≥１２，矛盾。因此假设不成立，题设结论成立■
6. 设G是具有k（k≥2）个连通分支的平面图，则 n–m+f=k+1。 证明：针对每个连通分支而言，满足欧拉公式及：ni-mi+fi = 2,因此Σni – Σmi + Σfi = 2k.因为对G图而言只有一个外部面，但在针对每个连通分支引用欧拉欧式的时候都计算了一次外部面，因此外部面多计数k-1次，所以总面数比求和公式少k-1个面，因此有Σni – Σmi + Σfi-(k-1) = 2k-(k-1) 得 n–m+f=k+1■ 7. 证明：对K3.3的任何一边e，K3,3-e是平面图。同样，对K5的任何边e，K5-e也是平面图。 证明：因为K3,3-e，K5-e 可以画成平面图的形式，如下： ■ 8. 当m和n取什么值时Km,n是平面图？证明你的结论。 解：当m≤2，n≥1, 或n≤2，m≥1时，Km,n是平面图。因为： 当m≤2，n≥1时，如果m = 1 , 那么此图是一颗树，因此是平面图 如果ｍ＝２，那么可以将此图案如下方式图示： 20