离散数学(本)阶段练习四.doc_第1页
离散数学(本)阶段练习四.doc_第2页
离散数学(本)阶段练习四.doc_第3页
离散数学(本)阶段练习四.doc_第4页
全文预览已结束

下载本文档

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

文档简介

华东理工大学 网 络 教 育 学 院本科离散数学第四阶段练习一、判断题（对的在括弧中打个“”，错的在括弧中打个“”）1、对任何无向图，奇其点的个数必然为奇数。（）2、对于简单无向图而言，其所有顶点的度数和等于其两倍的边数。（）3、自补图对应的完全图的边数必为偶数。（）4、通路就是边不重复的一个点边交替序列。（）5、若图是连通的，则其补图必然是不连通的。（）6、若是图的邻接矩阵，则矩阵幂次中的对角线上元素等于它对应的顶点的度。（）7、所有顶点的度都为偶数的无向图一定是欧拉图。（）8、含有汉密尔顿路的图就是汉密尔顿图。（）9、对连通平面图而言，其边数、点数、面数必然满足。（）10、任意一棵树都至少拥有三个1度点。（）11、任一连通图都至少有一棵生成树，且生成树可以不唯一。（）12、任意一棵二叉树的树叶可对应一个前缀码。（）二、作图题1、画出一个自补图；2、画出一个既有欧拉回路、又有汉密尔顿圈的无向图；3、画出一个有欧拉回路、但没有汉密尔顿圈的无向图；4、画出一个无欧拉回路、但却有汉密尔顿圈的无向图；5、画出一个自对偶图。三、一棵树有个2度点，个3度点，个度点，其余均为1度点，试问：这棵树有多少个1度点？解：设树有个1度点，是的边数，于是有解之即得四、若无向图中恰有两个奇点，试证明这两点之间必有一条路相连。证明：（反证法）不妨设着两个奇点为，且它俩在图中没有路相连，那么它俩必存在于两个连通分支中，即存在于图的两个不连通的子图、当中，而作为每个子图来说，其中奇点的数目一定为偶数，故子图、当中至少分别存在两个奇点，即图中至少有4个奇点，这显然与图中恰有两个奇点矛盾。故这两点之间必有一条路相连。五、试证明完全二部图不是平面图。证明：（反证法）设完全二部图是平面图，且点数、边数、面数分别为、，由于图中任何三条边围不成一个面，即围成一个面至少需要4条边，于是有，即，代入欧拉公式中即得。而中的，且，于是矛盾，故而不是平面图。六、用韦尔奇.鲍威尔法证明右下图的着色数。证明：由韦尔奇.鲍威尔法，按红（）、蓝（）、黄（）、白（）的着色顺序，给本图染色如右，正好用了4中颜色，因此该图是4色的。又由于该图中存在完全图，其4个顶点必须染以不同的颜色，所以该图不可能是3色的，故该图的色数。七、试证明彼得森（）图不是汉密尔顿图。证明：（仿照课本的例题2的标号法）因为任一个汉密尔顿图经过这种标号后，的个数必然相等（注意逆命题不成立！），利用逆否命题，现在此图因为有7个，9个，故彼得森（）图不是汉密尔顿图
人人文库> 全部分类> 教育资料 > 课设设计

温馨提示

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

最新文档

评论

0/150

提交评论