图论第二次作业40055.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《图论第二次作业40055.pdf》由会员分享,可在线阅读,更多相关《图论第二次作业40055.pdf(4页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 图论第二次作业 Newly compiled on November 23,2020 图论第二次作业 一、第四章(1)画一个有 Euler闭迹和 Hamilton圈的图;(2)画一个有 Euler闭迹但没有 Hamilton 圈的图;(3)画一个有 Hamilton 圈但没有 Euler闭迹的图;(4)画一个既没有 Euler闭迹也没有 Hamilton 圈的图;解:(1)一个有 Euler闭迹和 Hamilton圈的图形如下:(2)一个有 Euler闭迹但没有 Hamilton 圈的图形如下:(3)一个有 Hamilton 圈但没有 Euler闭迹的图形如下:(4)一个既没有 Euler闭
2、迹也没有 Hamilton 圈的图形如下:证明:若 G没有奇点,则存在边不重的圈 C1,C1,Cm,使得)()()()(21mCECECEGE。证明:将G中孤立点除去后的图记为1G,则1G也没有奇点,且2)(1G,则1G含圈1C,在去掉)(11CEG 的孤立点后,得图2G,显然2G仍无奇度点,且2)(2G,从而2G含圈2C,如此重复下去,直到圈mC,且)(mmCEG 全为孤立点为止,于是得到)()()()(21mCECECEGE 。证明:若(1)G不是二连通图,或者(2)G是具有二分类),(YX的偶图,这里YX,则 G是非 Hamilton图。证明:(1)因为 G不是二连通图,则 G不连通或者
3、存在割点 v,有2)(vGw,由相关定理得:若 G是 Hamilton 图,则对于 v(G)的任意非空顶点集 S,有:SSGw)(,则该定理得逆否命题也成立,所以可得:若 G不是二连通图,则 G是非 Hamilton 图。(2)因为 G是具有二分类),(YX的偶图,又因为YX,在这里假设YX,则有XYXGw)(,也就是说:对于 v(G)的非空顶点集 S,有:SSGw)(成立,则可以得出 G是非 Hamilton 图。设 G是有度序列),(21nddd 的非平凡简单图,这里nddd 21,证明:若不存在小于2)1(n的正整数 m,使得mdm且mndmn1,则 G有Hamliton 路。证明:在
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二次 作业 40055
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内