《离散数学第8,9章课后习题答案.pdf》由会员分享，可在线阅读，更多相关《离散数学第8,9章课后习题答案.pdf（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 8 章 习题参考答案1. 在一次 10 周年同学聚会上， 想统计所有人握手的次数之和，应该如何建立该问题的图论模型？解： 将每个同学分别作为一个节点， 如果两个人握过一次手就在相应的两个节点之间画一条无向边，于是得到一个无向图。 一个人握手的次数就是这个节点与其他节点所连接的边的条数，进而可得出所有人握手的次数之和。2. 在一个地方有 3 户人家，并且有 3 口井供他们使用。由于土质和气候的关系，有些井中的水常常干枯，因此各户人家要到有水的井去打水。不久，这3户人家成了冤家，于是决定各自修一条路通往水井，打算使得他们在去水井的路上不会相遇。试建立解决此问题的图论模型。解：将3 户人家分别看
2、做 3 个节点且将 3 口井分别看做另外 3 个节点，若1户人家与 1 口井之间有一条路， 则在该户人家与该口井对应的节点之间连一条无向边，这样就得到一个无向图。3. 某人挑一担菜并带一条狼和一只羊要从河的一岸到对岸去。 由于船太小，只能带狼、菜、羊中的一种过河。由于明显的原因，当人不在场时，狼要吃羊，羊要吃菜。通过建立图论模型给出问题答案。解：不妨认为从北岸到南岸，则在北岸可能出现的状态为24=16 种，其中安全状态有下面 10 种： （人，狼，羊，菜） ， （人，狼，羊） ， （人，狼，菜） ， （人，羊，菜） ， （） ， （人，羊） ， （菜） ， （羊） ， （狼） ， （狼，菜）
3、；不安全的状态有下面 6 种： （人） （人，菜） （人，狼） （狼，羊，菜） （狼，羊） （羊，菜） 。线将北岸的 10 种安全状态看做 10 个节点， 而渡河的过程则是状态之间的转移，这样就得到一个无向图，如图 8-1 所示。(人，狼，羊，菜)(人，狼，羊)(人，狼，菜)(人，羊，菜)(人，羊)(狼，菜)(羊)(狼)(菜)()图 8-1从上述无向图可以得出安全的渡河方案有两种：第 1 种： （人，狼，羊，菜） （狼，菜）（人，狼，菜） （狼）（人，狼，羊）（羊）（人，羊）（） 。第 2 中： （人，狼，羊，菜） （狼，菜）（人，狼，菜） （菜）（人，羊，菜）（羊）（人，羊）（） 。4. 证
4、明：任何 n 阶完全图 Kn的边数为 n(n-1)/2。2n(n 1)/ 2。证 n 阶简单图的边数为CN5. 对于 n 阶简单无向图 G，若其边数为 m，试计算 G 的补图G的边数。解：由于 G 的边数与其补图G的边数之和为n 阶完全图 Kn的边数为 n(n-1)/2，因此G的边数为n(n-1)/2-m。6. 证明：对于任意 n 阶简单图 G 有(G) n 1。证：根据简单图的定义，当一个节点与其余所有节点均邻接时，其度数达到最大，于是对于任意 n 阶简单图 G 有(G) n 1。7. 无向图 G 有 6 条边，各有一个 3 度和 5 度节点，其余均为 2 度节点，求G 的阶数。解 设图 G
5、 有 x 个节点度数为 2，则 G 的阶数为 x+1+1=x+2。根据握手定理有：1 3 1 5 x 2 2 6于是 x=2，进而 G 的阶数为 2+2=4。8. 将有向图 G 的边的方向去掉得到的无向图称为 G 的基础图， 基础图是完全图的有向图称为竞赛图。证明： 任意竞赛图的所有节点的出度平方和等于入度平方和。证 设 G=（V，E）是n 阶竞赛图，则其边数为En(n1)/2且对于任意vV有od(v) id(v) n 1根据竞赛图的定义知，odvV (v) 2id(v) vVEn(n 1)/ 22于是，vVod(v)=vV(n 1) id(v)2vV(n1) 2 (n1)id(v)(id(v
6、)2n(n 1)2 2(n 1)id(v) vVid(v)v V2=n(n 1)2 2(n 1) n(n 1)/ 2 =vV2id(v)id(v)v V29. 是否存在一个无向图，其度数序列分别为(1)5，4，4，3，3，2，2(2)4，4，3，3，2，2，2，2证： （1） 不存在，因为有3 个数位奇数，与任何图中必须有偶数个节点度数为奇数矛盾。（2） 存在，因为恰有 2 个数位奇数，图 8-2 的度数序列为 4，4，3，3，2，2，2，2。图 8-210.设无向图 G 有 10 条边，3 度和 4 度节点各 2 个，其余节点的度数均小于 3，则 G 至少有多少个节点？在最少节点的情况下，求
7、出 G 的度数序列、最大度(G)和最小度(G)。解：由于 3 度和 4 度节点各 2 个，而图 G 的边数为 10，根据握手定理知，其余节点度数之和为2 10 (3 2 4 2) 6，这时 G 至少还有 3 个节点，进而 G 至少有 2+2+3=7 个节点， 在这种情况下 G 的度数序列为4， 4， 3， 3， 2， 2， 2， 最大度(G)=4和最小度(G)=2。11. 画出 K3的所有不同构的非空子图。解K3的所有不同构的子图有 7 个，分别如图 8-3 所示。图 8-312. 画出所有不同构的(5，3)简单无向图及其补图。解：(5，3)简单无向图的度数分序列分别为： （a）3，1，1，1
8、，0； （b）2，2，2，0，0； （c）2，2，1，1，0； （d）2，1，1，1，1；于是所有不同构的(5，3)简单无向图分别入图 8-4 所示。(a)(b)(c)(d)图 8-4对应的补图分别如图 8-5 所示。(a)(b)(c)(d)图 8-513. 证明：在 K4的所有不同构的生成子图中，有 3 个具有 3 条边。证：(4，3)简单图的度数序列分别为： （1）3，1，1，1； （2）2，2，2，0； （3）2，2，1，1；很容易知道，对应于每个度数序列只有唯一的一个 K4的不同构的生成子图。14. 说明图 8.6(a)和图 8.6(b)两个无向图不同构。(a)(b)图 8.6解：观察
9、图8.6（a）和图8.6（b）中两个无向图的度为 3 的节点，与其邻接的节点都有 3 个，这 3 个节点在图 8.6（a）所示的图中只有 1 个节点度数为 2，但在图 8.6（b）所示的图中有 2 个节点度数为 2，所以图 8.6（a）和图 8.6（b）所示的图不同构。15. 说明图 8.50 中四个有向图彼此不同构。图 8.7解 在图 8.7（a）中有 3 个节点的出度均为 1，1 个节点出度为 0；在8.7（b）中有 1 个节点的出度为 1， 1 个节点的出度为 2 而入度为 1， 2 个节点的出度为 0；在 8.7（c）中有 1 个节点的出度为 1，1 个节点的出度为 2 但该节点入度为
10、 0，2个节点的出度为 0；在图在8.7（d）中有3 个节点的出度为 0，于是，图8.7 中 4个有向图彼此不同构。16. 若一个简单无向图 G 与其补图G同构，则称 G 为自补图。(1) 试画出所有不同构的 5 阶自补图。(2) 若 G 是 n 阶自补图，则 Kn的边数为偶数。(3) 若 G 是 n(n 2)阶自补图，则存在正整数 k 使得 n=4k 或 n=4k+1(4) 是否存在 6 阶自补图？证 （1）所有不同构的 5 阶自补图有如图 8.8 所示的两个。图 8.8（2）设 G 是 n 阶自补图，边数为 m，则其补图G的边数也为 m，因为 G 的边数与G的边数之和等于 Kn的边数，即
11、Kn的边数为 m+m=2m，因此 Kn的边数为偶数。（3）由（2）知，n(n-1)/2=2m，即 n(n-1) =4m。由于（n，n-1）=1，所以 n 为 4 的倍数：n=4k 或 n-1 为 4 的倍数，n-1=4k，即 n=4k+1。（4）由于 K6的边数为 6(6-1)/2=15 是奇数，由（2）知，不存在 6 阶自补图。17. 对于完全无向图 Kn，(1) 共有多少个圈？(2) 包含某条边的圈有多少个？(3) 任意两个不同节点间有多少条路径？解 （1）在 Kn中，任意圈的长度 L 均满足 3Ln。对于长度为 L 的圈，有 L 个节点。从 n 个节点任取 L 个节点有CnL种选取方式。
12、对于任意的长度为 L 的圈，它有 L个节点。 由于任意两个节点都是邻接的， 所以在这种情况下， 圈是从第一个节点 （与其关联的边有 L-1 条）到第二个节点（与其关联的边有L-2 条） ，一直下去，但注意到，每个圈重复了一次，于是这样的圈有(L-1)!/2。因此 Kn中共有LnCnL(L 1)!/ 2个圈。3(2)对于包含边 e 的圈，已经有两个节点，那就是e 的两个端点。从Kn的其余 n-2 个i节点任取 i 个节点，可以得到长度为 i+2 的圈，有Cn2（1in-2）种取法。考虑从e 的其中一个端点 u 出发最后通过 e 返回到 u 的圈， 在端点 u 处除 e 外还有 i 条边与u 关联
13、， 当从 u 出发达到第二个节点是， 虽然第二个节点本身有 i+1 个节点与之关联，但只有通过其中 i-1 条边中某条才能最终通过 e 返回到 u，一直下去，这样的圈有i！i个，所以包含某条边的圈有Cn2i!个。i1n2（3）与（2）类似，对于任意两个不同节点 u 到 v，从 u 到 v 的路径若与u，v形i成圈，则有Cn2i!条；否则只有直接从 u 到 v 一条路径。故从 u 到 v 共有i1n2n2iCni2i!1条路径。118. 在图 8.9 中，求节点 A 到节点 F 的：(1)所有路径；(2)所有轨迹；(3)距离。ABCv1v4v2DEFv3图 8.9图 8.10解 （1）节点 A
14、到节点 F 的所有路径分别为：ABCF；ABCEF；ABEF；ABECF；ADEF；ADECF；ADEBCF。（2）节点 A 到节点 F 的所有轨迹分别为：ABCF；ABCEF；ABEF；ABECF；ADEF；ADECF；ADEBCF；ADEBCEF。(3) d（A，F）=319. 在图 8.10 中，求(1)v1到 v4长度分别为 1，2，3 的路分别有哪些？(2)v1 到 v1 长度分别为 1，2，3 的回路分别有哪些？(3)长度为 3 的路共有多少条？其中多少条回路？解 （1）v1到 v4长度分别为 1 和 2 的路：没有。v1到 v4长度为 3 的路一条：v1 v2 v3 v4。（2）
15、v1到 v1长度分别为 1 回路有一条：v1 v1；v1到 v1长度分别为 2 的回路一条 v1 v1 v1；v1到 v1长度分别为 3 的回路两条：v1 v1 v1 v1，v1 v2 v3 v1。（3）长度为 3 的路共有 30 条，分别是 v1到 v1有 2 条，v1到 v2有 2 条，v1到 v3有 1 条，v1到 v4有 1 条，v2到 v1有 2 条，v2到 v2有 1 条，v2到 v3有 2 条，v3到 v1有 4 条，v3到 v2有 4 条，v3到 v3有 1 条，v3到 v4有 2 条，v4到 v1有 3条，v4到 v2有 2 条，v4到 v3有 3 条。长度为 3 的回路共有
16、 4 条，分别是v1到 v1有 2 条，v2到 v2有 1 条，v3到 v3有 1 条。20. 若无向图 G 的任意两个节点之间都存在一条路，则 G 中任意两条最长轨迹存在公共节点。证 显然，在同一个图 G 中任意两条最长轨迹的长度是相同的。若图 G 存在两条最长轨迹 L1：u0u1un和 L2：v0v1vn没有公共节点。因为 G 的任意两个节点之间都存在一套路，必村子一条最短路径从 L1中节点 ui到 L2中节点 vj。(1)若 ij，则轨迹 L：v0v1vj-1vjuiui+1un的长度大于 n。（2）若 ij，则轨迹 L：u0u1uj-1ujvivi+1vn长度大于 n。由（1）和（2）
17、知，连通无向图的任意两条最长轨迹存在公共节点。21. 设 G = (V，E)是连通无向图，则(1)去掉 G 中任意简单回路 C 上一条边 e 得到的图 Ge 连通。(2)去掉度数为 1 的节点 v 得到的图 Gv 连通。证 （1）设与边e 关联的节点为 u 和 v，由于e 是简单回路 C 上的一条边，在图G-e中，u 和 v 是可达的。由于 G 是连通图，于是对于任意的 G-e 中的两个节点均是可达的，因此 G-e 连通图。（2）在图 G-v 中，对于任意节点 v1和 v2，由于 G 是连通图且 deg(v)=1，显然 v1和v2在 G-v 中是可达的，因此 G-v 是连通图。22. 设 G
18、是 n(n 2)阶简单无向图，若(G) n/ 2，则 G 是连通图。证 （反证）假设 G 不连通，则 G 可以分解称两个不连通的子图 G1和 G2，其阶数分别为 n1和 n2（n1，n21 且 n1+n2=n） 。因为G 是简单图，于是G1和 G2是简单图，进而对于 G1中的任意节点 u 和 G2中的任意节点 v 有deg(u)n1-1，deg(v)n2-1于是deg(u)+ deg(v) n1+ n2-2=n-2。 根据已知条件 deg(u)n/2， 因此deg(u)+ deg(v)n/2+ n/2=n，矛盾。另证若 G 不连通，则G 的连通分支数 w(G)2。任取G 的 2 个连通分支 C
19、1和C2，分别在 C1和 C2中取节点 u 和 v，则 C1至少有 1+deg(u)个节点，C2至少有1+deg(v)个节点，于是 G 至少有(1+deg(u)+( 1+deg(v)2+2(G)2+n 个节点，矛盾。23. 对于简单连通无向图 G = (V， E)， 若 G 不是完全图， 则存在 3 个节点u,v,wV使得u,v E且v,w E但u,w E。证：由于 G 不是完全图，必存在u,wV使得u,w E。又由于 G 是连通的，u 可达 w，即 u 到 w 存在一条路 L：uv0w。对 L 的长度l归纳。若l=2，即 L：uvw，结论成立。假设l=k 时结论成立，当l=k+1 时，分两种
20、情况讨论：（1）v0与 w 邻接，令 v= v0结论成立。（2）v0与 w 不邻接，由于v0与 w 存在一条长度为 k 的路 L u，v0，取u=v0，根据归纳假设知结论成立。24. 分别求出 n 阶完全无向图 Kn的点连通度和边连通度。解 显然， 使得 Kn不连通或是 1 阶图， 至少要删除 n-1 个节点， 于是有(Kn) n 1。由于(Kn) n 1，使得Kn不连通或是平凡图，至少要删除 n-1 条边，于是(KN) n 1。所以，(Kn) (Kn) n 125. 设 G = (V，E)是非平凡有向图，若对于任意WV，G 中起点在 W，终点在 VW 的边至少 k 条，则称有向图 G 的边连
21、通度至少为 k。证明：非平凡有向图 G 是强连通图的充要条件是 G 的边连通度至少为 1。证 （） （反证）若存在WV，而不存在 G 中起点在 W，终点在 V-W的边，显然W 中节点不可达 V-W中节点，这与 G 是强连通图条件矛盾。（）对于任意u,vV，由于 G 的边连通度至少为 1，因此 u 到 Vu中节点 u1有边，即(u,u1)E。对于W u,u1，必存在节点u2VW使得(u,u2) E或者(u1,u2)E，于是总存在 u 到 u2的路，继续这个过程，一定存在u 到 v 的路。由于u,vV的任意性知，G 是强连通图。0026. 已知有向图 G 的邻接矩阵为A00210010，画出图 G
22、 的图形。011001解图 G 的图形如图 8.11 所示1127. 已知无向图 G 的关联矩阵为M 000解图 G 的图形如图 8.12 所示100111100001101，画出图 G 的图形。0011000000图 8.11图 8.1228. 求出图 8.13 所示的无向图 G1及有向图 G2的关联矩阵。e1v1v2e6e3e2e1v1v2e4v4e4v4e3e2e5v3(a) G1(b) G2图 8.13e5v302解 （a）G1的关联矩阵为M(G1) 000010111000。1101100110 10010 11 100。（b ）G2的关联矩阵为M(G2) 0 1101000 1 1
23、29. 画出分别满足以下条件的欧拉图(n，m)。(1) n 和 m 的奇偶性相同。(2) n 和 m 的奇偶性相反。解（1）满足条件（1）的欧拉图（n,m）如图 8.14 所示。 (a) n,m 为奇数 (b) n,m 为偶数图 8.14（2）满足条件（2）的欧拉图（n,m）如图 8.15 所示。(a) n 为奇数,m 为偶数 (b) n 为偶数,m 为奇数图 8.1530. 证明：n 阶完全无向图 Kn是欧拉图当且仅当 n 为奇数。证 n 阶完全无向图 Kn是连通图且每个节点的度数均为 n-1，于是 Kn是欧拉图当且仅当 n-1 是偶数，即 n 为奇数。31. 证明：若一个无向图 G = (
24、V，E)存在一个节点vV使得 deg(v)=1，则 G 不是哈密尔顿图。证 因为图 G 的哈密尔顿回路要经过节点 v， 这是显然 deg(v)2， 故 G 不是哈密尔顿图。32. 回答下列问题：(1) 彼得森图不是哈密尔顿图吗？说明理由。(2) 可以通过加边使彼得森图称为哈密尔顿图吗？若可以，试画出添加后的图的图形。(3) 若只能添加原彼得森的一些边的多重边，能是其成为哈密尔顿图吗？(4) 删除彼得森图的一个节点后所得到的图是否是哈密尔顿图？解 （1） 由于彼得森图是有 10 个节点、15 条边的图，若存在哈密尔顿回路C，则 C 中恰含 10 条边，即有5 条边不在 C 中，又由于彼得森图是3
25、正则图，因而与同一个节点关联的 3 条边中恰有一条边不在 C 中。 Petersen (a) (b)图 8.16在节点 a 处，只需分别考虑 ab 和 af 不在 C 中的情况，如图 8.16 所示在图 8.16（a）中，有 ae，fa 和 gb，bc 都在 C 中。若 jh 不在 C 中，则ej，jg，ch，hf 都位于 C 中，于是得到一条圈aejbchfa，进而不存在哈密尔顿回路 C。若 jh 在 C 中，则 hc 和 hf 有一条边不在 C 中。若 hc 不在 C 中，则 cd 和 hf在 C 中，进而fi 不在 C 中。于是di,ig 在 C 中，因而得到一个圈bcdigb，所以不存
26、在哈密尔顿回路 C。若 hf 不在 C 中，hc,fi 在 C 中，由于bc,hc 在 C 中，因而 cd 不在 C 中，进而 id,de 在 C 中，于是得到一个圈 afidea,因而不存在哈密尔顿回路 C。类似地，可以对图 8.16（b）进行讨论之，不存在哈密尔顿回路 C。图 8.17(a)(b)图 8.18（2）在彼得森图中（见图8.17） ，添加节点a 与 j 之间的一条边，得到一个哈密尔顿图，其哈密尔顿回路为 aedcbgifhja。（3）显然，仅添加多重边不会影响图的哈密尔顿性，所以仅添加原彼得森图的一些边的多重边，不能使其成为哈密尔顿图。（4）由于彼得森图的对称性，只需考虑删除节
27、点 a（见图 8.18（a） ）和删除节点 f（见图 8.18（b） ）的情况。在图 8.18（a）中 ejhfigbcde 是其哈密尔顿回路，在（b）中，aejhcdigba 是其哈密尔顿回路。33. 分别画出满足下列条件的无向图。(1) 既是欧拉图又是哈密尔顿图。(2) 是欧拉图，不是哈密尔顿图。(3) 不是欧拉图，是哈密尔顿图。(4) 既不是欧拉图又不是哈密尔顿图。解 （1）和（2）分别见图 8.19(a)和(b)， （3）和（4）分别见图 8.19(c)和(d)。(a)(b)(c)(d)图 8.1934. 一只小蚂蚁可否从立方体的一个顶点出发，沿着棱爬行，它爬过每一个顶点一次且仅一次，
28、最后回到原出发点？是利用图作解释。解 可以将立方体投影在平面上得到图 8.20 所示的图，显然在该图中 123456781 是一条哈密尔顿回路。图 8.2035. 有 n(n 4)人，若任意两个人合起来认识其余 n-2 个人，则他们可以站成一个圈，使得每个人的两旁都站着他的朋友。证：设这 n 个人分别是 v1，v2，vn，将其作为节点集 V。若两人认识，则在相应的节点之间画一条无向边，于是得到一个简单无向图 G 且满足条件：对于任意 u，vV，有 deg(u)+deg(v)n-2。对于任意不相邻的节点 u，vV，考虑任意节点 wVu，v。根据已知条件，u与 w 或 v 与 w 邻接。又因为u
29、与 v 不邻接，因此u 与 w 且 v 与 w 邻接。根据w 的任意性有 deg(u)，deg(v)n-2，于是 deg(u)+deg(v)2（n-2） 。由于 n4，所以 2（n-2）n，于是 deg(u)+deg(v)n。根据教材中定理 8.16 知，G 是哈密尔顿图。36. 证明：K5和 K3，3都是极小非平面图。证 首先 K5和 K3，3都不是平面图。（1）对于 K5，任意去掉一条对角线所在边 e 所得到的图 K5e 和去掉非对角线所在边 e 所得到的图 K5e 都是平面图，其平面表示分别见图 8.21(a)和图 8.21(b)，因此K5是极小非平面图。（2）对于 K3，3，任意去掉一
30、条边 e 所得到的图 K3，3e 是平面图，其平面表示见图8.21(c)，因此 K3，3都是极小平面图。(a) K5e(b) K5e(c) K3，3e图 8.2137. 设 G 是 n(n 3)阶极大平面图，试证明：(1) G 是连通图。(2) G 的每个面都是三角形。证 （1）若G 不是连通图，则G 至少有两个连通分支。设C1和 C2是 G 的两个连通分支， 在 C1和 C2中各取一个节点 u 和 v， 于是在 G 添加一条边 uv 所得到的图 G+uv仍是平面图，这与 G 是极大平面图相矛盾，于是 G 是连通图。（2）由于极大平面图是简单图，于是 G 的每个面至少 3 条边围成，假设存在
31、G 的1 个面 R 至少由 4 条边围成， 其面的边界为 v1v2v3v4v1。 若 v1与 v3在 G 中不邻接，则在 R 内添加边 v1v3，所得到的图仍为平面图，与已知矛盾。于是 v1与 v3在 G 中邻接且边 v1v3在 R 的外部。同样v2与 v4在 G 中也邻接且边 v2v4也在 R 的外部。因此得到两条边 v1v3和 v2v4，它们相较于 R 的外部，这与 G 是平面图相矛盾，故 G的每个面都是三角形。38. 证明：最小度(G) 3的简单连通平面图 G 的边数不可能为 7。证 (反证)设 G 是(n，m)图，这里 m=7，根据推论 1 知，m3n-6，即 73n-6，于是3n13
32、。根据握手定理，有2 7 deg(v) 3n，即 3n14。这是一个矛盾。v39. 若(n，m)平面图的每个面至少由 k(k3)条边围成，则mk(n 2)/(k 2)。证 由于 G 是连通图，根据欧拉公式，G 的面数为 m-n+2。因为每个面至少由 k 条边围成， 但每一条边是两个面的边界， 于是 k(m-n+2)/2m， 所以mk(n 2)/(k 2)。40. 分别画出图 8.22(a)与图 8.22(b)的对偶图。(a) G1(b)G2图 8.22解图 8.22 的对偶图见图 8.23 的虚线部分所画的图。(a) G1*(b)G2*图 8.23(G) k，则 G 至少有 k(k1)/2 条
33、边。41. 设图 G 的节点着色数(G) k，设 0 图 G 用 1，2，k 种颜色对节点着色，且分别涂上这 k 种证 由于颜色的节点集合分别为 V1，V2，Vk，则对于任意 ij，Vi与 Vj之间至少存在一(G) k矛盾。于是 G条边，否则可以给 Vi和 Vj的节点涂色同一种颜色，这与已知至少有 k(k1)/2 条边。42. 证明：任意 9 个人中，有 3 个人相互认识或 4 个人相互不认识。证 在完全无向图 K9中，其节点代表人，若两个人认识则在相应的两节节点所连的边上涂上红色，否则涂上蓝色。于是问题转化为，若仅用红、蓝对 K9的边涂色，则任意的一种涂色方案，都存在一个边是红色的 K3或边
34、是蓝色的 K4。任取一个节点 v，由于与 v 关联的边有 8 条，当用红、蓝两种颜色去涂时，任意的一种涂色方案，都至少有 4 条边涂的红色或至少有 4 条边涂的蓝色。不妨设至少 4 条边涂的是红色，设与这 4 条边关联的另外 4 个节点分别为 v1，v2，v3和 v4。若 v1，v2，v3和 v4所构成的 K4中存在 1 条边涂的是红色，如 v1v2，则三角形 v v1v2是红色的 K3。 若 K4中任意两条边都涂的是蓝色， 则出现一个边是蓝色的 K4。第 9 章 习题参考答案1.分别画出所有不同构的五阶无向树和六阶无向树。解 根据性质 1,5 阶无向树恰有 4 条边，由握手定理知，其所有节点
35、度数之和为24=8。根据性质 2,5 阶无向树 G 至少两片叶。若 G 恰有两片叶，则其度数序列为 2,2,2,1,1，此时为图 9.1(a)所示。若 G 恰有3 片叶，则其度数序列为 3,2,1,1,1，此时为图 9.1(b)所示。若 G 恰有 4 片叶，则其度数序列为 4,1,1,1,1，此时为图 9.1(c)所示。因此，所有不同构的 5 阶无向树共 3 棵，如图 9.1 所示。 (a) (b) (c)图 9.1类似，6 阶无向树恰有 5 条边，其所有节点度数之和为 25=10。6 阶无向树 G至少片叶。若 G 恰有 2 片叶，则其度数序列为 2,2,2,2,1,1，此时为图 9.2(a)
36、所示。若 G恰有 3 片叶，则其度数序列为3,2,2,1,1,1，此时为图9.2(b)和图 9.2(c)所示。若G恰有4片叶， 则其度数序列为4,2,1,1,1,1， 或3,3,1,1,1,1， 此时为图9.2(d)和图 9.2(e)所示。若 G 恰有 5 片叶，则其度数序列为 5,1,1,1,1,1，此时为图9.2(f)所示。因此，所有不同构的 6 阶无向树共 6 棵，见图 9.2。 (a) (b) (c) (d) (e)（f）图 9.22.设 G 是一棵无向树且具有 2 个 4 度节点，3 个 3 度节点，其余均为叶节点。(1) 求出该无向树共有多少个节点？(2) 画出两棵不同构的满足上述
37、要求的无向树。解 （1） 设该无向树 G 有 x 个也节点，于是 G 共有 2+3+x=x+5 个节点。根据无向树性质知，G 有 x+4 条边，由握手定理有24+33+x=2(x+4)于是 x=9，进而 G 由 9+5=14 个节点。（2）图 9.3 所示的是两个不同构的满足上述要求的无向树。(a)(b)图 9.33. 证明：连通无向图 G 是无向树的充要条件是 G 的每一条边都是桥。证（）若图 G 存在一条边 e=u,v不是桥，则 Ge 仍连通，因而节点 u 和v 之间必存在一条不经过 e 的路径，进而 G 中存在圈，这与无向树的定义矛盾。（）若 G 中存在圈，则圈上的任何边都不是桥，这与已
38、知矛盾。于是，G 中不含有圈，由于 G 是连通的，故 G 是无向树。4证明：恰有两片树叶的无向树是一条路径。证 设 G 是 n 阶无向树，它恰有两片树叶，于是其余 n-2 个节点 v1，v2，vn-2中的每一个节点至少为 2 度，根据握手定理，有2 (n 1) 2 deg(vi)i1n因此对于任意 i(i=1，2，n-2)，有 deg(vi)=2。这时，G 中存在一条从一个叶节点到另一个叶节点的欧拉轨迹，且该轨迹是一条路径。5. 如图 9.4 所示的两个图，分别画出所有不同构的生成树。(a)(b)图 9.4解 （1）对于图9.4(a)所示的图，其所有不同构的生成树有3 棵，如图9.5 所示。(
39、a)(b)(c)图 9.5（2）对于图 9.4(b)所示的图，其所有不同构的生成树有 2 棵，如图 9.6 所示。(a)(b)图 9.66. 证明：在根树中，从树根到任意节点有且仅有唯一的一条路径。证 当 k=0，1 时，结论显然成立。假设对层数 k-1 的节点结论成立，对于层数 k的任意节点 v，由于节点 v 的入度为 1，因此存在唯一的一个节点 u 使得 u 与 v邻接，这时节点 u 所在的层数为 k-1。根据归纳假设，存在唯一的一条从根节点到 u 的路径，进而只有唯一的一条从树根到节点 v 的路径。7. 画出所有不同构的 4 阶根树及 5 阶根树。解 （1） 所有不同构的 4 阶根树有
40、4 棵，如图 9.7 所示。(a)(b)(c)(d)图 9.7（2） 所有不同构的 5 阶根树有 9 棵，如图 9.8 所示。(a)(b)(c)(d)(e)(f)(g)(h)(i)图 9.88指出图 9.9 中的根树 T 的以下节点。(1) 根节点；(2) 树叶节点；(3) 分支节点；(4) 内点；(5) 每个节点的层；(6) 每个节点的父节点；(7) 每个节点的子节点；(8) 树高；(9) 最大出度；(10) 所有子(根)树。ABCDEFKLM图 9.9解 （1） 根节点为 A。（2）树叶节点分别为 K，L，F，G，M，I，J。（3）分支节点分别为 A，B，C，D，E，H。（4）内点分贝为
41、B，C，D，E，H。（5）第 0 层节点为 A；第 1 层节点有 B，C，D；第 2 层节点有 E，F，G，H，I，J；第 3 层节点有 K，L，M。（6）节点 A 无父节点；节点 B，C，D 的父节点为 A；节点 E，F 的父节点为B；节点 G 的父节点为 C；节点 H，I，J 的父节点为 D；节点 K，L 的父节点为 E；节点 M 的父节点为 H。（7）节点 A 的子节点为 B，C，D；节点 B 的子节点为 E，F；节点 C 的子节点为 G；节点 D 的子节点为 H，I，J；节点 E 的子节点为 K，L；节点 H 的子节点为 M；叶节点 K，L，F，G，M，I，J 均无子节点。（8）树高为
42、 3。（9）最大出度为 3。（10）所有子（根）树分别为：根树本身， TB，E，F，K，L，TC，G，TD，H，I，J，M，TE， K，L，TH，M，平凡子树分别为 K，L，F，G，M，I，J。9. 如图 9.10 所示，存在是根树的生成子图吗？若存在，求出所有不同构的是根树的生成子图。GHIJ图 9.10解： （1）不同构的是根树的生成子图只有 1 棵，见图 9.11 所示（未画出根树的方向） 。（2） 不同构的是根树的生成子图只有 3 棵， 见图 9.12 所示 （未画出根树的方向） 。图 9.11（a）（b）（c）图 9.1210. 证明以下结论：(1) 完全二叉树的节点个数必为奇数；(
43、2)n 阶完全二叉树的树叶的数目为(n+1)/2。证 （1）由性质 6 知结论成立。（2）根据性质 6，有 L 片树叶的完全二叉树有 2L-1 个节点，于是 n=2L-1 进而树叶的数目为 L=(n+1)/2。11计算有 13 片树叶，分别赋权 2，3，5，7，11，13，17，19，23，29，31，37，41 的哈夫曼树。解 对于 2，3，5，7，11，13，17，19，23，29，31，37，41，先组合两个最小的权 2+3=5，得 5，5，7，11，13，17，19，23，29，31，37，41；在所得到的序列中再组合 5+5=10，重新排列后为 10，7，11，13，17，19，23
44、，29，31，37，41；再组合 10+7=17，得 17，11，13，17，19，23，29，31，37，41；继续下去，最后组合 95+143=238。23555107771717111111111313131324242417171717173434341919191919192323232323234242424229292929292929535353959531313131313131316565653737373737373737374141414141414141417878143238所求的哈夫曼树如图 9.13 所示。图 9.1312. 在下面给出的 3 个符号串集合中，哪
45、些是前缀码？哪些不是前缀码？若是前缀码，则构造定位二叉树，其树叶代表其二进制编码。若不是前缀码，则说明理由。(1) A1=0，10，110，1111。(2) A2=1，01，001，0000。(3) A3=1，11，101，001，0011。解 显然 A1和 A2的各符号串互不为前缀，因此 A1和 A2是前缀码。在 A3中 1 既是 11 的前缀，又是 101 的前缀，所以 A3不是前缀码。由 A1和 A2所构造的定位 2 叉树分别见图 9.14 的(a)和(b)。(a)(b)图 9.1413在通信中，八进制数字0，1，2，3，4，5，6，7 出现的频率分别为 0：30%，1：20%，2：15
46、%，3：10%，4：10%，5：6%，6：5%，7：4%。编写一个传输它们的最佳前缀码，使通信中出现的二进制数字尽可能地少。具体要求如下：(1) 画出相应的哈夫曼树。(2) 写出每个数字对应的前缀码。(3) 传输上述比例出现的数字 10000 个时，至少要用多少个二进制数字？解应该用较短的符号串传输出现频率较高的数字， 可以用各数字出现的频率作为 2 叉树的树叶的权，求得最优 2 叉树（哈夫曼树） ，然后用这样的 2 叉树产生的前缀码去传输上面的数字。（1）将各数字出现的频率按从小到大的顺序排列为0.04，0.05，0.06，0.1，0.1，0.15，0.2，0.3。于是根据哈夫曼算法得到的哈夫曼树见图 9.15。（2）根据哈夫曼树可得出前缀码为 0：01；1：11；2：001；3：100；4：101；5：0001；6：00000；7：00001；（3）由（1）知，最优 2 叉树的权为0.32+0.22+0.153+0.32+0.13+0.13+0.064+0.055+0.044=2.74所以，传输10000 个按上述比例出现的数字时，至少要用2.7410000=27400 个二进制数字。图 9.1514将图 9.16 所示的森林 F 转换成定位二叉树 B。AEGBCDFHIJ图 9.16解 按自然转换规则得到的定位二叉树 B 见图 9.17。图 9.17