《离散数学 杨圣洪 第五章习题解答》由会员分享，可在线阅读，更多相关《离散数学 杨圣洪 第五章习题解答（7页珍藏版）》请在金锄头文库上搜索。
1、第五章习题解答第五章习题解答 1、确定图 5.36 中各点的度数，判断是否满足握手定理，是否构成一个欧拉图？是否满 足哈密尔顿的充分条件，并用 Powell 着色方法对其各个结点进行着色？给出其对偶图，并 对对偶图的结点进行着色？给出其邻接矩阵，算出任意二点之间长度为 1、2、3、n-1 的路的条数，从而判断它是否连通？给出其生成树？用 Prim 给出其最小生成树，用 Kruskal 给出其最小生成树。 解：(1) Deg(A)=3，deg(B)=3，deg(C)=3，deg(D)=2，deg(E)=5，deg(F)=2 点的度数和=3+3+3+2+5+2=18 边数=9，所以度数和=边数的
2、2 倍，从而满足握手定理。 (2)度数为奇数的结点 4 个，不可能存在欧拉路，也不可能存在欧拉回路。 (3)n=6，(A,B)=6，(A,C)=6，(A,D)=5, (A,E)=8, (A,F)=5, (B,C)=6,(B,D)=5,(B,E)=8,(B,F)=5, (C,D)=5, (C,E)=8, (C,F)=5, (D,E)=7, (D,F)=4deg(A)=deg(B)= deg(C) deg(D)=deg(F)。E-A-B-C-D-F 用 1 号色对结点 E 进行染，未着色有：A-B-C-D-F 用 2 号色对结点 A 进行染色，与 A 不相邻的 B 也染 2 号色，未着色 C-D-
3、F 用 3 号色对 C 染色，与 C 不相邻的 D 染 3 号色，与 C、D 均不相邻的 F 也染 3 号色。 (5)其对偶图如下：deg(5)=6deg(1)=deg(2)=deg(3)=deg(4)=3 结点 5 着 1 号色， 结点 1 着 2 号色，结点 3 与 1 不相邻着 2 号色， 结点 2 着 3 号色，结点 4 与 2 不相邻着 3 号色。 (6)其邻接矩阵为： A F B ED C 3 4 4 5 5 1 2 6 5 1 23 4 5 A F B E D C 3 图 5.36 2 6 4 图 5.37 5 1 3 4 4 5 5 1 2 6 1 1 2 2 3 3 4 5
4、010001 101111 010010 010011 011100 110100 (7)长为 1，2，3，n-1 的路之条数 长为 1 的路的条数 010001 101111 010010 010011 011100 110100 长为 2 的路的条数，即为邻接矩阵的平方 010001 101111 010010 010011 011100 110100 = 010001 101111 010010 010011 011100 110100 211211 151222 112211 222311 121132 121123 长为 3 的路的条数，即邻接矩阵的 3 次方 211211 1512
5、22 112211 222311 121132 121123 = 010001 101111 010010 010011 011100 110100 272345 787988 272354 393477 485744 584744 长为 4 的路条数，即邻接矩阵的 4 次方 272345 787988 272354 393477 485744 584744 = 010001 101111 010010 010011 011100 110100 121611161212 163916242424 111612161212 162416231616 122412162019 1224121619
6、20 长度为 5 的路的条数，即邻接矩阵的 5 次方 121611161212 163916242424 111612161212 162416231616 122412162019 122412161920 = 010001 101111 010010 010011 011100 110100 286328404344 6310463877979 286328404443 408740566363 437944635252 447943635252 (8)由于任何二点之间均存在长度为 2 的路，即任意二点之间经过二条边均可达，所以 它是连通的。 (9)给出其生成树？ n=6，任取 5 条不构
7、成回路的边，便构成一棵生成树，如 AC,AE,AF,EB,ED。 (10)用 Prim 给出其最小生成树 解：以边为角度，寻找边权最小的 5 条边。 ED(1)，EC(2), AF(3), FE(4), BC(4) (11)用 Kruskal 给出其最小生成树。 解：从结点 A 出发，依次找出与已知结点最近的结点与相应边 U=A,F T=AF U=A,F,E T=AF,FE U=A,F,E,D T=AF,FE,ED U=A,F,E,D,C T=AF,FE,ED,EC U=A,F,E,D,C,B, T=AF,FE,ED,EC,CB 2、确定图 5.37 中各点的度数、入度、出度，判断是否满足握手
8、定理，是否构成一个欧 拉图？是否满足哈密尔顿的充分条件，并用 Powell 着色方法对其各个结点进行着色？给出 其对偶图，并对对偶图的结点进行着色？给出其邻接矩阵，算出任意二点之间长度为 1、2、 3、n-1 的路的条数，从而判断它是否连通？给出其生成树？给出其根树，用 Prim 给 出其最小生成树，用 Kruskal 给出其最小生成树。 (1)各点的度数：deg(1)=2，deg(2)=2, deg(3)=3, deg(4)=2, deg(5)=3, deg(6)=2，和=14 入度：deg(1)=1, deg(2)=1, deg(3)=1, deg(4)=1, deg(5)=1, deg(
9、6)=2，和=7 出度：deg(1)=1, deg(2)=1, deg(3)=2, deg(4)=1, deg(5)=2, deg(6)=0，和=7 出度和=入度和，所有点度数 14=边数 7 的两倍 (2)如果不考虑边的方向，度数为奇数的结点 3、5，所以存在一条无向的 Euler 路，但 不存在无向的 Euler 回路。如：31-12-23-35-54-46-65 如果考虑边的方向，由于结点 3、5、6 的入度不等于出度，所以不存在有向 Euler 路， 也不存在有向 Euler 回路。 (3)n=6，不考虑边的方向，存在 Hamilton 路的充分条件是，任意二点的度数=5， deg(1
10、)+deg(6)=4deg(1)=deg(2)=deg(4)=deg(6)，队列为 3-5-1-2-4-6 用 1 号色着结点 3，与 3 不相邻的 4 着 1 号色，未着色 5-1-2-6 用 2 号色着结点 5，与 5 不相邻的 1 着 2 号色，未着色 2-6 用 3 号色着结点 2，与 2 不相邻的 6 着 3 号色。 (4)由于原图只有 2 个封闭的区域，与一个完全开放的区域，因此其对偶图只有 3 个结 点，跨越原图每边，得到对偶图的边，因此最终的对偶图如下图所示。 Deg(A)=3，deg(B)=3，deg(C)=7，由于任意二点之间均有边相连，则需要 3 种颜色。 3 2 6 1
11、 5 4 1 1 2 2 3 3 4 A B C (5)给出其邻接矩阵 000000 101000 100000 010001 000100 000010 (6)算出任意二点之间长度为 1、2、3、n-1 的路的条数，从而判断它是否连通？ 长度为 1 的路就是邻接矩阵 000000 101000 100000 010001 000100 000010 长度为 2 的路就是跨越 2 条边可达的路之条数，即邻接矩阵的平方 000000 101000 100000 010001 000100 000010 = 000000 101000 100000 010001 000100 000010 000
12、000 100000 000000 101010 010001 000100 长度为 3 的路就是跨越 3 条边可达的路之条数，即邻接矩阵的 3 次方 000000 100000 000000 101010 010001 000100 = 000000 101000 100000 010001 000100 000010 000000 000000 000000 100100 101010 010001 长度为 4 的路就是跨越 4 条边可达的路之条数，即邻接矩阵的 4 次方 000000 000000 000000 100100 101010 010001 = 000000 101000 1
13、00000 010001 000100 000010 000000 000000 000000 010001 100100 101010 长度为 5 的路就是跨越 5 条边可达的路条数，即邻接矩阵的 5 次方 000000 000000 000000 010001 100100 101010 = 000000 101000 100000 010001 000100 000010 000000 000000 000000 001010 010001 100100 (7)不考虑边的方向，任找 5 条不构成回路的边得到其生成树：12,23,35,54,56。 (8)考虑边的方向，从结点 1 出发的生
14、成树，即根树为 12,23,35,54,56 (9)最小生成树是指不考虑边的方向，生成边权最小的树：31(1),23(1),56(2),35(3),46(3) (10)Kruskal 生成树： U=1,3,T=31 U=1,3,2,T=31,23 U=1,3,2,5,T=31,23,35 U=1,3,2,5,6,T=31,23,35,56 U=1,3,2,5,6,4,T=31,23,35,56,46 3、给定权值 1(A)、4(S)、9(D)、16(F)、25(G)、36(H)、49(J)、64(K)、81(L)、100(M)， 构造出表 5.1 所示的构造表，并给出图 5.23 所示的 Huffman 树，要遵循“左小右大、组合 优先，左 0 右 1，不足补 0”的原则，得到唯一的最优二叉树，对 ASDFGHJKLM 进行编码， 并对“1101100000110110011111”译码。 解：权值已从底到高排列好，先构造数据表，然后构造 Huffman 树。 385 166 219 81 85100119 36 49
