组合数学及其图论试题库

1、组合数学及其图论1、一个图G是指一个有序三元组（V（G），E（G），），其中是：_.关联函数2、是有40个点的简单图且 中任两个点之间有且只有1条路，则 。 39 3、只有一个顶点所构成的图称为：_平凡图4、如果H是G的子图，其中V（H）=V（G）和E（G）=E（H）至少有一个不成立，就称H是G的：_.真子图5、设G是p阶简单图，则_等号成立当且仅当G是完全图。q(G)p(p-1)/26、如果一条途径的_与_相同，就称这条途径为闭途径。起点 终点7、如果对图G=（V，E）的任何两个顶点u与v，G中存在一条（u-v）路，则称G是_否则称为是_ 连通图、 非连通图8、设G是P阶连通图，则_. q(

2、G)p-19、若二分图 有Hamilton回路，则 与 满足 。  10、若G是2-边连通图，则G有强连通的_. 定向图11、边数最少的连通图是 。树12、没有回路的连通图称为_. 树13、 的图是 图或 图。 平凡图，不连通图14、树T的每一个非悬挂点都是T的 _. 割点15、二分图 中若 与 满足 ，则 必有完美对集。 16、给定一个图G，如果图G的一个生成子图T是一棵树，则称T是G的一个 _. 生成树17、设G是无环图，e是G的一条边，则(G)=_.（Ge）+(G·e)18、 是 阶简单图，则 ，等号成立当且仅当 是 图。 ，完全图 2、19、_的生成树称为最优生成树

3、。连通赋权图中具有最小权20、 的一个对集 是最大对集的充要条件是 。 中无 可扩路21、一个有向图D，如果略去每条弧的方向时所得无向图是一棵树，就称D为_.有向树22、经过G的每条边的迹称为G的Euler迹，如果这条迹是闭的，则称这条闭迹为G的 _. Euler环游23、 是简单图且 ，则 。 24、若 是 -正则图，则 。 25、简单图 满足 ，则 是 图。 不连通图， 平凡图26、 的图 是 图或 图。 2 27、树 恰有两个悬挂点，则 。 连通28、 有生成树的充要条件是 。 3029、若 是有31个点的连通图且 中每条边都是割边，则 。 130、 阶图 是连通图，则 。 ，31、若

4、是 的一个对集，则 ，等号成立当且仅当是 对集。 完美对集32、每位上的数字互异且非零的两位数共有_个。 7233、现在有10双不同的鞋。为了保证能够有一双鞋被选出，至少要从这20只鞋中取出_只鞋。 11 34、展开式中的系数为_。42035、序列 1, c, c2, , cn, 的生成函数是_。;36、数值函数f和g的卷积f *g的通项f *g (r) = 。.37、叙述下列概念：发点，收点，中间点。参考要点：D包含两个特定的顶点x和y，x设有向连通图D=（V，A）满足：仅有出弧而没有入弧，称为发点；y仅有入弧而没有出弧，称为收点；D中其余顶点既有出弧有入弧，称为中间点。38、在一次围棋擂台

5、赛中，双方各出n名选手。规则是双方先各自排定一个次序，设甲方排定的次序是， ，乙方排定的次序为，。与先比赛，胜的一位与对方下一位选手比赛。按这种方法直到有一方的最后一位选手出场并输给对方，比赛结束。问最多进行几场比赛可定胜负（假定比赛无平局）。参考要点：建立一个有向图D=（V，A），V=，如果与之间连一条弧，其方向从胜者指向负者。则D的每一条弧对应一场比赛，D中弧的数目就是这次比赛的次数。根据规则，每一名选手至多输一场，所以D中每个顶点的入度至多为1，但必有一个入度为1，另一个为0。 ，即至多2n-1场比赛可定胜负。39、用一些圆面覆盖平面上取定的2n个点。试证：若每个圆面至少覆盖n+1个点，

6、则任两个点能由平面上的一条折线所连接，而这条折线整个地被某些圆面所覆盖。参考答案：构造图G=（V，E）如下：V就取平面上给定的2n 个点，两个不同的顶点如果含在同一个圆面上，就在这两个顶点之间连上一条边（边也含在这个平面上）。所得图是一个简单图，而且每个顶点的度至少是n，即，由推论，G是连通图，所以G中任两点之间有一条路连接。由G的构造，这条路被若干个圆面覆盖。40、在二元正则树T中，它的分支点数和树叶数t满足：r=t-1。参考答案：因为正则二元树T的弧数为r+t-1，顶点度数的总和为2+3（r-1）+t。由顶点度数与边数的关系，有2（r+t-1）=2+3（r-1）+t得r=t-1。41、某编

