图论与组合数学期末复习题含答案

组合数学部分第1章 排列与组合例1：1)、求小于10000的含1的正整数的个数；2、)求小于10000的含0的正整数的个数；解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有999916560个.含1的有：99996560=3439个2)、“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有个，2位数有个，3位数有个，4位数有个 不含0小于10000的正整数有个含0小于10000的正整数99997380=2619个。例2：从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？解：将1,300分成3类：A=i|i1(mod 3)=1,4,7,298,B=i|i2(mod 3)=2,5,8,299,C=i|i0(mod 3)=3,6,9,300.要满足条件，有四种解法：1)、3个数同属于A;2)、3个数同属于B；3)、3个数同属于C;4)、A,B,C各取一数；故共有3C(100,3)+1003=485100+1000000=1485100。例3：（Cayley定理：过n个有标志顶点的数的数目等于）1）、写出右图所对应的序列；2）、写出序列22314所对应的序列；解：1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子节点相连接的线），而与这个去掉的叶子节点相邻的另外一个内点值则记入序列。如上图所示，先去掉最小的叶子节点，与其相邻的内点为，然后去掉叶子节点，与其相邻的内点为，直到只剩下两个节点相邻为止，则最终序列为51155.。2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：112223344567。我们再将给出序列22314写在第一行，插入后的递增序列写在第二行。如下图第一行所示：。我们每次去掉第一行第一个数，并在第二行寻找第一个无重复的元素5并将它取出，将与连接起来，并在第二行去掉第一行的第一个元素，剩下的序列为1122334467，依次执行下去。最终剩下的两个元素（47）连在一起。则形成了以下的树。例4：（圆排列问题：从n个字符中取r个不同的字符构成圆排列的个数为。）5对夫妇出席一宴会，围一圆桌坐下有多少种方案？要求每对夫妇相邻而坐，方案有多少种？解：1）、此问便是考查圆排列的公式定义，由可得，排列方式有 种。2）、同样，先将5个丈夫进行圆排列则有种，再将5个妻子插到丈夫的空隙之中，每个妻子只有两种选择，要么在丈夫的左边，要么在右边。因此由种插入的方法，所以一共有种。有错误！例5：（允许重复的排列）已知重集，做重集S的全排列，问有多少中排列方案？解： 设可重复，其中，为S中k个不同元素，则S的个数为，S的全排列为：则据题意可得：方案数为。列6：（允许重复的组合）试问有多少项？解：由于，相当于从右边每个括号里取一个元素相乘，而元素可以对应相同（如4个括号我都取x）或者不同。这就相当于将4个无区别的球放进3个有区别的盒子，由于在个不同元素中取个进行组合，允许重复，则组合数为。（或者说个无区别的球放进个有区别的盒子里，每个盒子球数不限，则共有种）。问题等价于从3个元素中取4个做允许重复的组合，项。例6：（线性方程的整数解个数问题）已知线性方程，和都是整数，求此方程非负整数解的个数？解：方程的非负整数解对应一个将个无区别的球放进个有区别的盒子的情况，允许一盒多球，故原式可以等价转化为将将1到的正整数取个作为允许重复的组合，其组合数为个。例7：（不相邻的组合）从中取三个元素做不相邻的组合，有多少种方式？解：由于从中，取个作不相邻的组合，其组合数为，因此在此题中，组合数种类有种。例8：（全排列的三种生成算法）（1）、已知，求对应的序列。（2）、利用字典序法求求839746521的下一个排列。解：（1）、由于0到中的任何整数都可以唯一表示为其中，可以证明从0到的个整数与一一对应，我们要得到这些值就得每次除以与其相对应的数值，就可以得到与相对应的余数值。因为，所以：所以：。把n-1个元素的序列和n个元素的排列建立一一对应关系，从而得到一种生成排列的算法序数法。将与给出序列相对应，例如给出4213，那么对应，由大到小的计算当前数值位置右边比此位置数值大的数值的个数，例如最大的数为4，4这个数右边有3个数比它小，所以，同理，第二个大的数为3，在3这个数右边有0个比它小的数，所以，同理对应2这个数右边有一个数比他小，所以。综上所述，对应序列为。4同时，由也可以推出最大数4的右边有3个比它小的数，为：43第二个大的数3右边比他小的数的个数为0，因此，为：第三个大的数2右边比他小的数有1个，而1的位置也4213可以确定了因此为（2）、字典序法首先从序列后向前找出第一组，记下此式的值，然后有从后向前找第一个比的值大的数，并将和调换位置，然后再将原来（现在）位置以后的全部序列倒序即可以了。如题中所示的序列839746521中，首先找出从右向左第一组的，此处为4，然后找到为5，将它们两调换得到839756421，然后将5后面的数逆序得到839751246。例9：（格路模型）一场电影的票价是50元，排队买票的顾客中有位是持有50元的钞票，位是持有100元的钞票。售票处没有准备50元的零钱。试问有多少种排队的方法方法使得购票能顺利进行，不出现超不出零钱的状况。假设每位顾客只限买一张票，而且。解：在格路模型中，从的路径选择有种。因为这个问题可以看成是由个向右和个向上组成，就是一个可重复的全排列问题。当然，将这一模型推广以后就可以应用于此题了，我们将问题简化就可以得到卖票者从没有钱到把所有票都卖完，在这个期间他必须实现每次卖票成功（即有足够的零钱找给顾客）。在格路模型中，我们把x轴看成是m个100元，y轴看成是n个50元，最重要实现将这m个100元和n个50元收入囊中，而且要满足不出现找不出50元钞票的情况。问题等价于从到的路径中，找出yx且不穿越（但可以接触）y=x线上点的路径。然而不允许接触的情况是从点出发到的所有路径减去从点出发经过y=x的路径，如右图所示，由对称性以及可以知道，从出发经过y=x的路径等于由出发到达的路径，因为由出发到达必须经过y=x。所以，原问题可以转化为：路径数=。然而，此处是可以接触y=x的，因此我们可以将纵坐标向下移动一个单位如右图所示：即可以接触y=x但是不可以穿过y=x-1。此时相当于从到点减去从经过y=x-1到点的路径，而这一路径与从到的路径数相等，所以路径数=。例10：（若干等式及其组合意义）分别解释下列组式子的组合意义。1）、即；2）、即；3）、；4）、即;5）、；6）、；7）、；解：1）、即这个式子可以被看作是格路模型的应用，从到达在个格子上面先走个格子，剩下再走个格子，这个和先走个格子，再走个格子是一样的。2）、即，这个式子组合意义之一便是格路模型中的意义，从到的路径数可以被看成是，从到的路径数可以被看成是，从到路径数可以被看成是。就是说我们从出发都是必须先经过或再到达的。还有一种模型便是从含有的个数中取出个数有几种取法的问题，首先我们将取得的数分为两类：一类是取得的数中含有，一类是不含有，因此，含有的有种取法（先将取出，再从剩余的个数中取个）。不含有的有种取法。因此。3）、，运用上题中的模型即可。4）、即，左边相当于从n个小球中取出个小球，再从个小球中取出r个，右边相当于从n个小球中先取出r个小球,由于这里面有重复度为，它等于从剩下的个小球中取出个小球，这样一组合就相等了5）、，二项式模型。等式右边为将m个无区别的球放入2个有区别的盒子，左边表示其中一个盒子分别装有0个，1个，m个球的组合数纸盒。6）、；二项式定理，当时，=0。7）、，等式左边相当于在有个红球和个蓝球混合后从中取出r个球，等式右边相当于在取得的r个球中有0个红球和r个蓝球，一个红球和个蓝球，r个红球和0个蓝球。第2章 递推关系与母函数例1：（母函数与递推关系）利用母函数法求解满足递推关系的Fibonacci序列的解。解：首先，我们根据题意设母函数为，则：由可得：。令，解得。因此，令，则，由可得，=。因此，递推关系式为，由于，所以，即，。例2：（Fibonacci序列的若干不等式）（1）、证明：；（2）、证明：；（3）、证明：；证：（1）、由于序列为Fibonacci序列，所以有：，因此： ， ，所以，。（2）、由于序列为Fibonacci序列，所以有：，因此：， ，所以有。（3）、由于序列为Fibonacci序列，所以有：，因此：，,，即。例3：（线性常系数齐次递推关系）（1）、求解Fibonacci数列的递推关系。（2）、求数列的递推关系。解：（1）、由原式可得特征方程为，特征根为，所以，由定理可得。又由可得，带入上述式子可得：。（2）、有原式可得特征方程为，特征根为，所以，由定理可得。由初值条件可以得到：，故递推关系式为：。例4：（线性常系数非齐次递推关系）（1）、求的递推关系。解：（1）、由题意可得，此题为线性非齐次递推关系的求解，我们可以将表示为齐次部分的通解加上特解，即，其中为特解，为通解。对于其次部分，其特征多项式为，解得特征解为，我们设，所以，又因为，则可以得出，我们设，那么由题意可得，将此式带入原式可得，则解此式可得。由可得，又由可以得到解得，所以。说明：若为的一个特解，为 的一个通解，则原非齐次递推关系的通解。 有以下结论：、若为的次多项式，则，其中为待定系数；若导出的常系数线性齐次递推关系特征根为1的重根，则。、若为的形式，若是导出的常系数线性齐次递推关系的重特征根，为的次多项式，则。 例5：（指数型母函数问题）对于序列定义为序列的指数型母函数。几个具有代表性的指数型母函数：（1）、序列的指数型母函数为：（2）、序列的指数型母函数为：（3）、序列的指数型母函数为：（4）、序列的指数型母函数为：若有8个元素，其中设重复3次，重复2次，重复3次。从中取个组合，其组合数为多少？解：设的母函数为：=。对应当时，即从中取一个进行排列，排列数为3，当时，即从中取4个进行排列，排列数为70。例6：（整数的拆分问题）若有1克的砝码3枚，2克的4枚，4克的2枚，问能称出哪些重量？各有几种方案？解：由题意可得，我们设，其中第一项表示1克砝码3个，第二项表示2克砝码2个，第三项表示4克砝码2个。借出这个多项式可得：那么比如能称出11克的方法就有5种，因为。例7：（Stirling数问题）个有区别的球放到个无区别的盒子中,要求无一空盒,其不同的方案数用表示,称为第二类Stirling数。即是将个数拆分成非空的个部分的方案数。Stirling数具有以下几点性质：1）、；2）、；3）、；4）、；5）、；6）、；7）、；8）、；9）、以上式子的证明都可以用Stirling数的定义来证明，详见教材。个球放到个盒子里，依球和盒子是否有区别？是否允许空盒？共有多少种状态？其方案计数分别列于下表。编号个球个盒子是否空盒方案个数有区别有区别有空盒有区别有区别无空盒有区别无区别有空盒有区别无区别无空盒无区别有区别有空盒无区别有区别无空盒无区别无区别有空盒的项系数无区别无区别无空盒的项系数解释：、当我们认为盒子无区别的时候，由Stirling数的定义可得有种组合。然后，将个盒子进行全排列，共有种全排列，因此全部的排列数为。、对于无区别盒子有空盒情况的全排列，我们可以转化为无区别盒子无空盒的情况解决。即将非空盒数分为1个非空、2个非空、个非空的各种情况的加和的情况。因为盒子无区别，所以不用考虑空盒子的情况。表示只有1个盒子非空，表示只有2个盒子非空，表示只有个盒子非空，当然，这是球数大于盒子数量的结果，当球数小于盒子数时，由性质2）可以得到最大的情况就是个盒子不为空，为，综上所述，方案数为种。、由Stirling数的定义可得。、这个模型可以转化为从个元素中取个元素（允许重复抽取）做允许重复的组合，则可以得出组合数为。、我们的目的就是要将个球放入个有区别的盒子。首先，我们将个球排成一列，1之间共有个空隙，然后我们用隔板法将这列小球分成部分，而要将球分成部分，我们只需要块隔板就可以了，问题就转化为将块隔板插入个缝隙共有多少种插法，由分析可得有种插法。、此模型可以转化为整数拆分模型，目的就是将个无区别的球拆分成等数的和的问题，所以母函数，转化后即得出的项系数即为整数的拆分。、此模型也可以转化为整数拆分模型，首先，我们从个球中选取个球放进盒子里面，保证每个盒子里面有一个球，这只有一种方法。然后将剩下的个无区别的球拆分成等数的和的问题，但是此处是取其中项的系数，所以母函数，当然，如果仍然想取项系数，我们将上式转化后即得出的项系数即为整数的拆分，再乘以从个球中选取个球放进盒子里的方法数1。第三章 容斥原理例1：（容斥原理的基本定义）（1）、一个学校只有三门课程：数学、物理、化学。已知修这三门科的学生分别有170、130、120人；同时修数学物理两门课的学生有45人；同时修数学、化学的20人；同时修物理、化学的22人；同时修三门科的学生3人。问这学校有多少学生？（2）、把n本不同的书放入m个有编号的箱子中去（nm)，使得没有一个箱子为空。共有多少种方法？解：（1）、设为修数学这门学科的学生集合，为修物理学科学生的集合，为修化学这门学科的学生集合。则根据题意可得，。则根据容斥原理的定义可得在校生人数为： =170+130+120-45-20-22+3=336。（2）、对应于个小球放入个盒子模型中的第种。但是，此处我们用容斥原理来解决。首先，对应于原题条件，我们用表示盒子允许为空的放球放法数，然后用表示第个盒子为空的情况，那么表示所有盒子都不为空的情况，由容斥原理可得：例2：（有限制条件的排列）从（0,0）点到（10,5）点的路径中，求不能过AB，CD，EF，GH的路径数，其中A（2,2），B(3,2)，C(4,2)，D(5,2) E(6,2),F(6,3) ,G(7,2),H(7,3) 。解：如右图所示，从左往右依次是、，由题意可得，我们要求得是从到的路径数，即可表示为：,由容斥原理可以的出： 根据格路模型可以知道，经过路径可以被认为先从到的路径数再乘上从到的路径数,那么，由此可得：。则，=3003-720-840-420-360+336+90+60+900+150+0-80-60-0+0=2049，因此，共有2049种路径（仅供参考）。第四章 鸽巢原理例1：（鸽巢原理的证明：只鸽子，个巢，则至少有一个巢不少于只鸽子）（1）、证明：若把个物体放到个盒子中去，则至少有一个盒子放有至少2个物体。（2）、证明：若在一个集合中存在个不相同的元素，那么在中至少可以找出一组由个元素组成的或未单调递增或者单调递减的子序列。证明：（1）、用反证法证明。如果n个盒子中每个盒子至多放入一个物体，则放入n个盒子中的物体总数至多为n个。这与假设有n+1个物体矛盾。从而定理得证。（2）、我们从集合中选取一个元素，再向后找比大的元素，直到后面再也没有比它前一个元素还大的元素为止，例如，有一个序列如下：5,3,16,10,15,14,9,11,6,7从中可以找出不同的单调递增序列，例如：5,16；5,10,15；3,9,11；3,6,7或者是单调递减的序列，例如：5,3；16,10,9,6；16,15,14,11,7我们设中每一个元素都有若干个单调递增的子序列，但其中有一个最多的子序列，设这个子序列的元素个数为，于是得到序列，当序列某一个元素，则已经符合要求，否则，设序列中不存在超过个元素的单调递增子序列，即：，这就相当于把个小球放到个盒子中取，由于此处，则共有种。例2：（Ramsey二染色定理）设a、b为正整数，令R(a,b)是保证a个人彼此认识或b个人彼此不认识的所需最少人数，则称R(a,b)为Ramsey数。R(3,3)=6；R(4,3)=9；R(3,4)=9；R(4,4)=18。注：这些定理只给出了几个Ramsey数的上界，并不一定是最好的结果。证明：6个人中一定有3个人相互认识或相互不认识。证明：（1）、这类问题其实就是Ramsey二染色问题。如右图所示，在六个人中，对于某个人，要么他与别人相互认识、要么互不相识，所以存在这两种情况。我们将另外的五个人分为Friend和Stranger两个集合，那么：Friend=其余5个人与A互相认识的集合；Stranger=其余5个人与A不互相认识的的人；依据鸽巢原理，在Friend集合或者Stranger集合里至少有3个人，假设是在Friend集合里有3个人分别是B、C、D，那么依据鸽巢原理可得在这个Friend=5的集合中，至少有个人相互认识或者不认识，如果3个人互相不认识，那么满足题意“至少有3个互不认识”，否则其中两个人B、C相互认识，又因为A与Friend集合里面的人互相认识，所以至少有A、B、C相互认识。同理，对于Stranger集合也是一样的。图论部分第五章 图的基本概念例1：（图的定义）一个图定义为一个偶对，记作，其中：（1）、是一个集合，其中的元素称为顶点；（2）、是无序集到中一个子集合，气元素称为边，其中的元素可在中出现不止一次。二部图(二分图)：设和是的顶点子集 ，使=，且的每条边的一个端点在中，另一个端点在中，则称为二部图，记。完全二部图：如果中的顶点和中的每一个顶点都邻接，则称为完全二部图，记为Kn,m。补图：设为完全图，为简单图，其中，则称相对于互为补图，记。生成子图：设图，一个满足（1）、；（2）、；的真子图，叫做G的生成子图（spaning graph）（条件：点同边少）。途径点、边可相同闭链边不同回路(闭链)道路点不同圈对于途径（其中表示顶点，表示两顶点之间相连的边），若其中均不同，则称为链（chian）。所有顶点均不相同（从而所有边都必然不相同）的路径称为道路（path）。一条封闭的道路成为圈（cycle）。设是图中的两个顶点,若中存在一条道路,则称顶点和是连通的（connected）.如果图中每一对不同的顶点间都有一条道路,则称图是连通的.若以表示顶点与是连通的，那么这种顶点间的连通关系是一个等价的关系，即：1）、（反身性）；2）、，则（对称性）；3）、则（传递性）；每一个等价关系确定一个类，这些类称为的连通分支或简称为分支 (compouent)，分支的个数记为。环和(ring sum)： 在和的并中去掉和的交所得到的图，即环合运算满足交换律和结合律。第六章 树例1：（破圈法和避圈法）给定图T，以下关于树的定义是等价的。1)、无回路的连通图。2)、无回路且其中是边数，是结点数。3)、连通且。4)、无回路，但增加一条新边，得到一个且仅有一个回路。5)、连通，但删去任一边后便不连通。6)、每一对结点之间有一条且仅有一条路。如果图中删去一条边后，图的分支数增加，则称此边位的割边(cut-edge)。如果图中去掉一个顶点（同时去掉与该点关联的所有边）后图的分支数增加，则称该点为G的割点(cut-vertex)。图有生成树的充分必要条件是图是连通的。任何连通图至少存在一棵生成树.设阶无向连通图有条边,则。设阶无向连通图有条边,是的生成树,是的余树,则中有条边.（1）、利用“破圈法”求出图的一个生成树。（2）、利用“避圈法”求出图的一个生成树。解：（1）、所谓“破圈法”，就是先在图中找出一个圈，然后再去掉圈中的一条边，使其破开，如右图所示，先在图中找一个圈，然后又将其中的去掉，在余下的图中，再取一个新圈，然后又将去掉，在余下的圈中，取新圈，然后再在余下的圈中去掉，最后再将余下圈中的也去掉，此时剩余的图中不含圈，那么这个生成树就生成出来了。（2）、所谓“避圈法”，就是避免在生成树的过程中产生圈，因此，我们以为起始点开始找出与不构成圈的边，因此，接着取、，这样再也找不出不能产生圈的生成树了，因此，最终结果就是、。第七章 欧拉图和哈密顿图例1：（环路）环路（cir）是圈与圈的边不重并。圈是环路，圈是连通的，环路不一定连通。闭链是环路。环路中每个顶点的度均为偶数。图G是连通环路当且仅当存在一条包含G的所有边的闭链。每个顶点的度为偶数的图G是环路。环合： 例2：（欧拉图）顶点的度均为偶数的图称为欧拉图(Euler graph)。（图中存在经过所有顶点、所有边的闭路径，此图称为连通欧拉图。）结论：1）、闭链是欧拉图；2）、环路是欧拉图；3）、图G是连通欧拉图当且仅当存在一条包含G的所有边的闭链；4）、两个欧拉图的环和仍是欧拉图。无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。无向图G为欧拉路径(非欧拉图)，当且仅当G连通，并且恰有两个顶点的度是奇数。例3：（哈密顿图）图G称为哈密顿图（Hamilton graph），如果G上有一条经过所有顶点的回路（也称这一回路为哈密顿回路或者哈密顿圈）。称无向图有哈密顿通路(非哈密顿图)，如果G上有一条经过所有顶点的通路(非回路)。设G是阶简单图，是有最小度的顶点，如果，则G是哈密顿图。设是阶图中两个不邻接的顶点，如果，则是哈密顿图的充要条件是为哈密顿图。设为一阶图，若任意一对顶点满足：，而且边，则将加于图上，得到，如此反复加边直到无边可加为止，这样得到的图叫做图的闭包，记作。如下图所示 图G称为可2-着色（2-chromatic），如果可用两种颜色给G的所有顶点着色，使每个顶点着一种颜色，而同一边的两个不同端点必须着不同颜色。设图G是可2-着色的。如果G是哈密顿图，那么着两种颜色的顶点数目相等；如果G有哈密顿通路，那么着两种颜色的顶点数目之差至多为一。第八章 割集例1：（割集与断集）我们定义连通图的顶点数减1为图的秩，记作，即，如果有个连通分支，则。设，如果，则称边集为图的一个割集。割集是指一个边集S，在G中去掉S的所有边后G变为具有两个分支的分离图，但是去掉S中的部分边时图仍然是连通的，割集就是“割”掉的部分的边的集合。图中端点分别属于和的所有边的集合称为的断集(broken set)。表示一个端点在中，另一个端点在中的所有边的集合。设是连通图的一棵生成树，并且是任一树枝，则：、连枝集中不包含G的割集。、包含的一个唯一的割集。连通图G的一个割集至少包含生成的一个树枝。例2：（关联集）设是图的一个顶点，与关联的所有边的集合，称为顶点的关联集，记作。设是图的顶点集合的非空子集，其中任何两个的交均为空集，则：设和是图顶点集合的非空子集，则: =。其中，, ,。图的任一断集均可表示成若干个关联集的环和。图中任一顶点的关联集等于其余顶点关联集的环和。例3：（割集空间）设是图的一个割集，是一棵生成树，如果中恰好含有的一树枝，则称为的关于生成树的基本割集。个基本割集称为图的基本割集组。每个基本割集只含有一个树枝，这个基本割集称为图关于生成树的基本割集组，记作。图的任一断集均可表示成若干基本割集的环和。图的所有断集和空图的集合作成向量空间的一个子空间，称为的割集空间。结论：1）、阶连通图关于生成树的基本割集组是的割集空间的一组基底，割集空间维数为。2）、图的全部断集的个数为，空集不是断集。阶连通图恰有个线性无关的关联集。然后求出它们所有可能的环合，即可求出G的全部断集。第九章 最短道路与最小树例1：（最短道路）所谓最短道路问题就是在道路集合中，寻求长为最小的道路，这样的道路称为从到的最短道路(shortest path)。（1）、利用Dijnstra算法计算下图中从到的最短路径。（2）、利用Floyd算法计算下图中任意两点之间的距离。解：（1）、步骤如下：、首先，我们给起始点标上标号，给其他各点标上标号。其中：。、再在所有标号中找最小者，则把的标号改为标号。、从开始，重新计算具有标号的其他各点的标号。并比较与的大小，由于此时只有与和相邻，因此，同理可得，。、重复以上步骤直到，而此时就是到的最短路径。详细过程如下：集合集合则到的最短路径为。（2）、步骤如下：、首先将图转化为矩阵，如下所示：由Floyd算法可以得出下一次变换中元素为，即的第一行和第一列是上一