组合数学与图论复习题及答案
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个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj，要么有ri＋rj ＝100，也就是说ai－aj|100或者ai＋aj|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).
令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。
在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者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?
A ．15个人进行圆排列，减去ab 组成一个元素的14人的圆排列，然后减去ba 组成一个元素的14人的圆排列。
B ．15个人进行圆排列，减去ab 组成一个元素的14人的圆排列。
8． Determine the number of 10-combinations of the multiset S={∞*a,4.b,5*c,7*d}。
(1+x+x 2+x 3+…)( 1+x+x 2+…+x 4) ( 1+x+x 2+…+x 5) ( 1+x+x 2+…+x 7)展开
9． 把n 个有编号的球放入m 个有编号的盒子中，不允许有空盒子，有多少种
放法。
先假设，盒子没有编号，然后乘上组合与排列的关系：),(!*2m n S m
10． 证明在n （n ≥2）个人中总有两个人，他们在这群人中所认识的人数目相同。
当n ＝2时，如果两个人相互认识，则每个人认识的人只有一个；如果不认识，则每个人认识的人为0个。
当n>2时，设x i (x=1,2,…,n)表示，第i 个人认识的人的数目。（每个人最多只能认识n-1个人。） A ．如果每个人都有熟人
那么由鸽子洞原理知道至少有两个人i 和j 认识的人数相同即x i ＝x j B ．如果只有一个人没有认识的人
那么对于剩下的n －1个人来说能认识的人对多只有n －2个，由鸽子洞原理知道，这n －1个人中至少有两个人i 和j 认识的人数一样即x i ＝x j
C ．如果至少有两个人都没有熟人，则满足题设。
11． 一个剧团演出11周，为保证收入和不至于太累，规定每天至少演出一场，
每周不超过12场。证明存在连续的若干天，恰好演出21场。
设a 1为第一天该剧团的演出的次数，a i 表示前i 天一共的演出次数。可知道a i 是单调递增的。且有a 1>=1,a 77<=132。于是有a i ＋21(i=1,2,…,77)，也是单调递增的。而a 77＋21<=153。则有154个在1到153之间，所以由鸽子洞原理知道，至少存在两个数a i 和a j 有a i ＝a j ＋21即a i －a j ＝21
12． 在边长为1的正三角形中任选5个点，证明必有两个点的距离不超过1/2。
如上图所示，将这个正三角形分割成4个小的正三角形，有每个小正三角形的边长为1/2。将5个点放入这4个小三角形内，由鸽子洞原理有一个三角形内部有2个点，因为小三角形的边长为1/2，所以这两个点的最大距离为1/2。
13． 设a 1，a 2，a 3，?，a n 是1，2，3，?，n 的一个排列，证明当n 是奇数时，
乘积（a 1-1）（a 2-2）（a 3-3）?（a n -n ）是偶数。 假设，当n 为奇数时A ＝（a 1-1）（a 2-2）（a 3-3）?（a n -n ）是奇数，则： （a i -i ）均为奇数，否则A 为偶数。也就是说当i 为奇数时a i 必须为偶数；因为n 为奇数，所以从1到n 的偶数数目为（n-1）/2，奇数数目为 （n+1）/2，所以由鸽子洞原理可以知道当i 为奇数时，至少有一个（a i -i ）为偶数，所以A ＝（a 1-1）（a 2-2）（a 3-3）?（a n -n ）是奇数。
14． 有100个人的舞会，每个人的舞伴数都是偶数，证明必有3个人有相同的
舞伴数。
由于每个人的舞伴数是偶数个，所以可能有的舞伴数为0，2，4，6，8，…，98。共有50种可能。
A ．如果每个人都有舞伴，可能的舞伴数为2，4，…，98。共49种可能，相当于把100个球放入49个篮子中，由鸽子洞原理知道至少有一个篮子有3个球以上，也就是说有3个人有相同的舞伴数。
B ．如果只有一个人没有舞伴，剩下的人可能的舞伴数为2，4，…，98。共49种可能，相当于把99个球放入49个篮子中，由鸽子洞原理知道至少有一个篮子有3个球，也就是说有3个人有相同的舞伴数。
C ．如果有两个人没有舞伴，剩下的人可能的舞伴数为2，4，6，…，96。共48中可能。相当于把98个球放入48个篮子中，由鸽子洞原理知道至少6有一个篮子有3个球以上，也就是说有3个人有相同的舞伴数。
D ．如果有至少3个人没有舞伴，则有3个人的舞伴数为0
15． N 个质点排成一列，涂以红、白、黑三种色，每点涂一色，要求同色的点
为偶数，有多少种？
(1+x 2
+x 4
+…)3
=(
2
11x
-)3
=∑∞
=-+0
2),13(r r x r r C
16．有两堆石块，每一石块的重量都小于nkg(Z)，每一堆中的石块重量互不相同(规定石块重量为整数)。证明，如果两堆石块的总数不少于n，那么总可以从两堆中分别选出一块，使两者的总重量是nkg。
石块按重量可以分成这样几类：
{1,n-1},{2,n-2},{3,n-3},…,{????2/
2/n
n}，共??2/n个集合。
,
假定第一堆石头有p块，第二堆有q块，由题意有p+q>=n。两堆石头关
系等价，所以下面以第一堆为参照。
A．考虑第一堆石头都集中在k类集合里面（除去单出来的石头外，其他石头都两两在一起）。此时如果第二堆石头里面有分布在k类集合中的元素，则肯定有
满足题意的来自两堆石头的两块石头；如果先让第二堆石头分布满在其他的
??2/n－k个集合，因为每堆中石块重量不同，那么现在一共有n－1或n－2
块石头分布在集合中，第二堆就多出了1或2个石头，那么这1或2个石头肯
定是在前面的k个集合中，所以这也有满足题意的两块石头。
B．如果第一堆石头分布在i（i从k到p）个集合中，同样，显然第二堆石头分布满剩下的??2/n－i个集合，由于每堆中石块重量都不一样，所以
第二堆将会多出q＋2*i－2*??2/n块石头，那么这些多出来的石头，肯定会分
布在第一堆石头所在的i个集合中，所以有满足题意的两块石头。
17．在9个人中，或者有3人相互认识，或者有4人相互不认识。
N(3,4) <= N(2,4)+N(3,3) 因为N(2,4)和N(3,3)都为偶数，所以有：
N(3,4) <= N(2,4)+N(3,3)-1 = 4+6-1=9
18．证明当R(p，q-1)和R(p-1，q)都是偶数时，R(p，q)≤R(p，q-1)+R(p-1，q)-1。
19．把n个球放入k个盒子，分别考虑球有无编号，盒子有无编号，以及盒子可否空3种情况下的配置数。
A．n个球无编号，k个盒子也没有编号，允许为空
F(k,n)/K! 首先认为盒子是有编号的，然后去掉盒子的编号B．n个球无编号，k个盒子也没有编号，不允许为空：
在每个盒子中先放一个球，剩下n－k个球，任意放。
F(k,n-k)/K! 首先认为盒子是有编号的，然后去掉盒子的编号。
D ．n 个球无编号，k 个盒子有编号，允许空
F(k,n)=C(k+n-1,n) E ． n 个球无编号，k 个盒子有编号，不允许空
在每个盒子中先放一个球，剩下n －k 个球，任意放。 F(k,n-k)=C(n-1,n-k)
F ． n 个球有编号，k 个盒子无编号，允许空
∑=k
i i n S
1
2
),(
F ．n 个球有编号，k 个盒有无编号，不允许空 S 2(n,k)
G ．n 个球有编号，k 个盒有有编号，允许空 先认为盒子没有编号，然后再乘上每次取盒子的方法数。
∑=k
i i n S
i k C 1
2
),(),(
H ．n 个球有编号，k 个盒有有编号，不允许空 先认为盒子没有编号，然后再乘上给盒子编号的方法数。
),(!2k n S K
20． 将n 个元素的集合划分为非空子集，有多少种？
可能的划分成的集合数有：1，2，3，…，n 。
相当于将n 个球，分别放入以上数字的篮子中的放法，然后求和。有：
∑=n
k k n S
12
),( （球有编号的时候）
∑
=n
k k n k F 1
!
),( （球无序的时候）
21． 设有重量分别为1克，2克，3克，5克，7克的5个砝码，可以称多少种
不同重量的物体。
(1+x)(1+x 2)(1+x 3)(1+x 5)(1+x 7) 展开看有多少项。
22． 有A ，B ，C ，D 四位教师和1，2，3，4四门课程，已知A 和D 不能教1
和4，B 不能教3，C 不能教2和3。为每位教师恰好安排一门课程的方式有多少种。
… ＝1+7x+15x 2+10x 3+2x 4
N = 4!-7*3!+15*2!-10*1!+2*0!=4
23． 设有多重集B=｛∞·0，∞·1，∞·2，∞·3｝，可以组成长为r ， 0出现偶
数次的数字串有多少个。（限制排列问题）
(1+x 2
+x 4
+…)(1+x 2
+x 3
+…)3
= ∑
∞
=+++
-=
+-0
4
)2
)
1)(2()1(()
1()1(1r r
r
x r r x x
a r = 2
)
1)(2()1(+++
-r r r
24． 10个人圆桌会议，休会后重新入座，每个人都不与原先的人相邻的坐法有
多少种。
题目得条件时每个人都不与原先的人相邻，即是说新的圆排列中不出现123，234，345，…，(n-2)(n-1)n ，(n-1)n1，n12，这些情况。 设pi 表示圆排列具有i(i+1)(i+2)这一性质的，Ai 表示具有pi 这一性质的圆排列的集合。
n-2个元素进行圆排列 |A1| = (n-3)!，…，|Ai| = (n-3)! 对于 |A1∩A2| ＝ (n-4)!，…，|Ai ∩Ai+1| ＝ (n-4)! ……
N=(n-1)! – C(n,1)(n-3)! + C(n,2)(n-5)! +… 一直到C(n,n)
25． 求解递推方程
① f(n)=2f(n/2)+C n>1
f(1)=C n=1
设n=2
k
,C 为常数
f(n)=2f(n/2)+C 2f(n/2)=4f(n/4)+2C 4f(n/4)=8f(n/8)+4C …
2k-1(n/2k-1)=2k f(n/2k )+2k-1C
将上面的各等式，左右相加得：
f(n)=C+2C+…+2k-1C+2k f(n/2k )= C+2C+…+2k-1C+2k C
=∑=k
i i
C 0
2*=C*(2K ＋1-1)
② H(n)=4H(n-1)-4H(n-2) n>1
H(0)=0，
H(1)=1 特征方程为x 2-4x+4=0 解为二重根：q 1=q 2=2 通解表示为：H n =C 1*2n +C 2*n2n 由H(0)=0，H(1)=1有： C 1+0*C 2=0 C 1*2+C 2*2=1 解得:C 1=0 C 2=1/2 H n =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) = 2 f(2) = 3
F n
27．Kn =
且E=E 1∪E 2，E 1∩E 2=Φ。
① 证明n>11,若G 1是平面图，则G 2不是。 ② 证明G 1和G 2必有一个是连通图。
①假设G 2也是平面图。那么有e 1<=3n-6,e 2<=3n-6，所以有e<=2(3n-6)。因为Kn 是完全图所以有e ＝n*(n-1)/2，所以有n*(n-1)/2<=2(3n-6)，
n 2-13n+24<=0，满足不等式得n 得取值为：2～10，所以当n>11时，不等式不成立，所以当n>11时，由假设得出得结论是不成立得，所以假设不成立，所以若G1为平面图，G2肯定不是平面图。 化简得：
② 假设两个图都不是连通图。有e 1<=n-2和e 2<=n-2成立从而有
e<=2(n-2)。
因为Kn 是完全图所以有e=n*(n-1)/2，所以有n*(n-1)/2<=2n-4，解得n 2
－5n ＋8<=0。但是n 2－5n ＋8=(n-5/2)2+7/4>0，所以矛盾，所以必有一个图是连通图。
28. Let G be a planar graph of order n in which every vertex has the same
degree k. Provw that k ≤5. （∑∑==e v d r d i 2)()(,e<=3n-6,n-e+r=2,2e>=3r ）
所有点度的和应该是边数的2倍，即∑=e v d 2)(。由题意由G 的∑=nk v d )(，
那么由nk ＝2e ，对于平面图我们有e<=3n-6，所以有nk<=6n －12，k<=6-12/n ，因为k 为整数，所以有k<=5。
29. Let G be an undirected graph. Prove that κ(G)≤λ(G)≤δ(G). κ(G): vertex-connectivity,λ(G):edge-connectivity,
δ(G): the smallest degree of a vertex of G.
若G 不连通，则K(G)=λ(G)＝δ(G)=0，则κ(G)≤λ(G)≤δ(G)成立。 若G 连通
证λ(G)≤δ(G)：
假定λ(G)>δ(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)<= λ(G).
30. Prove that a connected graph with a bridge does not have a Hamilton
cycle.
由题意可以知道这个连通图的结构为：
H回路的定义是周游每个点恰好一次的回路，假设我们从A中的一个点a i 开始周游。
如果a i是P那么，当从P开始周游完A中所有点时，必将回到P点才能进入B，所以这种情况不可能构成H回路。
如果a i不是P，当只有完A中除P之外的所有点时必经过P然后通过Q进入B，周游完B后，要回到开始的点，必将再次经过Q和P，所以这种情况也不能构成H回路，所以如图的连通图不可能构成H回路。
31． Let G be a graph of order n and d(x)+d(y)≥n for all pairs of vertex x and y. Prove that G has a Hamilton cycle.
由于d(x)+d(y)>=n，所以G一定有H路径。设此路径为V1,V2,…,Vn。
若V1和Vn相邻接，则构成H回路。
若V1和Vn不相邻接。假定V1邻接于{Vi1，Vi2，。。。，Vi k}(2<=Vi k<=n-1)，则Vn必邻接于Vi1，Vi2，。。。，Vi k中一点。若Vn与Vi1，Vi2，。。。，Vi k都不邻接，那么Vn至多邻接n-k-1个点邻接即d(Vn)<=n-k-1，而d(V1)＝k，那么有d(V1)+d(Vn)<=n-1,与题设矛盾。所以Vn必与Vi1，Vi2，。。。，Vi k中一点邻接，从而构成H回路。
。。。……。。
V1 V2 Vi …Vn
32. 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有奇数长度的回路那么，肯定会有如图所示子图的情况：X Y
。。
。。
……
。。
。x1y1
。z
此时|E|为奇数，|V|也为奇数。
若z是属于X集合的点，那么对于边e(x1,z)，x1和z都属于X，这个与定义不符。若z属于Y，同样不满足。
B．若每个回路长度都是偶数，那么每个回路肯定会有这种结构。
X Y
。。
。。
……
。。
。x1y1
。
此种情况是满足定义的。
C．对于非回路，可以把每个隔点，归于一类，这样也可以满足定义。33．Prove 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 号球单独占用一个篮子，那么就是将剩下的n －1个球放入k －
1个篮子中，有 S 2(n －1,k －1)。
B ．如果第n 号球没有单独占用一个篮子，那么就是剩下的n －1个球放入k
个篮子中，有 S 2(n －1,k)。第n 号球可能在k 个篮子中的任意一个，所以放置方法数为 K* S 2(n －1,k)
所以得到 S 2(n,k)= kS 2(n-1,k)+ S 2(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。为每台机器恰好涂一种颜色的方案数有多少？
35．两位教师带k 位同学外出，排成一列，为安全起见，规定教师必须排在队首
和队尾。休息后重排，每个人都不在原来的位置的排法有多少种？试用有禁区的排列棋盘多项式求解。
D n =K!-C(K,1)(K-1)!+C(K,2)(K-2)!+…+(-1)K C(K,K)0!
有禁区的棋盘：
N=K!-r 1(k-1)!+r 2(k-2)!+…+(-1)k r k
K
K
R(
)=R()K =(1+x)K =
∑
=K
i i
x
i K C 0
),(
以下为图片格式文档
1．如图所示是一张城市平面图，图中的直线表示街道，直线的交点表示街道
的交叉路口，试证明从交叉路口()00S ，到交叉路口()T m n ，共有m n m
+??
???
条不同的
路径可走。
S
T (0
2.一个学生打算用37天总共60学时自学一本书，他计划每天至少自学1学时，证明：无论他怎样安排自学时间表，必然存在相继的若干天，在这些天内其自学总时数恰好为13学时（假定每天自学学时数为整数）。
4.某校有120名学生参加数学竞赛，竞赛试题共有甲，乙，丙三题．竞赛结果为：12名学生三题全对；20名学生只做对了甲题和乙题；16名学生做对了甲题和丙题；28名学生做对了乙题和丙题；48名学生做对了甲题；56名学生做对了乙题；16名学生三题都做错了．试求出做对了丙题的学生人数。（上题题目）
5.有两颗骰子，每个骰子六个面上刻有1，2，3，4，5，6个点．问掷骰子后，点数之和为r，两颗骰子的点数有多少种搭配方式？
6.求由数字2，3，4，5，6，7组成的r位数中，3和5都出现偶数次，2和4至少出现一次的r位数的个数。
7.有无穷多个字母A，B和C．求从中选出n个字母但必须包含偶数个A的方式数。
8.对1×n棋盘的每个正方形用红或蓝两种颜色之一着色．设an表示没有任何两个着红色的正方形是相邻的着色的方式数．求an所满足的递归关系并解之。
9.如果用an表示没有两个0相邻的n位三元序列（即由0，1，2组成的序列）的个数．求an所满足的递归关系并解之。
10.某人有n元钱，她每天要去菜市场买一次菜，每次买菜的品种很单调，或者买一元钱的蔬菜，或者买两元钱的猪肉，或者买两元钱的鱼．问，她有多少种不同的方式花完这n元钱?
11.求方程x1+x2+x3+x4=20的整数解的个数，其中1≤x1≤6，0≤x2≤7，4≤x3
≤8，2≤x4≤6。（相似解法如下）
12.在一个班上有n 名学生，临时将这n 个学生任意编号为123n
???，，，，．当教师上
课按原来的点名册点名时，如果编号为i 的学生正好是第i 个喊到时，就称为一次巧遇。a ．求至少有一次巧遇的概率；b ．求恰有m 次巧遇的概率。
本试卷满分90分 （06级计算机、信息安全专业、实验学院） 一、判断对错（本题满分10分，每小题各1分） （ 正确画“√”，错误画“×”） 1．对每个集合A ，A A 2}{∈。 （×） 2．对集合Q P ,，若?==Q P Q Q P ,，则P =?。 （√） 3．设,,:X A Y X f ?→若)()(A f x f ∈，则A x ∈。 （×） 4．设,,:Y B Y X f ?→则有B B f f ?-))((1。 （×） 5．若R 是集合X 上的等价关系，则2R 也是集合X 上的等价关系。 （√） 6．若:f X Y →且f 是满射，则只要X 是可数的，那么Y 至多可数的。（√） 7．设G 是有10个顶点的无向图，对于G 中任意两个不邻接的顶点u 和v, 均有9deg deg ≥+v u ，则G 是哈密顿图。 （×） 8．设)(ij a A =是 p 个顶点的无向图G 的邻接矩阵，则对于G 的顶点i v , 有∑==p j ij i a v 1deg 成立。 （√） 9. 设G 是一个),(q p 图，若1-≥p q ，则]/2[)(q p G ≤χ。 （×） 10．图G 和1G 同构当且仅当G 和1G 的顶点和边分别存在一一对应关系。（×）
二.填空(本题40分，每空各2分) 1．设}},{,{φφ=S 则=S 2 }}}{,{}},{{},{,{φφφφφ 。 2．设B A ,是任意集合，若B B A =\，则A 与B 关系为 φ==B A 。 3．设1)(,0)()(,:};3,2{},1,0{},,,{===→===c f b f a f Y X f Z Y c b a X , 3)1(,2)0(,:==→g g Z Y g ,则)()(c f g a f g ，分别为 2，3 。 4．设X 和Y 是集合且X m =，Y n =，若n m ≤，则从X 到Y 的单射的 个数为 !m C m n 。 5．设}2,1{},,,2,1{==B n X ，则从X 到Y 的满射的个数为 22-n 。 6．设)}2,4(),1,3(),3,2{()},4,3(),2,2(),2,1{(},4,3,2,1{===S R X ，则 =)(R S R )}2,3(),4,2(),4,1{( 。 7． 设???? ??=???? ??=5123454321,415235432121σσ，则???? ??=235411234521σσ 。 8. 设)},(),,(),,{(},,,,{a c c b b a R d c b a X ==，则 )},(),,(),,(),,(),,(),,(),,(),,(),,{(b c a c a b c b c a b a c c b b a a R =+ 。 9. 设X 为集合且X n =，则X 上不同的自反或对称的二元关系的个数 为 22222222n n n n n n +--+- 。 10．设}}{},{},,{{},,,,{d c b a A d c b a X ==是X 的一个划分，则由A 确定的 X 上的等价关系为 )},(),,(),,(),,(),,(),,{(d d c c a b b a b b a a 。 11．}10,,2,1{ =S ，在偏序关系“整除”下的极大元为 6，7，8，9，10 。 12．给出一个初等函数)(x f ，使得它是从)1,0(到实数集合R 的一一对应， 这个函数为 x ctg π或-x ctg π或)2/(ππ-x tg 。 13. 设G 是),(p p 连通图，则G 的生成树的个数至多为 p 。
第四届全国组合数学与图论会议纪要 为促进我国组合数学与图论学科的进一步发展，加强国内同行的学术交流与合作，第四届全国组合数学与图论大会于2010年8月21日至25日在徐州师范大学举行。会议由中国组合数学与图论学会主办，徐州师范大学承办，并得到了徐州师范大学和国家自然科学基金委天元基金的大力资助。 会议期间，来自国内外约160所大学和研究院所的约400位专家、学者和研究生共聚一堂, 积极讨论，相互交流。福州大学范更华教授、同济大学邵嘉裕教授、中科院胡晓东教授、香港大学臧文安教授、南开大学高维东教授和北京交通大学常彦勋教授等作了6个大会报告（60分钟）。另外，分四个分组进行了13个特邀报告（30分钟）以及近120个小组报告（15分钟）。报告内容涉及组合数学与图论的各个领域。其中包括结构图论、随机图论、代数图论、化学图论、图的染色、组合设计、组合优化、组合计数、组合矩阵、复杂网络、网络优化、代数组合论与应用图论等众多领域。 开幕式由徐州师范大学数学科学学院院长刘笑颖教授主持，徐州师范大学党委书记徐放鸣教授首先致开幕词，接着，中国组合数学与图论学会的理事长陈永川发表了热情洋溢的讲话。
本次会议还举行了中国组合数学与图论学会理事会的换届选举。首先由上届正副理事长陈永川教授、李学良教授和王军教授（其中宝升教授因事缺席）提出新一届理事会的候选人名单。然后经理事会充分讨论，并进行民主投票选举，产生了51位新任理事，并随后由新一届理事会选举产生了新一届常务理事会与正副理事长。 与会代表衷心感谢本次会议的东道主徐州师范大学的校、院各级领导对本次会议的大力支持，衷心感谢会务组的全体同志为本次会议的顺利召开而付出的辛勤劳动。 经新一届常务理事会讨论，决定下一届全国组合数学与图论大会于2012年在洛阳师范学院举行。
电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D
6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G
组合数学在计算机中的应用 组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。随着计算机科学的发展,组合数学也在迅猛发展,而组合数学在理论方面的推进也促进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础,组合数学作为大多数计算机软件设计的理论基础,它的重要性也就不言而喻。 就从目前我们在学习c++等语言进行编程解决问题看，组合数学的一些知识就能得到运用。例如Hannoi塔问题。用刚刚学的递推关系分析，设h(n)为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h(1)=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上，共计3个盘次，故h(2)=3。以此类推，当a柱上有n(n>=2)个盘子时，总是先借助c柱把上面的n-1个盘移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动h(n-1)+1+h(n-1)个盘次。所以：h(n)=2h(n-1)+1 （边界条件：h1=1）。而一旦得出了这个递推关系式，就很容易运用递归算法来解决这样一个问题，递归算法因为是运用栈的方式进行加深与回溯，这个栈是系统给出的，故大大减少代码量。因此利用组合数学中的知识很容易抽象出数学模型再用相应的编程技巧来解决问题。 另外，我们最近数据结构正好学到了图这一章节。图是一种非常重要的数据存储结构，而在图的建立，遍历，生成树等问题的解决算法上基本都运用了组合数学中的知识。例如在最小生成树算法中间需要判断是否有环的问题，中间算法思想中就包含了欧拉图判定定理，(1) 无向连通图G是欧拉图=>G不含奇数度的结点(即G的所有结点的度均为偶数(0视为偶数))；(定理1) (2) 非0平凡图G有欧拉通路=>G最多有两个奇数度的结点；(定理1的推论) (3) 有向图D是欧拉图=>D连通且D的所有结点的入度等于出度。有向连通图有欧拉通路=>除两个结点外，其余结点的出度均等于入度，且这两点deg-(v)-deg+(v)=±1。(定理2) 除此之外，在那些我们还没有接触的计算机领域中，处处也有组合数学的身影。如：信息检索是计算机科学中一个基本而又重要的问题。如何组织数据,使用什么样的查找方法,对检索的效率有很大的影响。所熟知的在有序表结构上的二分搜索算法是一种很有效的方法,那么二分搜索是最好的算法吗?Yao利用Ramsey数对这一问题作了肯定的回答。 具体地讲,假设一个表有n个不同的项,其元素取自键空间M={1,2,,, m } ,希望找到在表中存储M的任意n元子集S的方法,使得容易回答下述询问: X在S中吗?如何存储M的n元子集的规则称为一个表结构或( m , n)-表结构。最简单的表结构是有序表结构,它是按上升序列出S中的元素。更一般的是按置换排序的表结构,其方法是固定{1,2,,, n}的一个置换,根据比置换的次序列出S中的元素。 信息检索的计算复杂性依赖于表结构和搜索策略。复杂性的度量是最坏情形下确定x 是否在S中所需要的询问次数。例如,对有序表结构,如果用二分搜索,所需要的询问次数是[log2( n+ 1) ]。复杂性f ( m , n )定义为所有的( m , n)-表结构和搜索策略下的复杂性的最小值。关于f ( m , n ), Yao证明了: 定理1 对每个n ,存在数N ( n) 使得f ( m , n) = [log2 ( n +1 ) ]对所有m>=N ( n) 成立。据此定理,对充分大的m ,就信息检索来说,用有序表结构是最有效的方法。 利用下述两个引理,立即可得此定理的证明。 引理1 若m >=2 n -1 , n >=2 ,对于按置换排序的表结构。无论采用何种策略,在最坏情形
组合数学在生活中的应用
组合数学在生活中的应用
组合数学在生活中的应用 数计学院姓名：廖梓文班别： 11数本3班学号：2011224323 摘要本文从对组合数学的一些基本概念和方法入手,结合具体的应用举例和数学史上的著名故事作为论题进行研究,进行了较全面的资料搜集.使人们加深对组合数学的理解,并应用于生活. 关键词:组合数学;数学游戏 1 引言 本文通过具体的应用实例和数学史上的一些故事和难题,介绍了组合数学是如何在生活中应用的.在研究了一些典型的例子和趣味性的故事的基础上,系统的查阅了相关文献，并结合生活中涉及组合数学的相关知识进行阐述,具体说明了组合数学的基本方法及其在生活中的应用.这样就使组合数学显得更加形象,也使抽象的理论概念变得浅显具体,更易被初学者理解和接受,以至于可以激发人们在生活中应用组合数学的意识. 2 组合数学的历史 组合数学是一门既古老又年轻的数学分支。随着计算机的普及推广,组合数学这门古老的学科焕发出蓬勃的生机. 组合数学不仅在基础数学研究中具有极其重要的地位，在其他的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。 我国古人在《河图》《洛书》中便已经对一些有趣的组合问题给出了正确的解答。中国最早的组合数学理论可追溯到宋朝时期的”贾宪三角”, 后来被杨辉引用, 所以普遍称之为“杨辉三角”, 这在西方是1654年由帕斯卡提出，但比中国晚了400多年。近代，由于计算机的出现，组合数学这门学科得以迅猛发展，成为了一个重要的数学分支。近代图论的历史可追溯到18世纪的七桥问题—穿过K?nigsberg城的七座桥，要求每座桥通过一次且仅通过一次。Euler1736年证明了不可能存在这样的路线。 4.组合数学的基本解题方法
思考练习 第一章 1对任意图，证明。 证：，故。 2 在一次聚会有个人参加，其中任意6个人中必有3个人互相认识或有3个人互不认识。举例说明，将6个人改成5个人，结论不一定成立。 证：构图如下：图的顶点代表这6个人，两个顶点相邻当且仅当对应的两个人 互相认识。则对于图中任意一个点或。 不妨设及它的3个邻点为。若中有任意两个点，不妨设为 ，相邻，则对应的3个人互相认识；否则，中任意两个点不邻， 即它们对应的3个人互不认识。 若这5个人构成的图是5圈时，就没有3个人互相认识或有3个人互不认识。 3 给定图 画出下列几个子图: (a) ； (b); (c)
解：(a) (b) (c) 第二章 1设是一个简单图，。证明：中存在长度至少是的路。 证：选取的一条最长路，则的所有邻点都在中，所以
，即中存在长度至少是的路。 2证明：阶简单图中每一对不相邻的顶点度数之和至少是，则是连通图。 证：假设不连通，令、是的连通分支，对，有 ，与题设矛盾。故连通。 3设是连通图的一个回路，，证明仍连通。 证：，中存在路， 1、若，则是中的路； 2、若，则是中的途径，从而中存在 路。 故连通。 4图的一条边称为是割边，若。证明的一条边是割边当且仅当不含在的任何回路上。 证：不妨设连通，否则只要考虑中含的连通分支即可。 必要性：假设在的某一回路上，则由习题2.13有连通，，与是割边矛盾。故不在回路中。 充分性：假设不是割边，则仍连通，存在路，则就是含的一个回路，与不在回路中矛盾。故是割边。 5证明：若是连通图，则。 证：若是连通图，则。
第三章 1 证明：简单图是树当且仅当中存在一个顶点到中其余每个顶点有且只有一条路。 证：必要性：由定理3.1.1立即可得。 充分性：首先可见连通。否则，设有两个连通分支、，且， 则到中的顶点没有路，与题设矛盾。 其次，中无回路。否则，若有回路。由于连通，到上的点有路， 且设与的第一个交点为，则到上除外其余点都至少有两条路，又与题设矛盾。 故是树。 2 设图有个连通分支，。证明含有回路。 证：假设中不含回路。设的个连通分支为，则每个连通无回路，是树。从而 ， 与题设矛盾，故无回路。 3是连通简单图的一条边。证明在的每个生成树中当且仅当是的割边。 证：必要性：假设不是的割边，即连通，有生成树，与在的每个生成树矛盾。故不是的割边。 充分性：假设存在一棵生成树，使得不在中，从而连通，与是的割边矛盾。故在的每个生成树中。 4设是至少有3个顶点的连通图，证明中存在两个顶点，使得仍
一、用真值表证明德*摩根律（证明其中一条即可）。 二、设A,B,C是集合，试问在什么条件下(A-B)-C=A-(B-C)？给出证明。 三、设A={a,b,c}，问A上有多少种不同的：二元关系？自反关系？对称关系？传递关系？等价关系？偏序关系？良序关系？ 四、用花括号和空集来表示1?2（注意?表示集合的叉乘）. 五、设R是实数集，Q是有理数集，试构造出R-Q与R之间的双射. 1．简单叙述构造的思路； 2．给出双射f：R-Q -> R 或f：R -> R-Q的严格定义。 2008年期末考题： 一、在有向图中，如果存在从顶点u到顶点v的有向通路，则说u可达v；如果顶点u和顶点v互相可达，则说u双向可达v。回答下列问题： 1．顶点集上的可达关系是不是等价关系？为什么？ 2．顶点集上的双向可达关系是不是等价关系？为什么？ 3．对于上述两个关系，如果是等价关系，其等价类的导出子图称为什么？ 二、一棵树有13个顶点，除了3个2度顶点和若干个树叶之外，其余顶点都是5度。 1．求出5度顶点的个数（写出计算过程）； 2．画出所有互不同构的这种树。 三、计算出右图中v1到v4长度为4的通路数（要写出计算过程 的主要步骤），并写出一个最小支配集、一个最大团、一个最小 边覆盖、一个最大匹配。 四、如果一个图中所有顶点度数都为k，则称为k正则图。8阶3 正则简单图一定是平面图吗？一定不是平面图吗？为什么？ 五、证明：如果正则简单图G和补图G都是连通图，则G和G中至少有一个是欧拉图。 六、证明：如果n阶（n≥3）简单图G中，对于任何1≤j
离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝
图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f
浙江师范大学《图论》考试卷 （2007－2008学年第一学期） 考试类别 闭卷 使用学生 行知数学 051.052. 考试时间 150 分钟 出卷时间 2008年1月4日 说明：考生应将全部答案都写在答题纸上，否则作无效处理。 一、填空题 (25%) 1、给定图G 11 （1）给出图G 的一条最长路＿＿＿＿＿＿＿； （2）给出图G 的二个参数值λ(G)= ,κ(G)= ； （3）给出图G 的一个最大独立集 ； （4）作出子图G[u 2,u 5,u 7,u 9,u 11,u 12]________,G-{u 8,u 9,u 12}____________, G-{u 1u 3,u 1u 4,u 1u 7,u 1u 10}_________ _______； 2、图G 是二分图的充分必要条件是 ； 3、G=(X,Y,E)是二分图，无孤立点，则β1(G) 与α0(G)的关系是 ； 4、Ramsey 数r(k,t)、r(k-1,t) 和r(k,t-1) 的关系是 ； 5、G 是含有56个顶点的无回路图，且对Ｇ中任两个不相邻的顶点v u ,，Ｇ+uv 有唯一的回路，则Ｇ的边数为____________; 6、图G 有Euler 环游的充要条件是＿＿＿＿； 二、设七个字母在通迅中出现频率分别为a;25%,b;22%,c;20%,d;12%,e;10%,f;6%，g;5%。编一个最优前缀码，并画出相应的最优二元树。 (15%) 三、 证明：非平凡连通图G 至少有二个非割点。 (10%) 四、 G 是点色数χ(G)=2的k —正则简单图。证明G 有k 个边不交的完美对集M 1,M 2, ┄, M k ， 使 E(G)= M 1∪M 2∪┄∪M k 。 (13%) 五、 给出平面图G 的顶点数p(G)、边数q(G)、面数 )(G ?和连通分支数ω(G)的一个关系式， 并给予证明。 (15%) 六、 G 是p 个顶点的简单图，对G 中每一对不相邻的顶点u 、v,均有d G (u)+d G (v)≥p-1。 （1） 证明G 有Hamilton 路；（2） G 是二连通图吗？为什么？。 (12%) 七、设Ｇ是连通图，若对每个真子集V 0?V(G) ，只要∣V 0∣≤k-1，G- V 0仍连通.证明q(G)≥ kp(G)/2 。 (10%)
集合论与图论习题册 软件基础教研室 刘峰 2015.02
第一章 集合及其运算 8P 习题 1. 写出方程2210x x ++=的根所构成的集合。 2.下列命题中哪些是真的，哪些为假 a)对每个集A ，A φ∈； b)对每个集A ，A φ?； c)对每个集A ，{}A A ∈； d)对每个集A ，A A ∈； e)对每个集A ，A A ?； f)对每个集A ，{}A A ?； g)对每个集A ，2A A ∈； h)对每个集A ，2A A ?； i)对每个集A ，{}2A A ?； j)对每个集A ，{}2A A ∈； k)对每个集A ，2A φ∈； l)对每个集A ，2A φ?； m)对每个集A ，{}A A =； n) {}φφ=； o){}φ中没有任何元素； p)若A B ?，则22A B ? q)对任何集A ，{|}A x x A =∈； r)对任何集A ，{|}{|}x x A y y A ∈=∈； s)对任何集A ，{|}y A y x x A ∈?∈∈； t)对任何集A ，{|}{|}x x A A A A ∈≠∈。 答案： 3.设有n 个集合12,,,n A A A 且121n A A A A ???? ，试证：12n A A A === 。 4.设{,{}}S φφ=，试求2S ？ 5.设S 恰有n 个元素，证明2S 有2n 个元素。
16P 习题 6.设A 、B 是集合，证明:(\)()\A B B A B B B φ=?= 。 7.设A 、B 是集合，试证A B A B φ=?=?。 9.设A ，B ，C 为集合，证明：\()(\)\A B C A B C = 。 10.设A ，B ，C 为集合，证明：()\(\)(\)A B C A C B C = 。 11.设A ，B ，C 为集合，证明：()\(\)(\)A B C A C B C = 。 12.设A ，B ，C 都是集合，若A B A C = 且A B B C = ，试证B=C 。 15.下列命题是否成立？说明理由（举例）。 (1)(\)\(\)A B C A B C = ；(2)(\)()\A B C A B C = ； (3)\()()\A B C A B B = 。（答案：都不正确）
组合数学论文 现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好像是有思维的。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。 广义的组合数学就是离散数学，离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。 狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。 组合数学中有几个著名的问题： 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。 船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？ 这是线性规划的问题。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。 货郎问题：一个货郎要去若干城镇卖货，然后会到出发地，给定各个城镇之间的旅行时间，应怎么样计划他的路线，使他可以去每个城镇而且所用的时间最短。这个问题至今都没有有效的算法。 这几个问题将组合数学研究的问题具体表现出来，同时也可以看出他在我们生活中有着很重要的地位。 组合数学中主要可以分成以下几个部分：排列组合与容斥原理、二项式定理、递推关系与生成函数、polya定理。下面我将以这四个部分分别介绍组合数学的各方面问题。 1、排列组合与容斥原理： 排列组合里面的4个重要的基本原理：加法原理、乘法原理、减法原理、除法原理 前面两个最为基本，后面两个是根据前两个派生出来的。乘法原理有的时候的应用很巧妙，可以作为一种打开思路的办法。
电子科技大学研究生试卷 （测试时间：至，共__2_小时） 课程名称图论及其使用教师学时60 学分 教学方式讲授考核日期_2012__年___月____日成绩 考核方式：（学生填写） 一、填空题（填表题每空1分，其余每题2分，共30分) 1．n 阶k 正则图G 的边数()m G =___ ___2 nk ； 2．3个顶点的不同构的简单图共有___4___个； 3．边数为m 的简单图G 的不同生成子图的个数有__2___m 个； 4. 图111(,)G n m =和图222(,)G n m =的积图12G G ?的边数为1221____n m n m +； 5. 在下图1G 中，点a 到点b 的最短路长度为__13__； 6. 设简单图G 的邻接矩阵为A ，且 23 112012********* 102001202A ?? ? ? ?= ? ? ??? ，则图G 的边数为 __6__； 7. 设G 是n 阶简单图，且不含完全子图3K ，则其边数一定不会超过2___4n ?? ????； 8．3K 的生成树的棵数为__3__; 9. 任意图G 的点连通度()k G 、边连通度()G λ、最小度()G δ之间的关系为 __()()()____k G G G λδ≤≤； 10. 对下列图，试填下表（是??类图的打〝√ 〞，否则打〝?〞）。 ① ② ③ 学号姓名学院 ……………………密……………封……………线……………以……………内……………答……………题……………无……………效…………………… 4 5 6 6 4 1 1 2 7 2 4 3 a b G 1
能一笔画的图 Hamilton 图 偶图 可平面图 ① ? √ ? √ ② ? ? ? √ ③ ? √ √ √ 二、单项选择(每题2分，共10分) 1．下面命题正确的是(B ) 对于序列(7,5,4,3,3,2)，下列说法正确的是： (A) 是简单图的度序列； (B) 是非简单图的度序列; (C) 不是任意图的度序列; (D)是图的唯一度序列. 2．对于有向图，下列说法不正确的是(D) (A) 有向图D 中任意一顶点v 只能处于D 的某一个强连通分支中； (B) 有向图D 中顶点v 可能处于D 的不同的单向分支中; (C) 强连通图中的所有顶点必然处于强连通图的某一有向回路中; (D)有向连通图中顶点间的单向连通关系是等价关系。 3.下列无向图可能不是偶图的是( D ) (A) 非平凡的树； (B)无奇圈的非平凡图； (C) n (1)n ≥方体； (D) 平面图。 4.下列说法中正确的是( C ) (A)连通3正则图必存在完美匹配； (B)有割边的连通3正则图一定不存在完美匹配； (C)存在哈密尔顿圈的3正则图必能1因子分解； (D)所有完全图都能作2因子分解。 5. 关于平面图，下列说法错误的是( B ) (A) 简单连通平面图中至少有一个度数不超过5的顶点； (B)极大外平面图的内部面是三角形，外部面也是三角形； (C) 存在一种方法，总可以把平面图的任意一个内部面转化为外部面； (D) 平面图的对偶图也是平面图。 三、 (10分)设G 和其补图G 的边数分别为12,m m ，求G 的阶数。 解：设G 的阶数为n 。 因12(1) 2n n m m -+=…………………………………4分 所以：212220n n m m ---=……………………..2分
组
合
数
学
Combinatorics
马昱春 MA Yuchun myc@https://www.doczj.com/doc/5315541318.html,
1
组
合
数
学
Combinatorics
组合数学:有人认为广义的组合数学就是离散数学，也有人认 为离散数学是狭义的组合数学和图论、代数结构、数理逻辑 等的总称。但这只是不同学者在叫法上的区别。总之，组合 数学是一门研究离散对象的科学。
https://www.doczj.com/doc/5315541318.html,/zh-cn/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6
Combinatorics: Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics.
https://www.doczj.com/doc/5315541318.html,/wiki/Combinatorics 2
组合数学与离散数学
? 狭义的组合数学主要研究满足一定条件的组态（ 也称组合模型）的存在、计数以及构造等方面的 问题。
– 组合数学的主要内容有组合计数、组合设计、组合矩 阵、组合优化等。
? 离散数学(Discrete mathematics)是数学的几个分 支的总称，以研究离散量的结构和相互间的关系 为主要目标，其研究对象一般地是有限个或可数 无穷个元素；因此它充分描述了计算机科学离散 性的特点。
– 离散数学通常研究的领域包括：数理逻辑、集合论、 关系论、函数论、组合学、代数系统与图论。 。
3
1 2017年图论课程练习题 一．填空题 1.图1中顶点a 到顶点b 的距离d (a ,b )= 。 a b 9 图1 1 2.已知图G 的邻接矩阵0 11011 01001 1010001011001 0A = ，则G 中长度为2的途径总条数为 。 3.图2中最小生成树T 的权值W (T )= 。 4.图3的最优欧拉环游的权值为 。 12 图 2
2 图3 5.树叶带权分别为1,2,4,5,6,8的最优二元树权值为 。 二．单项选择 1．关于图的度序列，下列说法正确的是( ) (A) 对任意一个非负整数序列来说，它都是某图的度序列； (B) 若非负整数序列12(,,,)n d d d π= 满足1n i i d =∑为偶数，则它一定是图序 列； (C) 若图G 度弱于图H ，则图G 的边数小于等于图H 的边数； (D) 如果图G 的顶点总度数大于或等于图H 的顶点总度数，则图G 度优 于图H 。 2．关于图的割点与割边，下列说法正确的是（ ） (A) 有割边的图一定有割点； (B) 有割点的图一定有割边； (C) 有割边的简单图一定有割点； (D) 割边不在图的任一圈中。 3.设()k G ，()G λ，()G δ分别表示图G 的点连通度，边连通度和最小度。下面说法错误的是( )
3 (A) 存在图G ，使得()k G =()G δ=()G λ； (B) 存在图G ，使得()()()k G G G λδ<<； (C) 设G 是n 阶简单图，若()2n G δ ≥ ，则G 连通，且()()G G λδ=； (D) 图G 是k 连通的，则G 的连通度为k 。 4.关于哈密尔顿图，下列命题错误的是( ) (A) 彼得森图是非哈密尔顿图； (B) 若图G 的闭包是哈密尔顿图，则其闭包一定是完全图； (C) 若图G 的阶数至少为3且闭包是完全图，则图G 是哈密尔顿图； (D) 设G 是三阶以上简单图，若G 中任意两个不邻接点u 与v ，满足 ()()d u d v n +≥，则G 是哈密尔顿图。 5.下列说法错误的是( ) (A) 有完美匹配的三正则图一定没有割边； (B) 没有割边的三正则图一定存在完美匹配； (C) 任意一个具有哈密尔顿圈的三正则图可以1因子分解； (D) 完全图21n K +是n 个哈密尔顿圈的和。 三、 设无向图G 有10条边，3度与4度顶点各2个，其余顶点度数均小于3，问G 中至少有几个顶点？在最少顶点数的情况下，写出G 的度序列，该度序列是一个图序列吗？。
组合数学与图论复习题及答案 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个整数a 1，a 2 ，…，a 52 被100除的余数分别是r 1 ,r 2 ,…,r 52 ，而任意一 个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将 r 1,r 2 ,…,r 52 放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj， 要么有ri＋rj＝100，也就是说ai－aj|100或者ai＋aj|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). 令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。 在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者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?
-- 本试卷满分90分 (计算机科学与技术学院0９级各专业) 一、填空（本题满分１0分,每空各1分) 1.设B A ,为集合,则A B B A = )\(成立的充分必要条件是什么？(A B ?) ２.设}2,1{},,,2,1{==Y n X ,则从X 到Y 的满射的个数为多少?（22-n ) ３．在集合}11,10,9,8,4,3,2{=A 上定义的整除关系“|”是A 上的偏序关系， 则 最大元是什么? ( 无 ） 4．设{,,}A a b c =，给出A 上的一个二元关系,使其同时不满足自反性、反自 反性、对称性、反对称和传递性的二元关系。({(,),(,),(,),(,)}R a a b c c b a c =） ５．设∑为一个有限字母表,∑上所有字(包括空字）之集记为*∑，则*∑是 否是可数集? （ 是 ) ６.含5个顶点、3条边的不同构的无向图个数为多少？ （ ４ ） 7.若G 是一个),(p p 连通图，则G 至少有多少个生成树? （ 3 ） 8. 如图所示图G ,回答下列问题： (１）图G 是否是偶图? ( 不是 ) (2）图G 是否是欧拉图? ( 不是 ） (3)图G 的色数为多少？ ( 4 ) 二、简答下列各题（本题满分40分） 1．设D C B A ,,,为任意集合，判断下列等式是否成立?若成立给出证明，若不 成立举出反例。(6分) (1))()()()(D B C A D C B A ??=? ； （2）()()()()A B C D A C B D ?=??。 解:（1）不成立。例如}{,a c B D A ====φ即可。 （2）成立。(,)x y ?∈()()A B C D ?，有,x A B y C D ∈∈，即 ,,,x A x B y C y D ∈∈∈∈。所以(,),(,)x y A C x y B D ∈?∈?,因此 (,)()()x y A C B D ∈??,从而()()A B C D ??()()A C B D ??。 反之,(,)x y ?∈()()A C B D ??，有,,,x A x B y C y D ∈∈∈∈。即 (,)x y ∈()()A B C D ?，从而()()A C B D ???()()A B C D ?。