7、辑部收到由n个人所寄的一些问题的解，他们发现每个人寄来四个不同问题的解，每个问题的解恰好由两个人同时给出。问他们共收到几个不同问题的解。参考答案：首先建立图G=（V，E），G的n个顶点代表n个人。两个不同的顶点和之间连接的边数等于这两个点所对应的两个人同时给出相同问题解的个数。由条件，G的每一条边对应一个问题的解，每个顶点的度为4。因而共收到q（G）=2n个不同问题的解。42、有十七位学者，每一位都给其余的人写一封信，信的内容是讨论3个论文题目中的任一个，而且2个人相互通信所讨论的是同1个题目。证明至少有三位学者，他们之间通信所讨论的是同一个论文题目。参考答案：做一个完全子图，它的17个顶点代

8、表17位学者，把其中的边染成3种颜色：如果两个学者讨论的是第i个题目，就将连接相应的2个顶点的边染上第i种颜色（i=1，2，3）。这样就得到3色完全图。由定理。因此，这个3色完全图中有一个同色三角形。这个同色三角形所对应的3位学者之间通信所讨论的是同一个论文题目。43、证明和是非平面图。参考答案：含有6个顶点，9条边，但最短回路长度为4，不满足，因此不是平面图。有5个顶点，10条边，不满足，故不是平面图。44、在一次象棋擂台赛中,双方各出n名选手.比赛的规则是双方各自排定一个次序,设甲方排定的次序为x1,x2, xn ,乙方排定的次序为y1,y2,yn . x1与y1先比赛,胜的一位与对方输的

9、下一位选手比赛.按这种方法进行比赛,直到有一方的最后一位选手出场比赛并且输给对方,比赛就结束,问最多进行几场比赛可定胜负(假定比赛不出现平局)? 参考要点：建立一个有向图D=(V,A),V= x1,x2, xn , y1,y2,yn ,如果xi与yi进行过一场比赛,就在xi与yi之间连一条弧.其方向从胜者指向负者,则D的每一条弧对应一场比赛,D中弧的数目就是这次比赛的次数.根据比赛的规则,每一名选手至多输一场,故D中每个顶点的入度至多为1,但xn 与yn必有一个入度为1,另一个为0.因此 |A|即至多进行2n-1场比赛就可以确定胜负。45、平面上有n条线段,n3,其中任意3条都有公共端点.证明

10、这n条线段有一个公共端点。参考要点：设G是连通图,则G中任意两个不同的顶点与之间有一条路连接.若记这条路的长度为,显然.则.而对于任意的,因G连通,且,则有,所以R(G)中没有零元素.设与是G中的任意两个不同的顶点.因为存在,则在G中有一条长为的途径连接与.因而从与有一条路,故G是连通图。46、证明任意六个人中有三个人互相认识，或有三个人互不认识。.证：构图 如下：图的顶点代表这6个人，两个顶点相邻当且仅当对应的两个人互相认识。则对于图中任意一个点 或 。不妨设 及它的3个邻点为 。若 中有任意两个点，不妨设为 ，相邻，则 对应的3个人互相认识；否则， 中任意两个点不邻，即它们对应的3个人互不

11、认识。 47、给定图 ：    1、给出图 的一个生成树；    2、给出图 的点连通度；    3、给出图 的最大对集；     4、给出图 的一个最长回路； 5、给出图 的直径和半径。· 答案  1、  2、3 3、 4、 5、2 ，2  48、试给出一个算法,求连通赋权图中最大权的生成树.   算法：1)在 中选取边 ，使 尽可能的大；2)若已经选定边 ，则在 中选取边

12、，使满足以下两条：I.  不含回路；II.  在满足的前提下，使 尽可能的大。3）当2)不能继续执行时，停止。49、设是连通简单图，证明中存在个顶点，使得 仍是连通图。 证： 是连通简单图，设其最大度点为 。设 是 关于 的保距生成树，则 ，故 中至少有 个悬挂点，不妨设为 ，则 连通，是 的生成子图，即 连通。 50、对下图 ，求一个最优生成树。· 答案51、证明任意六个人中有三个人互相认识，或有三个人互不认识。.证：构图 如下：图的顶点代表这6个人，两个顶点相邻当且仅当对应的两个人互相认识。则对于图中任意一个点 或 。不妨设 及它的3个邻点为 。若 中有任意两

13、个点，不妨设为 ，相邻，则 对应的3个人互相认识；否则， 中任意两个点不邻，即它们对应的3个人互不认识。 52、给定图    问：1、作图 的一个最长回路 ；   2、给出图 的一个生成树；   3、给出图 的点连通度；   4、给出图 的最大对集；   5、作出图 的闭包。· 答案1、 2、3、 3 4、 5、 53、试证明：如果无环图G的任意两顶点都被唯一的路相连，则G是树。参考答案：证明：由于G中任意两顶点都被唯一的路相连，故G连通。 若G含有圈C，则C上的两点，在G中

