版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第六章特殊图题六一.判断图一哪些是欧拉图?对不是欧拉图至少要加多少条边才能成为欧拉图?图一解答:,一,二二.画一个无向欧拉图使它具有:(一)偶数个顶点,偶数条边。(二)奇数个顶点,奇数条边。(三)偶数个顶点,奇数条边。(四)奇数个顶点,偶数条边。解答:(一)四四(二)(三(三)(四)三.判断彼得松图是否为欧拉图,是否为哈密顿图。若不是,至少加几条新边才能使它成为欧拉图?又至少加几条新边才能使它变成哈密顿图?五条新边可以成为欧拉图加一条边可以成为哈密顿图。四.判断图二所示四个图是否能一笔画出。一三零离散数学图二解答:五.(一)画一个欧拉回路与哈密顿回路地;(二)画一个欧拉回路,但没有哈密顿回路图;(三)画一个没有欧拉回路,但有哈密顿回路地;(四)画一个既没有欧拉回路也没有哈密顿回路地解答:(一)三(三(二)(三)(四)六.设有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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 药品集中招标合作协议样本
- 学校网络升级国防光缆施工合同
- 养殖行业培训租赁协议
- 退休工程师技术支持合同
- 机场航站楼幕墙安装协议
- 舞蹈室租赁合同
- 酒店屋顶防水维护服务合同
- 医疗卫生合作的经济合同管理办法
- 暂停职务留薪协议
- 博物馆展区铁艺栏杆施工合同
- 2024年房屋装修工程合同
- 新高考背景下2025届高考英语完形和语填的命题实践和思考 课件
- 《魏书生班主任工作漫谈》读书心得体会课件
- 第16课 国家出路的探索与列强侵略的加剧 课件上学期统编版(2019)必修中外历史纲要上
- 2024秋期河南开放大学本科《法律社会学》一平台无纸化考试(作业练习1至3+我要考试)试题及答案
- 2024年四川雷波县“123”林业技术人才定向培养毕业生招聘拟聘易考易错模拟试题(共500题)试卷后附参考答案
- 白求恩人物生平纪念
- 2024年度陕西榆林能源集团限公司高校毕业生招聘(238人)高频难、易错点500题模拟试题附带答案详解
- 零工市场(驿站)运营管理投标方案(技术方案)
- GB 5009.6-2016 食品安全国家标准 食品中脂肪的测定
- 器乐进课堂——口风琴教学.ppt
评论
0/150
提交评论