求解几道离散数学题2

Question

第二部分 图论方法
第四章 图
4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个奇度顶点 ？

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点. [ ]

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为 [ ]

第五章 树
5-1 握手定理的应用（指无向树）
（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有( )个？
（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有( )片？

5-2 一棵树中有 i 个顶点的度数为 i（=2，…k），其余顶点都是树叶，问树叶多少片？
设有x片,则x=

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。试问：（1） T 的权 W（T）？ （2）树高几层 ？

5-4 以下给出的符号串集合中，那些是前缀码？将结果填入[ ]内.
B1 = {0，10，110，1111} [ ]
B2 = {1，01，001，000} [ ]
B3 = {a，b，c，aa，ac，aba，abb，abc} [ ]
B4 = {1，11，101，001，0011} [ ]

5-5(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝 [ ]

5-6(是非判断题)二元正则树有奇数个顶点。材 [ ]

5-7 奥运年欢送外国朋友时,在网上传输 GOODBYE 的最佳前缀码,共用多少位二
进制码。
求：1、最优二元树 T； 2. ? 位； 3、每个字母的码字；

Answer 1

4-1 10 个顶点的简单图 G 中有4个奇度顶点，问G的补图中有几个奇度顶点？

答案：6个奇度顶点。

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有8个顶点. 

答案：[对，是]

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为 [2]

答案：所有顶点的度数之和为2。

5-1  握手定理的应用（指无向树）

（1）在一棵树中有7片树叶，3个3 度顶点，其余都是4度顶点，问有( 1 )个？

（2）一棵树有两个4度顶点，3个3度顶点，其余都是树叶，问有( 7 )片？

5-2 一棵树中有i个顶点的度数为ai（i=2，…,k），其余顶点都是树叶，问树叶多少片？

 设有x片,则x=3*a3+4*a4+…+k*ak-2(a3+a4+…+ak)+2

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。试问：（1）T 的权W（T）=61，（2）树高5层。 

5-4  以下给出的符号串集合中，那些是前缀码？将结果填入[    ]内.

         B1 = {0，10，110，1111}                                       [是]

         B2 = {1，01，001，000}                                        [是]

         B3 = {a，b，c，aa，ac，aba，abb，abc}                         [否]

         B4 = {1，11，101，001，0011}                                  [否]

5-5(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝[否]

5-6(是非判断题)二元正则树有奇数个顶点。[是]

5-7 奥运年欢送外国朋友时,在网上传输 GOODBYE 的最佳前缀码,共用多少位二进制码。                                                  

求：1、G,O,D,B,Y,E权分别为1，2，1，1，1，1，最优二元树T看图，

2. 18 位；        

3、字母G,O,D,B,Y,E的码字分别为； 000，11，001，010，011，10

Answer 2

好难！