离散数学图论复习.docxVIP

一、填空题1、含5个结点，4条边的无向连通图（不同构）有3个，它们是。2、设图G = V, E，的邻接矩阵，则的入度= 3，的出度= 1，从到的长度2的路有1条。3、n个结点的无向完全图的边数为。n(n-1)/24、图的对偶图为。5、一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有1个4度结点。二、选择题1、图中从v1到v3长度为3 的通路有（D）条。A．0B．1C．2D． 32、下图中既不是Eular图，也不是Hamilton图的图是（B）。3、在一棵树中有7片树叶，2个3度结点，其余都是4度结点则该树有（A）个4度结点。A．1B．2C．3D．4 4、设G=V, E为无向图，|V|=7，|E|=23，则G一定是（D）。A、完全图 B、树 C、简单图 D、多重图5、给定无向图G=V, E，如下图所示，下面哪个边集不是其边割集（B）。A、B、C、D、6、有n个结点n≧3，m条边的连通简单图是平面图的必要条件（D）。A、 B、 C、 D、7、设V={a, b, c, d, e, f },，则有向图G=V, E是（C）。A、强连通的 B、单向连通的 C、弱连通的 D、不连通的8、下面那一个图可一笔画出（A）。9、在任何图中必定有偶数个（C）。A、度数为偶数的结点 B、入度为奇数的结点C、度数为奇数的结点D、出度为奇数的结点10、给定下列序列，（B）可以构成无向简单图的结点次数序列。A、（1，1，2，2，3）B、（1，1，2，2，2）C、（0，1，3，3，3）D、（1，3，4，4，5）11、设G是简单有向图，可达矩阵P(G)刻划下列（C）关系。A、点与边 B、边与点 C、点与点 D、边与边12、一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（C）。A、5 B、7 C、9D、8计算题权数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，，∴即，∵，∴ T中7个结点。（2）具有3个两度结点，一个3度结点，3片树叶的树（非同构的）共有以下三种：3、如图给出的赋权图表示六个城市a, b, c, d, e, f 及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。解：要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得其最小生成树为：其树权即最小造价为：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 20 25 20 35 40 25 3560100最优二叉树为:编码树为：前缀码：a：11； b：01； c：101； d：100； e：001；f：0000；g：0001 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