离散数学第九章图的道路与连通习题答案_第1页
离散数学第九章图的道路与连通习题答案_第2页
离散数学第九章图的道路与连通习题答案_第3页
离散数学第九章图的道路与连通习题答案_第4页
离散数学第九章图的道路与连通习题答案_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

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

文档简介

习题十1设G是一个(n,m)简单图，证明：mCn2,等号成立当且仅当G是完全图。证明：已知G是简单图，每对结点间最多一条边，故mCn2。其次，当G是完全图时，每对结点间都有一条边，即m=Cn2,反之亦然。,证明：在不少于2人的一群人中，至少有2个人这群人中有相同数目的朋友。证明：可转化为图论问题，以人为结点，如果2人是朋友关系，就对应的2个结点之间连一条边。问题转化为求简单图G中有至少2个结点度相同。如果不是如此，n个结点的度只能在0,1,2,n-1中取值，但0度和n-1度不能共存，因此，要么是0,1,2,n-2，要么是1,2,n-1。据抽屉原理，必有至少2个结点的度相同。,证明：在(n,m)图中，2m/n证明：对任何vV，d(v),d(v),即n2mn，即2m/n,习题十4,习题十6,设G是(n,m)简单二部图，证明：mn2/4证明：这个二部图两部结点数分别设为k和n-k,其边数m(n-k)kn2/4,若GG，称G是自补图。确定一个图为自补图的最低条件；画出一个自补图来。解：若GG，n阶图G的边数应为Kn边数的一半，即m=n(n-1)/4,一个图为自补图的最低条件可设为结点数须为4k或4k+1。例如：当k=1时：,习题十9,判别图中两图是否同构，并说明理由。解：两图不同构。因为如果同构，两图中唯一的3度结点应对应，但左图3度点的邻接结点度数分布是2，1，1，而右图的为2，2，1，不对应。,习题十10,若U和V是图G中仅有的两个奇数度结点，证明U和V必是连通的。证明：如果U和V不连通，则应各属一支，但此时它们所在支只有唯一的奇数度结点，与图论基本定理推论矛盾。,习题十15,证明：G是二部图当且仅当G的回路都是偶长回路。证明：（）当G是二部图时，设其二部划分为，则任何起于X部结点的回路应是C=x1y1x2y2xkykx1的形式，其长度为2k，即是偶长回路。（）当G的回路都是偶长回路时，设G连通，任取定一个结点u，构造集合X=xV且x到u的最短道路长度为偶数Y=V-X首先，uX，所以X，其次，X中无邻接结点，否则设x1x2E，则可得出G中存在奇长回路，矛盾。同理可证Y中无邻接结点。即是G的二部划分。,习题十16,设G=（V，E）是点度都为偶数的连通图，证明：对任何vV，(G-v)d(v)证明：设G-v有k支，G1G2Gk，则每支和v至少有2边相连，所以(G-v)d(v),习题十19,求出图的邻接矩阵、可达矩阵、强分图和关联矩阵。,解：邻接矩阵A=可达矩阵P=PPT=所以强分图有：a,b,c,d,e,f,g,0101000001010011001000010000000000000001010000110,1111100111110011111001111100000000000001110000111,1111000111100011110001111000000010000000110000011,abcd
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论