图论复习答案

　　一、填空题

　　1、含5个结点，4条边的无向连通图（不同构）有个，它们是。

　　?0

　　??1A??1??1?2、设图G = ，V?{v1,v2,v3,v4}的邻接矩阵101001001??1?0??0??，则v1的入度

　　deg?(v1)= ，v4的出度deg?(v4)= ，从v2到v4的长度2的路有条。

　　3、n个结点的无向完全图Kn的边数为。

　　4、图的对偶图为。

　　5、一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有 个4度结点。

　　二、选择题

　　1、图中从v1到v3长度为3 的通路有（D）条。

　　A．0 B．1 C．2 D． 3

　　2、下图中既不是Eular图，也不是Hamilton图的图是（B）。

　　1

　　3、在一棵树中有7片树叶，2个3度结点，其余都是4度结点则该树有（） 个4度结点。

　　A．1 B．2 C．3 D．4

　　4、设G=为无向图，|V|=7，|E|=23，则G一定是（D）。

　　A、完全图 B、树 C、简单图 D、多重图

　　5、给定无向图G=，如下图所示，下面哪个边集不是其边割集（B）。

　　A、{?v1,v4?,?v3,v4?}

　　B、{?v1,v5?,?v4,v6?}

　　C、{?v4,v7?,?v4,v8?}

　　D、{?v1,v2?,?v2,v3?}

　　6、有n个结点n≧3，m条边的连通简单图是平面图的必要条件（D）。

　　A、n?3m?6 B、n?3m?6 C、m?3n?6 D、m?3n?6

　　7、设V={a, b, c, d, e, f },

　　E?{?a

　　,b?,?b,c?,?c,a?,?a,d?,?d,e?,?f,e?}，则有向图G=是（C）。

　　A、强连通的 B、单向连通的 C、弱连通的 D、不连通的

　　8、下面那一个图可一笔画出（A）。

　　9、在任何图中必定有偶数个（C）。

　　A、度数为偶数的结点 B、入度为奇数的结点

　　C、度数为奇数的结点D、出度为奇数的结点

　　10、给定下列序列，（）可以构成无向简单图的结点次数序列。

　　A、（1，1，2，2，3） B、（1，1，2，2，2）

　　C、（0，1，3，3，3） D、（1，3，4，4，5）

　　2

　　11、设G是简单有向图，可达矩阵P(G)刻划下列（C）关系。

　　A、点与边 B、边与点 C、点与点 D、边与边

　　12、一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（C）。

　　A、5 B、7 C、9 D、8

　　三、 计算题

　　1. 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。

　　2. 一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。

　　（1）T中有几个结点；

　　（2）画出具有上述度数的所有非同构的无向图。

　　解：（1）设该树树叶数为t，则树T的结点数为3+1+t，又边数=结点数-1，

　　?deg(v)?边数2倍，∴3?2?1?3?t?1?2(3?t?1?1) i

　　即9?t?6?2t，∵t?

　　3，∴ T中7个结点。

　　（2）具有3个两度结点，一个3度结点，3片树叶的树（非同构的）共有以下三种：

　　3、如图给出的赋权图表示六个城市a, b, c, d, e, f 及架起城市

　　间直接通讯线路的预测造价。试给出一个设计方案使得各

　　城市间能够通讯且总造价最小，并计算出最小总造价。

　　3

　　解：要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得其最小生成树为：

　　其树权即最小造价为：1+2+3+5+7=18。

　　4. 设7个符号在通讯中使用的频率如下：

　　a：35% ，b：20% ，c：15% ，d：10% ， e：10% ，f：5% ，g ：5% 编一个相应的二元前缀码，使通讯中出现的符号尽可能地减少，并画出对应的二叉树及求二叉树的过程。

　　解：用100乘各频率得权数：

　　w1=35， w2=20， w3=15， w4=10， w5=10， w6=5， w7=5 将其由小到大排列用Huffman算法可求得最优树。

　　5 5 10 10 15 20 35

　　10 10 10 15 20 35

　　20 10 15 20 35

　　25 35

　　35

　　40

　　100

　　最优二叉树为:

　　编码树为：

　　前缀码：a：11； b：01； c：101； d：100； e：001；f：0000；g：0001

　　4

　　60

　　5、假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year的编码信息。

　　解：根据权数构造最优二叉树。传输它们的最佳前缀码如上图所示，happy new year的编码信息为：10 011 0101 0101 001 110 111 0100 001 111 011 000

　　5