离散数学[刘任任版]第5章答案.pptVIP

离散数学习题集;2、设G（p,q）是简单二分图求证： 。 ;3、设G（p,q）是简单图,求证:q≤p(p-1)/2，在什么情况下, q=p(p-1)/2? ;4、试画出四个顶点的所有非同构的简单图. ;5、证明图5.14中的两个图是同构的, 图5.15中的两个图不是同构的.试问,图5.16中的两个图是否同构?;1.?????? 令 ， ;（2）如下图，若(a)与(b)同构，则对任何双射， 必有 。于是推得 但d(b) ≠d(v)，故(a)与(b)不同构。 ? ;(3)下面两个图是同构。令 , ;6、设G（p,q）是简单二分图，且 ≌ ,求证 .;7、构造一个简单图G,使得 ≌ .;8、求证:对任何图G（p,q）,有:;9 、设G（p,q）是简单图,p≥2.求证:G中至少有两个顶点的度数相等.;10、求证:在图G（p,p+1）中,至少有一个顶点v,满足d(v) ≥3.;11、求证:在任何有n(n≥2)个人的人群中,至少有两个人在其中恰有相同个数的朋友.;12、求证:每一个p阶简单图G,都与Kp的子图同构.;13、求证:任何完全图的每个点导出子图仍是完全图.;14、求证:二分图的每个顶点数不小于2的子图仍是二分图.;15、设G（p,q）是简单图，整数n满足1 n p – 1,求证:若p≥ 4,且G的所有n 个顶点的导出子图均有相同的边数,则 或 . ;16.(1)设G（p,q）是连通图，求证:G至少有p – 1条边; ;16.(2)设G（p,q）是连通图，求证:若q p – 1,则G 中必含回路;;16.(3)设G（p,q）是连通图，求证:若q = p – 1,则G至少有两个悬挂点. ;17、求证:若边e 在图G的一条闭链中,则e 必在G 的一条回路中.;18、求证:对于图G(p,q),若 ,则G中必含回路.;19、设G（p,q）是简单图，且 ,求证:G是连通图.;;即 矛盾！故连通。 ;另解：;20、对于 p 1,作一个 的非连通图 . ;21、（1）证明：若 Ｇ(p,q) 是简单图，且 ,则G 连通.;21、（2）当p 为偶数时,作一个非连通的k –正则简单图,其中 ;22、证明:若e∈E(G),则 ;23、证明:对图G中任意三个顶点u,v和w, d(u,v)+d(v,w)=d(u,w) 。;24、设G是简单连通的非完全图,求证:G中存在三个顶点u,v和w,使uv,vw∈E(G),但uw E(G)。;于是由（1）可知： 且 且 …… 且 从而推得简单图G中任何两个顶点均邻接，即G是一个完全图。此与题设矛盾。 ;25、证明:若G是简单图,且 ,则G中有一条长度至少是 的回路.;26、求图5.17的关联矩阵和邻接矩阵.;邻接矩阵为：;27、设G是简单图,M(G)和A(G)分别是G的关联矩阵和邻接矩阵.(1)求证: M(G)中每列各元素之和为2.（2）A(G)的各列元素之和是什么? ;28、设G是二分图,求证:可以将G的顶点作适当排列,使得G的邻接矩阵M(G)形如其中:A21是A12的转置. ;29、设G是一个图(1)如何从 得到 和 ?(2)如何从 得到 ?;30、在图5.18中,找出从U1到各个顶点的最短通路长度,并给出从U1到U11的最短通路. ;最后得D[2]=2，D[3]=7，D[4]=1，D[5]=3，D[6]=6，D[7]=9, D[8]=5，D[9]=11，D[10]=10，D[11]=13。 其中U1到U11的最短通路为： ? I 2 3 4 5 6 7 8 9 10 11 P[i] 1 6 1 2 5 3 5 10 7 9