资源描述
离散数学习题集,第五章 图与子图,2、设G（p,q）是简单二分图求证： 。,3、设G（p,q）是简单图,求证:qp(p-1)/2，在什么情况下, q=p(p-1)/2?,证明：因 是简单图。所以G中任意两颗点之间最多只有一条边。故 。 当G为完全图时，有q=p(p-1)/2 。,4、试画出四个顶点的所有非同构的简单图.,共有11个。即,5、证明图5.14中的两个图是同构的, 图5.15中的两个图不是同构的.试问,图5.16中的两个图是否同构?,a,g,f,h,e,b,d,c,j,i,1. 令 ，,（2）如下图，若(a)与(b)同构，则对任何双射， 必有 。于是推得 但d(b) d(v)，故(a)与(b)不同构。,b,e,d,a,c,w,x,v,y,u,(3)下面两个图是同构。令 ,f,g,a,b,c,d,e,6、设G（p,q）是简单二分图，且 ,求证 .,G , 且 于是|E(G)|=p(p-1)/4。 显然|E(G)|是整数。于是P或P-1是4的倍数。 因此， 或 。,或,7、构造一个简单图G,使得 .,如下图，令 ， 则有 .,8、求证:对任何图G（p,q）,有:, 而 因此 即,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)个人的人群中,至少有两个人在其中恰有相同个数的朋友.,证明：作一个n阶简单图，n个顶点分别表示n个人。两个人是朋友当且仅当表示这两个人的顶点邻接。这样，问题就转化成中至少有两个顶点的度数相等。此结论题9已证。,12、求证:每一个p阶简单图G,都与Kp的子图同构.,证明：因任何一个P阶简单图GKp。又 。 故结论成立。,13、求证:任何完全图的每个点导出子图仍是完全图.,证明：由点导出子图的定义及完全图的结构即知结论成立。,14、求证:二分图的每个顶点数不小于2的子图仍是二分图.,证明：设 ，且 。 令 ， 显然 ， 且 。 因此 。,15、设G（p,q）是简单图，整数n满足1 n p 1,求证:若p 4,且G的所有n 个顶点的导出子图均有相同的边数,则 或 .,证明：若 和 均不成立， 则存在 使得u与v邻接，而w与x不邻接。 于是取 n=2 ，则 与 边数不相同，矛盾。 故 或 。,16.(1)设G（p,q）是连通图，求证:G至少有p 1条边;,证明：对p用归纳法 a) p=1时，显然成立。 b) 假设对于小于p的自然数，结论成立。 c）在p阶连通图中任取一个顶点v。设G-v共有k个分支，且每个分支有Pi个顶点， PiP, 。 于是由归纳假设可知GVi至少有Pi-1条边， ， 从而G-v至少有(P-1)-k条边。故G至少有P-1条边。,16.(2)设G（p,q）是连通图，求证:若q 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中的顶点不邻接。令 ， ，于是， ，且 ( ),即 矛盾！故连通。,另解：,考虑 。则有 （因为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 正则简单图,其中,取p=6。则 。 作非连通图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的关联矩阵和邻接矩阵.,邻接矩阵为：,27、设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 14 5 1,4,2,5,8,6 6 7 10 12 14 6 1,4,2,5,8,6,3 3 9 12 14 7 1,4,2,5,8,6,3,77 12 10 14 8 10 10 11 14 9 9 9 13,最后得D2=2，D3=7，D4=1，D5=3，D6=6，D7=9, D8=5，D9=11，D10=10，D11=13。 其中U1到U11的最短通路为： I 2 3 4 5 6 7 8 9 10 11 Pi 1 6 1 2 5 3 5 10 7 9,31、求图5.19所示的图G中任意两个顶点的最短通路长度,并给出从V1到V3的最短通路.,其中V1到V3的最短通路为： 。,
展开阅读全文