离散数学第8,9章课后习题答案

第8章习题参考答案1.在一次10周年同学聚会上，想统计所有人握手的次数之和，应该如何建立该问题的图论模型？解：将每个同学分别作为一个节点，如果两个人握过一次手就在相应的两个节点之间画一条无向边，于是得到一个无向图。一个人握手的次数就是这个节点与其他节点所连接的边的条数，进而可得出所有人握手的次数之和。2.在一个地方有3户人家，并且有3口井供他们使用。由于土质和气候的关系，有些井中的水常常干枯，因此各户人家要到有水的井去打水。不久，这3户人家成了冤家，于是决定各自修一条路通往水井，打算使得他们在去水井的路上不会相遇。试建立解决此问题的图论模型。解：将3户人家分别看做3个节点且将3口井分别看做另外3个节点，若1户人家与1口井之间有一条路，则在该户人家与该口井对应的节点之间连一条无向边，这样就得到一个无向图。3.某人挑一担菜并带一条狼和一只羊要从河的一岸到对岸去。由于船太小，只能带狼、菜、羊中的一种过河。由于明显的原因，当人不在场时，狼要吃羊，羊要吃菜。通过建立图论模型给出问题答案。解：不妨认为从北岸到南岸，则在北岸可能出现的状态为24=16种，其中安全状态有下面10种：（人，狼，羊，菜），（人，狼，羊），（人，狼，菜），（人，羊，菜），（Φ），（人，羊），（菜），（羊），（狼），（狼，菜）；不安全的状态有下面6种：（人）（人，菜）（人，狼）（狼，羊，菜）（狼，羊）（羊，菜）。线将北岸的10种安全状态看做10个节点，而渡河的过程则是状态之间的转移，这样就得到一个无向图，如图8-1所示。 图8-1从上述无向图可以得出安全的渡河有两种：第1种：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（狼）→（人，狼，羊）→（羊）→（人，羊）→（Φ）。第2中：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（菜）→（人，羊，菜）→（羊）→（人，羊）→（Φ）。4.证明：任何n阶完全图Kn的边数为n(n-1)/2。证n阶简单图的边数为。5.对于n阶简单无向图G，若其边数为m，试计算G的补图的边数。解：由于G的边数与其补图的边数之和为n阶完全图Kn的边数为n(n-1)/2，因此的边数为n(n-1)/2-m。6.证明：对于任意n阶简单图G有。证：根据简单图的定义，当一个节点与其余所有节点均邻接时，其度数达到最大，于是对于任意n阶简单图G有。7.无向图G有6条边，各有一个3度和5度节点，其余均为2度节点，求G的阶数。解设图G有x个节点度数为2，则G的阶数为x+1+1=x+2。根据握手定理有：于是x=2，进而G的阶数为2+2=4。8.将有向图G的边的方向去掉得到的无向图称为G的基础图，基础图是完全图的有向图称为竞赛图。证明：任意竞赛图的所有节点的出度平方和等于入度平方和。证设G=（V，E）是n阶竞赛图，则其边数为且对于任意有根据竞赛图的定义知，于是，====9.是否存在一个无向图，其度数序列分别为(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至少有多少个节点？在最少节点的情况下，求出G的度数序列、最大度和最小度。解：由于3度和4度节点各2个，而图G的边数为10，根据握手定理知，其余节点度数之和为，这时G至少还有3个节点，进而G至少有2+2+3=7个节点，在这种情况下G的度数序列为4，4，3，3，2，2，2，最大度=4和最小度=2。11.画出K3的所有不同构的非空子图。解K3的所有不同构的子图有7个，分别如图8-3所示。图8-312.画出所有不同构的(5，3)简单无向图及其补图。解：(5，3)简单无向图的度数分序列分别为：（a）3，1，1，1，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解：观察图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但该节点入度为0，2个节点的出度为0；在图在8.7（d）中有3个节点的出度为0，于是，图8.7中4个有向图彼此不同构。16.若一个简单无向图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，则其补图的边数也为m，因为G的边数与的边数之和等于Kn的边数，即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均满足3≤L≤n。对于长度为L的圈，有L个节点。从n个节点任取L个节点有种选取方式。对于任意的长度为L的圈，它有L个节点。由于任意两个节点都是邻接的，所以在这种情况下，圈是从第一个节点（与其关联的边有L-1条）到第二个节点（与其关联的边有L-2条），一直下去，但注意到，每个圈重复了一次，于是这样的圈有(L-1)!/2。因此Kn中共有个圈。(2)对于包含边e的圈，已经有两个节点，那就是e的两个端点。从Kn的其余n-2个节点任取i个节点，可以得到长度为i+2的圈，有（1≤i≤n-2）种取法。考虑从e的其中一个端点u出发最后通过e返回到u的圈，在端点u处除e外还有i条边与u关联，当从u出发达到第二个节点是，虽然第二个节点本身有i+1个节点与之关联，但只有通过其中i-1条边中某条才能最终通过e返回到u，一直下去，这样的圈有i！个，所以包含某条边的圈有个。（3）与（2）类似，对于任意两个不同节点u到v，从u到v的路径若与{u，v}形成圈，则有条；否则只有直接从u到v一条路径。故从u到v共有条路径。18.在图8.9中，求节点A到节点F的：(1)所有路径；(2)所有轨迹；(3)距离。图8.9图8.10解（1）节点A到节点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的路一条：v1v2v3v4。（2）v1到v1长度分别为1回路有一条：v1v1；v1到v1长度分别为2的回路一条v1v1v1；v1到v1长度分别为3的回路两条：v1v1v1v1，v1v2v3v1。（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的回路共有4条，分别是v1到v1有2条，v2到v2有1条，v3到v3有1条。20.若无向图G的任意两个节点之间都存在一条路，则G中任意两条最长轨迹存在公共节点。证显然，在同一个图G中任意两条最长轨迹的长度是相同的。若图G存在两条最长轨迹L1：u0u1…un和L2：v0v1…vn没有公共节点。因为G的任意两个节点之间都存在一套路，必村子一条最短路径从L1中节点ui到L2中节点vj。(1)若i≤j，则轨迹L：v0v1…vj-1vj…uiui+1…un的长度大于n。（2）若i>j，则轨迹L：u0u1…uj-1uj…vivi+1…vn长度大于n。由（1）和（2）知，连通无向图的任意两条最长轨迹存在公共节点。21.设G=(V，E)是连通无向图，则(1)去掉G中任意简单回路C上一条边e得到的图G－e连通。(2)去掉度数为1的节点v得到的图G－v连通。证（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是n(n(2)阶简单无向图，若，则G是连通图。证（反证）假设G不连通，则G可以分解称两个不连通的子图G1和G2，其阶数分别为n1和n2（n1，n2≥1且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个连通分支C1和C2，分别在C1和C2中取节点u和v，则C1至少有1+deg(u)个节点，C2至少有1+deg(v)个节点，于是G至少有(1+deg(u))+(1+deg(v))≥2+2≥2+n个节点，矛盾。23.对于简单连通无向图G=(V，E)，若G不是完全图，则存在3个节点使得且但。证：由于G不是完全图，必存在使得。又由于G是连通的，u可达w，即u到w存在一条路L：uv0…w。对L的长度归纳。若=2，即L：uv…w，结论成立。假设=k时结论成立，当=k+1时，分两种情况讨论：（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条边，于是。所以，25.设G=(V，E)是非平凡有向图，若对于任意，G中起点在W，终点在V－W的边至少k条，则称有向图G的边连通度至少为k。证明：非平凡有向图G是强连通图的充要条件是G的边连通度至少为1。证（）（反证）若存在，而不存在G中起点在W，终点在V-W的边，显然W中节点不可达V-W中节点，这与G是强连通图条件矛盾。（）对于任意，由于G的边连通度至少为1，因此u到V—{u}中节点u1有边，即。对于，必存在节点使得或者，于是总存在u到u2的路，继续这个过程，一定存在u到v的路。由于的任意性知，G是强连通图。26.已知有向图G的邻接矩阵为，画出图G的图形。解图G的图形如图8.11所示27.已知无向图G的关联矩阵为，画出图G的图形。解图G的图形如图8.12所示图8.11图8.1228.求出图8.13所示的无向图G1及有向图G2的关联矩阵。(a)G1(b)G2图8.13解（a）G1的关联矩阵为。（b）G2的关联矩阵为。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=(V，E)存在一个节点使得deg(v)=1，则G不是哈密尔顿图。证因为图G的哈密尔顿回路要经过节点v，这是显然deg(v)≥2，故G不是哈密尔顿图。32.回答下列问题：(1)彼得森图不是哈密尔顿图吗？说明理由。(2)可以通过加边使彼得森图称为哈密尔顿图吗？若可以，试画出添加后的图的图形。(3)若只能添加原彼得森的一些边的多重边，能是其成为哈密尔顿图吗？(4)删除彼得森图的一个节点后所得到的图是否是哈密尔顿图？解（1）由于彼得森图是有10个节点、15条边的图，若存在哈密尔顿回路C，则C中恰含10条边，即有5条边不在C中，又由于彼得森图是3—正则图，因而与同一个节点关联的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，所以不存在哈密尔顿回路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）由于彼得森图的对称性，只需考虑删除节点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.一只小蚂蚁可否从立方体的一个顶点出发，沿着棱爬行，它爬过每一个顶点一次且仅一次，最后回到原出发点？是利用图作解释。解可以将立方体投影在平面上得到图8.20所示的图，显然在该图中123456781是一条哈密尔顿回路。图8.2035.有n(n(4)人，若任意两个人合起来认识其余n-2个人，则他们可以站成一个圈，使得每个人的两旁都站着他的朋友。证：设这n个人分别是v1，v2，…，vn，将其作为节点集V。若两人认识，则在相应的节点之间画一条无向边，于是得到一个简单无向图G且满足条件：对于任意u，v∈V，有deg(u)+deg(v)≥n-2。对于任意不相邻的节点u，v∈V，考虑任意节点w∈V—{u，v}。根据已知条件，u与w或v与w邻接。又因为u与v不邻接，因此u与w且v与w邻接。根据w的任意性有deg(u)，deg(v)≥n-2，于是deg(u)+deg(v)≥2（n-2）。由于n≥4，所以2（n-2）≥n，于是deg(u)+deg(v)≥n。根据教材中定理8.16知，G是哈密尔顿图。36.证明：K5和K3，3都是极小非平面图。证首先K5和K3，3都不是平面图。（1）对于K5，任意去掉一条对角线所在边e所得到的图K5—e和去掉非对角线所在边e所得到的图K5—e都是平面图，其平面表示分别见图8.21(a)和图8.21(b)，因此K5是极小非平面图。（2）对于K3，3，任意去掉一条边e所得到的图​K3，3—e是平面图，其平面表示见图8.21(c)，因此K3，3都是极小平面图。(a)K5—e(b)K5—e(c)K3，3—e图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条边围成，假设存在G的1个面R至少由4条边围成，其面的边界为v1v2v3v4…v1。若v1与v3在G中不邻接，则在R内添加边v1v3，所得到的图仍为平面图，与已知矛盾。于是v1与v3在G中邻接且边v1v3在R的外部。同样v2与v4在G中也邻接且边v2v4也在R的外部。因此得到两条边v1v3和v2v4，它们相较于R的外部，这与G是平面图相矛盾，故G的每个面都是三角形。38.证明：最小度的简单连通平面图G的边数不可能为7。证(反证)设G是(n，m)图，这里m=7，根据推论1知，m≤3n-6，即7≤3n-6，于是3n≥13。根据握手定理，有，即3n≤14。这是一个矛盾。39.若(n，m)平面图的每个面至少由k(k(3)条边围成，则。证由于G是连通图，根据欧拉公式，G的面数为m-n+2。因为每个面至少由k条边围成，但每一条边是两个面的边界，于是k(m-n+2)/2≤m，所以。40.分别画出图8.22(a)与图8.22(b)的对偶图。(a)G1(b)G2图8.22解图8.22的对偶图见图8.23的虚线部分所画的图。(a)G1*(b)G2*图8.2341.设图G的节点着色数，则G至少有k(k－1)/2条边。证由于，设0图G用1，2，…，k种颜色对节点着色，且分别涂上这k种颜色的节点集合分别为V1，V2，…，Vk，则对于任意i≠j，Vi与Vj之间至少存在一条边，否则可以给Vi和Vj的节点涂色同一种颜色，这与已知矛盾。于是G至少有k(k－1)/2条边。42.证明：任意9个人中，有3个人相互认识或4个人相互不认识。证在完全无向图K9中，其节点代表人，若两个人认识则在相应的两节节点所连的边上涂上红色，否则涂上蓝色。于是问题转化为，若仅用红、蓝对K9的边涂色，则任意的一种涂色方案，都存在一个边是红色的K3或边是蓝色的K4。任取一个节点v，由于与v关联的边有8条，当用红、蓝两种颜色去涂时，任意的一种涂色方案，都至少有4条边涂的红色或至少有4条边涂的蓝色。不妨设至少4条边涂的是红色，设与这4条边关联的另外4个节点分别为v1，v2，v3和v4。若v1，v2，v3和v4所构成的K4中存在1条边涂的是红色，如v1v2，则三角形vv1v2是红色的K3。若K4中任意两条边都涂的是蓝色，则出现一个边是蓝色的K4。第9章习题参考答案1.分别画出所有不同构的五阶无向树和六阶无向树。解根据性质1,5阶无向树恰有4条边，由握手定理知，其所有节点度数之和为2×4=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条边，其所有节点度数之和为2×5=10。6阶无向树G至少片叶。若G恰有2片叶，则其度数序列为2,2,2,2,1,1，此时为图9.2(a)所示。若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)画出两棵不同构的满足上述要求的无向树。解（1）设该无向树G有x个也节点，于是G共有2+3+x=x+5个节点。根据无向树性质知，G有x+4条边，由握手定理有2×4+3×3+x=2(x+4)于是x=9，进而G由9+5=14个节点。（2）图9.3所示的是两个不同构的满足上述要求的无向树。(a)(b)图9.33.证明：连通无向图G是无向树的充要条件是G的每一条边都是桥。证（）若图G存在一条边e={u,v}不是桥，则G—e仍连通，因而节点u和v之间必存在一条不经过e的路径，进而G中存在圈，这与无向树的定义矛盾。（）若G中存在圈，则圈上的任何边都不是桥，这与已知矛盾。于是，G中不含有圈，由于G是连通的，故G是无向树。4．证明：恰有两片树叶的无向树是一条路径。证设G是n阶无向树，它恰有两片树叶，于是其余n-2个节点v1，v2，…，vn-2中的每一个节点至少为2度，根据握手定理，有因此对于任意i(i=1，2，…，n-2)，有deg(vi)=2。这时，G中存在一条从一个叶节点到另一个叶节点的欧拉轨迹，且该轨迹是一条路径。5.如图9.4所示的两个图，分别画出所有不同构的生成树。SHAPE\*MERGEFORMAT(a)(b)图9.4解（1）对于图9.4(a)所示的图，其所有不同构的生成树有3棵，如图9.5所示。(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阶根树有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)所有子(根)树。图9.9解（1）根节点为A。（2）树叶节点分别为K，L，F，G，M，I，J。（3）分支节点分别为A，B，C，D，E，H。（4）内点分贝为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）树高为3。（9）最大出度为3。（10）所有子（根）树分别为：根树本身，T[B，E，F，K，L]，T[C，G]，T[D，H，I，J，M]，T[E，K，L]，T[H，M]，平凡子树分别为K，L，F，G，M，I，J。9.如图9.10所示，存在是根树的生成子图吗？若存在，求出所有不同构的是根树的生成子图。图9.10解：（1）不同构的是根树的生成子图只有1棵，见图9.11所示（未画出根树的方向）。（2）不同构的是根树的生成子图只有3棵，见图9.12所示（未画出根树的方向）。图9.11（a）（b）（c）图9.1210.证明以下结论：(1)完全二叉树的节点个数必为奇数；(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，29，31，37，41；再组合10+7=17，得17，11，13，17，19，23，29，31，37，41；继续下去，最后组合95+143=238。 2 3 5 7 11 13 17 19 23 29 31 37 41 5 5 7 11 13 17 19 23 29 31 37 41 10 7 11 13 17 19 23 29 31 37 41 17 11 13 17 19 23 29 31 37 41 17 24 17 19 23 29 31 37 41 24 34 19 23 29 31 37 41 24 34 42 29 31 37 41 34 42 53 31 37 41 42 53 65 37 41 42 53 65 78 95 65 78 95 143 238所求的哈夫曼树如图9.13所示。图9.1312.在下面给出的3个符号串集合中，哪些是前缀码？哪些不是前缀码？若是前缀码，则构造定位二叉树，其树叶代表其二进制编码。若不是前缀码，则说明理由。(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%，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.3×2+0.2×2+0.15×3+0.3×2+0.1×3+0.1×3+0.06×4+0.05×5+0.04×4=2.74所以，传输10000个按上述比例出现的数字时，至少要用2.74×10000=27400个二进制数字。图9.1514．将图9.16所示的森林F转换成定位二叉树B。SHAPE\*MERGEFORMAT图9.16解按自然转换规则得到的定位二叉树B见图9.17。图9.17(人，狼，羊，菜)(人，狼，羊)(人，狼，菜)(人，羊，菜)(人，羊)(狼，菜)(羊)(狼)(菜)(Φ)（a）（b）（c）（d）（e）（f）（g）�EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3����EMBEDEquation.3���ABCDEFGKLHIJMABCDEFGHIJ_1474856097.unknown_1475217627.unknown_1475218318.unknown_1475218660.unknown_1475218794.unknown_1475222066.unknown_1475632067.unknown_1475632085.unknown_1475221903.unknown_1475218759.unknown_1475218769.unknown_1475218715.unknown_1475217791.unknown_1475218274.unknown_1475217635.unknown_1475217778.unknown_1475216649.unknown_1475216881.unknown_1475217533.unknown_1475217618.unknown_1475216907.unknown_1475216665.unknown_1474856593.unknown_1474859754.unknown_1474856421.unknown_1465494344.unknown_1474722396.unknown_1474723048.unknown_1474855587.unknown_1474855794.unknown_1474724162.unknown_1474722976.unknown_1474722983.unknown_1474722780.unknown_1474722055.unknown_1474722162.unknown_1474722259.unknown_1474722114.unknown_1474720822.unknown_1474721355.unknown_1465498808.unknown_1465498862.unknown_1465494345.unknown_1465493448.unknown_1465493506.unknown_1465493559.unknown_1465494248.unknown_1465494343.unknown_1465493568.unknown_1465493549.unknown_1465493496.unknown_1465367566.unknown_1465367716.unknown_1465367738.unknown_1465367748.unknown_1465367757.unknown_1465367726.unknown_1465367613.unknown_1465367614.unknown_1465367612.unknown_1465367611.unknown_1465367536.unknown_1465367545.unknown_1465215107.unknown