组合数学与图论复习题及参考答案

组合数学与图论复习题及答案1 Show that if n+1 integers are chosen form the set 1,2, ,2n,then there are always two which differ by at most 2.从1,2, ,2n中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到2n之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k大的另一个数。2 Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100. 设52个整数a1，a2，a52被100除的余数分别是r1,r2,r52，而任意一个数被100除余数为0，1，2，99，一共100个。他们可以分为51个类0,1,99,2,98,49,51,50。将这51个集合视为鸽笼，则将r1,r2,r52放入51个笼子中，至少有两个属于同一个笼子，所以要么有rirj，要么有rirj100，也就是说aiaj|100或者aiaj|100。3 从1，2，3，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。 鸽子洞原理，必有两个数相邻，相邻的两个数互质4 Prove that Ramsey number R(p,q)R(p,q-1)+R(p-1,q).令NR(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。在剩下的R(p,q-1)+R(p-1,q)21个人中，由鸽子洞原理有，或者F中有R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)R(p,q-1)+R(p-1,q)5 There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。从10人中随意选一个人p，F表示与p相识的人，S表示与p不相识的人若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6 In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats?6个男的先进行圆排列，然后6个女的插入空位。7 In how many ways can 15 people be seated at round table if B refuses to sit next to A? What if B only refuses to sit on A right?A15个人进行圆排列，减去ab组成一个元素的14人的圆排列，然后减去ba组成一个元素的14人的圆排列。B15个人进行圆排列，减去ab组成一个元素的14人的圆排列。8 Determine the number of 10-combinations of the multiset S=*a,4.b,5*c,7*d。 (1+x+x2+x3+)( 1+x+x2+x4) ( 1+x+x2+x5) ( 1+x+x2+x7)展开9 把n个有编号的球放入m个有编号的盒子中，不允许有空盒子，有多少种放法。先假设，盒子没有编号，然后乘上组合与排列的关系： 10 证明在n（n2）个人中总有两个人，他们在这群人中所认识的人数目相同。当n2时，如果两个人相互认识，则每个人认识的人只有一个；如果不认识，则每个人认识的人为0个。当n2时，设xi (x=1,2,n)表示，第i个人认识的人的数目。（每个人最多只能认识n-1个人。）A 如果每个人都有熟人那么由鸽子洞原理知道至少有两个人i和j认识的人数相同即xixjB 如果只有一个人没有认识的人那么对于剩下的n1个人来说能认识的人对多只有n2个，由鸽子洞原理知道，这n1个人中至少有两个人i和j认识的人数一样即xixjC 如果至少有两个人都没有熟人，则满足题设。11 一个剧团演出11周，为保证收入和不至于太累，规定每天至少演出一场，每周不超过12场。证明存在连续的若干天，恰好演出21场。设a1为第一天该剧团的演出的次数，ai表示前i天一共的演出次数。可知道ai是单调递增的。且有a1=1,a77=132。于是有ai21(i=1,2,77)，也是单调递增的。而a7721=n。两堆石头关系等价，所以下面以第一堆为参照。A 考虑第一堆石头都集中在k类集合里面（除去单出来的石头外，其他石头都两两在一起）。此时如果第二堆石头里面有分布在k类集合中的元素，则肯定有满足题意的来自两堆石头的两块石头；如果先让第二堆石头分布满在其他的k个集合，因为每堆中石块重量不同，那么现在一共有n1或n2块石头分布在集合中，第二堆就多出了1或2个石头，那么这1或2个石头肯定是在前面的k个集合中，所以这也有满足题意的两块石头。B 如果第一堆石头分布在i（i从k到p）个集合中，同样，显然第二堆石头分布满剩下的i个集合，由于每堆中石块重量都不一样，所以第二堆将会多出q2*i2*块石头，那么这些多出来的石头，肯定会分布在第一堆石头所在的i个集合中，所以有满足题意的两块石头。17 在9个人中，或者有3人相互认识，或者有4人相互不认识。N(3,4) = N(2,4)+N(3,3) 因为N(2,4)和N(3,3)都为偶数，所以有：N(3,4) 1f(1)=C n=1 设n=2k,C为常数f(n)=2f(n/2)+C2f(n/2)=4f(n/4)+2C4f(n/4)=8f(n/8)+4C2k-1(n/2k-1)=2kf(n/2k)+2k-1C将上面的各等式，左右相加得：f(n)=C+2C+2k-1C+2kf(n/2k)= C+2C+2k-1C+2kC=C*(2K1-1) H(n)=4H(n-1)-4H(n-2) n1 H(0)=0，H(1)=1特征方程为x2-4x+4=0解为二重根：q1=q2=2通解表示为：Hn=C1*2n+C2*n2n由H(0)=0，H(1)=1有： C1+0*C2=0 C1*2+C2*2=1解得:C1=0 C2=1/2Hn=n*2n-1 26. 在r位二进制序列里，使数字0不相邻的序列有多少个（用递推方程）？ 前一位的0和1都会允许后一位为1，前一位为1后一位允许为0。所以设f(x)表示x位的满足条件的序列的个数，有：f(x) = f(x-1)+f(x-2) /f(x-1)表示f(x)中第x位为1的序列数/f(x-2)表示f(x)中第x位为0的序列数f(1) = 2f(2) = 3Fn27Kn=是n 个结点的完全图，G1=和G2=是Kn的子图，且E=E1E2，E1E2=。 证明n11,若G1是平面图，则G2不是。 证明G1和G2必有一个是连通图。假设G2也是平面图。那么有e1=3n-6,e2=3n-6，所以有e=2(3n-6)。因为Kn是完全图所以有en*(n-1)/2，所以有n*(n-1)/2=2(3n-6)，n2-13n+2411时，不等式不成立，所以当n11时，由假设得出得结论是不成立得，所以假设不成立，所以若G1为平面图，G2肯定不是平面图。化简得： 假设两个图都不是连通图。有e1=n-2和e2=n-2成立从而有e=2(n-2)。因为Kn是完全图所以有e=n*(n-1)/2，所以有n*(n-1)/2=2n-4，解得n25n80，所以矛盾，所以必有一个图是连通图。28. Let G be a planar graph of order n in which every vertex has the same degree k. Provw that k5. （,e=3r）所有点度的和应该是边数的2倍，即。由题意由G的，那么由nk2e，对于平面图我们有e=3n-6，所以有nk=6n12，k=6-12/n，因为k为整数，所以有k(G)。设a点时G中度最小的点，那么(G)就是与a相连的边数，将与a相连的边全部去掉，那么G就不在连通，所以(G)(G)是不可能成立的。所以有(G)(G)。证(G)(G)：若(G)1，即只需要去掉一条边G就不在连通，此时记这条边为e这条边的两个端点记为V1和V2，则e是这个图的桥，此时有(G)1，所以(G)(G)成立。若(G)=2，此时若去掉(G)条边G就不连通了，如果只去掉(G)1条边，则会产生一个桥e(u,v)。对于(G)1条边中的每一条边，都删去一个不同于u，v的点，则至少删去(G)1条边。若这样产生的图是不连通的则有(G)(G)1(G)；若仍连通则产生桥e(u,v)，删去u或者v G也不在连通，此时(G)=n，所以G一定有H路径。设此路径为V1,V2,Vn。若V1和Vn相邻接，则构成H回路。若V1和Vn不相邻接。假定V1邻接于Vi1，Vi2，。，Vik(2=Vik=n-1)，则Vn必邻接于Vi1，Vi2，。，Vik中一点。若Vn与Vi1，Vi2，。，Vik都不邻接，那么Vn至多邻接n-k-1个点邻接即d(Vn)=n-k-1，而d(V1)k，那么有d(V1)+d(Vn)=n-1,与题设矛盾。所以Vn必与Vi1，Vi2，。，Vik中一点邻接，从而构成H回路。 。 。 。 。V1V2ViVn32. Prove that a graph G is bipartite if and only if each of its cycle has even length.二分图定义：G的点可以可以分成互不相交的两部分X，Y。如果一条边是两个集合间的边，那么肯定一个点是X另一个点是Y的；没有一条边是一个集合中的边，两个点都属于一个集合X或者Y的。A如果G有奇数长度的回路那么，肯定会有如图所示子图的情况：XY。 。x1。y1 。z此时|E|为奇数，|V|也为奇数。若z是属于X集合的点，那么对于边e(x1,z)，x1和z都属于X，这个与定义不符。若z属于Y，同样不满足。B若每个回路长度都是偶数，那么每个回路肯定会有这种结构。XY。 。x1。y1。此种情况是满足定义的。C对于非回路，可以把每个隔点，归于一类，这样也可以满足定义。33Prove that the second Stirling number satisfies a recurrence relation S2(n,k)= kS2(n-1,k)+ S2(n-1,k-1)第二类stirling数S2(n,k)的意义是将n个有编号的球放入k个无编号的篮子中的放置方法数。假定，我们将第n号球先取出来单独放置。A 如果第n号球单独占用一个篮子，那么就是将剩下的n1个球放入k1个篮子中，有 S2(n1,k1)。B 如果第n号球没有单独占用一个篮子，那么就是剩下的n1个球放入k个篮子中，有 S2(n1,k)。第n号球可能在k个篮子中的任意一个，所以放置方法数为 K* S2(n1,k)所以得到 S2(n,k)= kS2(n-1,k)+ S2(n-1,k-1)34 A、B、C、D四台机器和1、2、3、4、5五种颜色，规定A和D不能用1和4，B不能用3，C不能用2和3，D不能用5。为每台机器恰好涂一种颜色的方案数有多少？引入第五个机器E，并且E不能涂任何颜色。12345ABCDE35 两位教师带k位同学外出，排成一列，为安全起见，规定教师必须排在队首和队尾。休息后重排，每个人都不在原来的位置的排法有多少种？试用有禁区的排列棋盘多项式求解。Dn=K!-C(K,1)(K-1)!+C(K,2)(K-2)!+(-1)KC(K,K)0!有禁区的棋盘：N=K!-r1(k-1)!+r2(k-2)!+(-1)krkK K R()=R()K=(1+x)K=以下为图片格式文档1如图所示是一张城市平面图，图中的直线表示街道，直线的交点表示街道的交叉路口，试证明从交叉路口到交叉路口共有条不同的路径可走。2.一个学生打算用37天总共60学时自学一本书，他计划每天至少自学1学时，证明：无论他怎样安排自学时间表，必然存在相继的若干天，在这些天内其自学总时数恰好为13学时（假定每天自学学时数为整数）。4.某校有120名学生参加数学竞赛，竞赛试题共有甲，乙，丙三题竞赛结果为：12名学生三题全对；20名学生只做对了甲题和乙题；16名学生做对了甲题和丙题；28名学生做对了乙题和丙题；48名学生做对了甲题；56名学生做对了乙题；16名学生三