14、存在两条路相连，这与题设的“唯一”矛盾。故G中不含圈。由树的定义知道：G是树。54、有n张纸牌，每张纸牌的正反两面都写上1，2，.n的某一个数。证明：如果每个数字都恰好出现两次，那么这些纸牌一定可以这样摊开，使朝上的面中1，2，3n都出现。参考答案：证明：作一二分图G=（X，Y；E），其中X=1，2，n,Y=y y 2 .yn表示这张牌。i与yj之间连接的边数等于数i在纸牌yj出现的次数，这样得到的图G是一个2正则二分图。则G中存在一个完美对集，设为M=1y 2y.ny则只要把纸牌y中的1朝上，y中的2朝下，y中的n朝上，这样摊开的纸牌就能使朝上的面中1，2，3.n都出现。55、证明边长为2的

15、正方形内任意5个点必有两点，其距离不超过。证：构造抽屉如图，将5个点放在4个边长为1小正方形内，由抽屉原理，必有一个小正方形内至少有两个点，这两个点的距离就小于或等于。 56、解：57、设数值函数f = 1,2,22,23,.，g = 1,3,32,33,.，求3f-5g的生成函数。解：数值函数f = 1,2,22,23,.和g = 1,3,32,33,.的生成函数58、设初始值h(0) = 0, h(1) = 1，h(2) = 2，求解递推关系h(n) = h(n1)+9h(n2)9h(n3). (n = 3,4,.) 参考答案：特征方程为：x3 - x2- 9x+9 = 0解得特征根为1,

16、 3,-3.因此 h(n) = A1n + B3n+ C(-3)n为一般解，由边界条件得解此线性方程组得唯一解 因此所求的解为 59、平面上给出25个点，其中没有任何3个点共线。这些点能确定多少条直线？多少个三角形？解：由于没有3个点共线，所以每对点就确定一条直线，而直线的确定与两个点的次序无关，属组合问题，直线的总数为每三个点确定一个三角形，因此所确定的三角形总数为60、一个面包店有6种不同类型的面包，这些面包以每打12个为单位向外出售。这个面包店能装配成多少打不同的面包（不考虑面包的顺序）？如果在每打中每种类型的面包至少有一个，那么又能装配成多少打不同的面包？解：假设面包店每种面包都有很多

17、（每种至少12个），由于每打中的面包与顺序无关，故为组合问题，能装配成不同的面包的打数即为6种类型的多重集（无穷重数）的12-组合数，其值为种。 如果在每打中每种类型的面包至少有一个，那么能装配成不同的面包的打数可以看成为6种类型的多重集（无穷重数）的6-组合数，其值为种。61、试用生成函数求下式之和：. 解：设 两边求导再乘 x 得:令 x = 1 得:.62网络专业的学生选修C+ 的有38人，选修VB的有15人，选修DELPHI的有20人，选修这三门课的同学总数为58人，且其中只有3人同时选修这三门课，试求同时选修两门课的同学有几人？解：设A, B, C分别为选修C+, VB, DELPH

18、I的同学的集合，则由 |AÈBÈC| = |A| + |B| + |C| - (|AÇB| + |AÇC| +|BÇC| ) + | AÇBÇC| 得 (|AÇB| + |AÇC| +|BÇC| )= |A| + |B| + |C| + | AÇBÇC| - |AÈBÈC| = 38 + 15 + 20 + 3 - 58 = 18 同时选修两门课的同学有18人。63、设简单图中每个顶点的度至少是3，则含有长为偶数的回路。证明：设是的一条最长路，则的所有邻点

19、全在内，设的邻点为，其中，在中取三个回路 它们的长度分别为。这三个数至少有一个是偶数。即中至少有一个是长为偶数的回路。 证毕。64、树的每一个非悬挂点都是的割点。证明：设是阶树，是中一个非悬挂点，即。不难看出含个顶点，其边数为 =，因而不是树。显然不含回路，所以非连通，即是的割点。 证毕。65、若连通图恰好有个奇点，则在中存在条边不交的迹，使得 。证明：设的个奇点为，在中增加条分别连接的新边，所得图记为，则是一个Euler图。记的一条Euler环游为，然后在中删除新加的条边，就将分成段，这段即为的条边不交的迹。 证毕。66、若阶图没有孤立顶点，则证明：设是的最大独立集，是的最小点覆盖，则是的独立集，是的点覆盖，所以 = 因此67在一次聚会上有10位男士和10位女士。这10位女士能够有多少种方法选择男舞伴开始第一次跳舞？如果每个人必须换舞伴，那么第二次跳舞又有多少种选择方法？解：对于第一次跳舞，可以对10位男士和10位女士并排排列，如果10位男士不改变次序，10位女士一个全排列就是一种配对方式，共存在10! = 3628800可能的选择； 对于第二次跳舞，每位女士必须选择一位不是第一次与她跳舞的男舞伴，因此可能的选择方法数为移位排列数 =