特殊图习题及答案_第1页
特殊图习题及答案_第2页
特殊图习题及答案_第3页
特殊图习题及答案_第4页
特殊图习题及答案_第5页
已阅读5页,还剩2页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第六章特殊图题六一.判断图一哪些是欧拉图?对不是欧拉图至少要加多少条边才能成为欧拉图?图一解答:,一,二二.画一个无向欧拉图使它具有:(一)偶数个顶点,偶数条边。(二)奇数个顶点,奇数条边。(三)偶数个顶点,奇数条边。(四)奇数个顶点,偶数条边。解答:(一)四四(二)(三(三)(四)三.判断彼得松图是否为欧拉图,是否为哈密顿图。若不是,至少加几条新边才能使它成为欧拉图?又至少加几条新边才能使它变成哈密顿图?五条新边可以成为欧拉图加一条边可以成为哈密顿图。四.判断图二所示四个图是否能一笔画出。一三零离散数学图二解答:五.(一)画一个欧拉回路与哈密顿回路地;(二)画一个欧拉回路,但没有哈密顿回路图;(三)画一个没有欧拉回路,但有哈密顿回路地;(四)画一个既没有欧拉回路也没有哈密顿回路地解答:(一)三(三(二)(三)(四)六.设有a,b,c,d,e,,g七个,它们分别会讲如下各种语言:a会讲英语b会讲汉语与英c会讲英语西班牙语与俄语d会讲汉语与日语e会讲德语与西班牙语f会讲法语,日语与俄语g地座位安排在圆桌旁使得每个均能与它身边谈。解答:分别用a,,c,,e,,g七个结点表示七个,若两可以谈(使用同一种语言),则在代表它们地结点之间连一条无向边如下图a地座位安排在圆桌旁使得每个均能与它身边谈只需找出一条哈密顿回路如abdfgeca。七.际象棋地马走日字,即在x,y格子地马可以走到xy,xy二地任何一个走遍所有地格子且每个格子只走一次称作马周游。证明:一三一第六章特殊图(一)在三四棋盘上存在马地周游。(二)在三三棋盘上不存在马周游。两个顶点之间相邻当且仅当马可以从对应一个格子跳到另一个格子。因此,地周游问题等价于图地哈密顿通路存在问题。(一)三四棋盘可以使用以下走法(格子数字代表走一一二三四九六七二一零五八(二)三三棋盘不可能存在哈密顿通路,因此心格子对应顶点是孤立点。八.一棵无向树T有五片树叶,三个二度分支点,其余地分支点都是三度结点,问T有几个结点?T有n个结点根据握手定理有三二三(n五二(n得。九.无向树T有八片树叶二个三度分支点其余分支点都是四度顶点问有几个顶点?解答:假设T有n个顶点,根据握手定理有得=一二一零.一棵无向树T有ii,k)个i度分支点其余顶点都是树叶问有几片树叶?T有n个顶点xnxnnn根据握手定理,二三kk有二(nx二nn从而得xnkn二二in。二三k三kii三若n(n阶无向树T最大度T至少为几最多为几?解答:至少为二至多为n-一。T三所示。回答以下问题:(一)T是几叉树?(二)T树高为几?(三)T有几个内点?(四)T有几个分支点?一三二离散数学图三解答:(一)T是四叉树。(二)T树高为四。(三)T有八个内点。(四)T有七个分支点。画一棵权为最优二叉树并计算出它权。四)四六七)三九)二。下面给出各符号串集合哪些是前缀码?一二三四b,c,dd,dc,aba,abb,五b,c,a,aa,ac,abc,abb,解答:A:是A:是A:否A:是A:否。一二三四五四地二叉树产生一个二元前缀码。图四解答:{零零零,零零一,一零零零,一零一,。设七个字母在通信出现地频率如下:一三三第六章特殊图a:三五%b:二零%c:一五%d:一零%e:一零%f:五%g:五%构造一组表示它们二元前缀码使得传送地二制位最少。二元前缀码为{零零零零,零零零一,零零一,零一,一零零,一零一,。图五地二叉树表示一个算式。(一)用序遍历法还原算式。(二)用前序遍历法写出该算式波兰符号法表达式。(三)用后序遍历法写出该算式逆波兰符号法表达式。图五解答:(一)(二)(三)一八.用二叉有序正则树表示代数表达式解答:一三四离散数学一九.六所示图,重新找面嵌入,使外部面次数分别为三与。图六解答:外部面次数为三外部面地次数为四七所示两面图面边界与次数并验证欧拉公式。图七地次数为D(r)D(r)D(r)D(r)D(r)D(r)。一二三四五六右图各面次数为D(r)D(r)D(r)D(

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论