资源预览内容
第1页 / 共50页
第2页 / 共50页
第3页 / 共50页
第4页 / 共50页
第5页 / 共50页
第6页 / 共50页
第7页 / 共50页
第8页 / 共50页
第9页 / 共50页
第10页 / 共50页
亲,该文档总共50页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
离散数学习题集第五章 图与子图2、设G(p,q)是简单二分图 求证: 。 3、设G(p,q)是简单图,求证:qp(p- 1)/2,在什么情况下, q=p(p-1)/2? 证明:因 是简单图。所以G中任意两颗点 之间最多只有一条边。故 。l当G为完全图时,有q=p(p-1)/2 。4、试画出四个顶点的所有非同构的简 单图. l共有11个。即5、证明图5.14中的两个图是同构的, 图5.15 中的两个图不是同构的.试问,图5.16中的两 个图是否同构?agfhebdcji1. 令 ,l(2)如下图,若(a)与(b)同构,则对任何双射,l必有 。于是推得l但d(b) d(v),故(a)与(b)不同构。bedacwxvyu(3)下面两个图是同构。令 , fgabcde6、设G(p,q)是简单二分图,且 , 求证 .lG , 且 l于是|E(G)|=p(p-1)/4。l显然|E(G)|是整数。于是P或P-1是4的倍数。l 因此, 或 。或7、构造一个简单图G,使得 .l如下图,令 ,l 则有 . 8、求证:对任何图G(p,q),有:l而ll因此l即9 、设G(p,q)是简单图,p2.求证:G 中至少有两个顶点的度数相等.证明:假设G(p,q)中任何顶点的度均不相等, 则p个顶点的 度分别为0,1,2,p-1。 (1)设 ,则 中存在孤立点 ;(2)设 ,则 中无顶点v 满 足 ,此与(1)矛盾。总之,0和p-1不能同时出现。由抽屉原理知,必有, 使 。10、求证:在图G(p,p+1)中,至少有一个顶 点v,满足d(v) 3.证明:若对任意 ,均有 ,则有即 , 也即 。 从而 ,矛盾。故存在 , 使 。11、求证:在任何有n(n2)个人的人群中,至 少有两个人在其中恰有相同个数的朋友.l证明:作一个n阶简单图,n个顶点分别表示n个 人。两个人是朋友当且仅当表示这两个人的顶点 邻接。这样,问题就转化成中至少有两个顶点的 度数相等。此结论题9已证。12、求证:每一个p阶简单图G,都与Kp的子图同构.证明:因任何一个P阶简单图GKp。又 。故结论成立。13、求证:任何完全图的每个点导出子图仍 是完全图.l证明:由点导出子图的定义及完全图的结构即知 结论成立。14、求证:二分图的每个顶点数不小于2的子 图仍是二分图.l证明:设 ,且 。 令 , 显然 , 且 。因此 。15、设G(p,q)是简单图,整数n满足1 p 1,则G 中必含回路;证明:设 。若G不含回路,则必有 满足 。于是 仍连通且无回路,而 恰有 条 边。如此下去, 连通无回路且 恰含 条边,一个顶点 ,此时 是一个平凡图。从而 即 。此与 矛盾。故G必含回路。16.(3)设G(p,q)是连通图,求证:若q = p 1,则G至少有两个悬挂点. 证明:设 ,若对任何 ,均有 , 则 ,即 。 此与 矛盾。 故G中至少有一个悬 挂点.。又若G中最多只有一个悬挂点,则即 。 从而得出 (矛盾)。故G中至少有两个悬挂点。 17、求证:若边e 在图G的一条闭链中,则e 必 在G 的一条回路中.证明:设 ,G中含e的闭链为 。若E不是回路,则必有 。(因为回路定义是 :没有重复点) 从E中去掉 ,得到仍为闭链。如此下去,就可得到含 的回路 。18、求证:对于图G(p,q),若 ,则G中必 含回路.证明: G中无悬挂点。任取 ,设v1与v0邻接 。如此下去,可得G中的一条链 又因G是有限图,由此可得一条闭链,由第题的 证明过程可知,故此链上必有回路。19、设G(p,q)是简单图,且 , 求证:G是连通图.证明:若G不连通,则可将V(G)划分成V1,V2,使 得V1中的顶点与V2中的顶点不邻接。令 , ,于是, ,且( )即矛盾!故连通。另解:l考虑 。则有l(因为p(p-1)/2是完全图的边数)即 不连通,于 是,G 连通。 20、对于 p 1,作一个 的非连 通图 . 证明:令 。作如下 ,故G不连通。21、(1)证明:若 (p,q) 是简单图,且 ,则G 连通.证明:(1)设 。 若G不连通,则G的顶点可划分成两个集合 ,使得V1与 V2中的顶点互不邻接。不妨设 ,则 。 由G是简单图知,( 因为 ) 从而 矛盾。故G必连通。21、(2)当p 为偶数时,作一个非连通的k 正则简单图,其中 l取p=6。则 。l作非连通图G如下:22、证明:若eE(G),则证明:因G的任意一条边e最多联结G-e的两个分支 。故 23、证明:对图G中任意三个顶点u,v和 w, d(u,v)+d(v,w)=d(u,w) 。证明:若 d(u,v)+d(v,w)d(u,w),则与距离的概念不符。(因为距离的定义是:连 接两点之间的最短路径的长度) 故结论成立。 24、设G是简单连通的非完全图,求证:G中存 在三个顶点u,v和w,使uv,vwE(G),但uw E(G)。证明:反证法。若不然,即对任意的 ,只要 , 就有 ,也即且 . (1 )今任取 。由G连通知,存在 -通 路:于是由(1)可知:且且且 从而推得简单图G中任何两个顶点均邻接,即G是 一个完全图。此与题设矛盾。 25、证明:若G是简单图,且 ,则G中有 一条长度至少是 的回路.证明:不妨设 连通(否则可对其分支进行讨论)。 于是 ,即G中至少有 个顶点。设 是G中的一条极长通路,则v1不与P 以外的任何顶点邻接。(如果存在就与P是极长通路矛盾 )又因 。所以存在P上的 个顶点均与v1邻接。于是有回路 ,显然 。26、求图5.17的关联矩阵和邻接矩阵.邻接矩阵为:=1101101101021120 )(43214321vvvvvvvvGA27、设G是简单图,M(G)和A(G)分别是G的关联矩阵和邻接 矩阵.(1)求证: M(G)中每列各元素之和为2.(2)A(G)的各列元素之和是什么? (1)证明:因每条边 恰与两个端点u,v关联 ; (2)若 上无环,则 所在列(行)各元素之 和为 ,否则 所在列(行)各元素之和为 。 28、设G是二分图,求证:可以将G的顶点作适当排 列,使得G的邻接矩阵M(G)形如 其中:A21是A12的转置. 证明:因为G是二分图,所以G中无环,设 。令则 其中;且 。29、设G是一个图 (1)如何从 得到 和 ? (2)如何从 得到 ?解:(1)对每个 ,将 中 所在列的元 素全置为0,则得 ; (2)对每个 ,将 中 所在行的元素 全置为0,则得到 ; (3)对每个 ,将 中 所在行与列的 元素全置为0,则得到 ;30、在图5.18中,找出从U1到各个顶点的最 短通路长度,并给出从U1到U11的最短通路. 迭代 W D2 D3 D4 D5 D6 D7 D8 D9 D10 D11初始 1 2 8 1 1 1,4 4 2 8 10 2 1,4,2 2 8 3 10 3 1,4,2,5 5 8 6 10 5 12 4 1,4,2,5,8 8 8 6 10 12 145 1,4,2,5,8,6 6 7 10 12 146 1,4,2,5,8,6,3 3 9 12 147 1,4,2,5,8,6,3,77 12 10 148 10 10 11 149 9 9 13l最后得D2=2,D3=7,D4=1,D5=3, D6=6,D7=9, D8=5,D9=11,D10=10 ,D11=13。l其中U1到U11的最短通路为:I 2 3 4 5 6 7 8 9 10 11 Pi 1 6 1 2 5 3 5 10 7 931、求图5.19所示的图G中任意两个顶点的 最短通路长度,并给出从V1到V3的最短通路. l其中V1到V3的最短通路为: 。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号