离散数学题(3) 求解 20+5

发布网友发布时间：2023-09-03 22:39

共1个回答

热心网友时间：2024-03-06 10:40

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