图论与组合数学期末复习题含答案
组合数学部分
第1章 排列与组合
例1：
1)、求小于10000的含1的正整数的个数；
2、)求小于10000的含0的正整数的个数；
解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个
2)、“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有()
()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。
例2：
从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？
解：将[1,300]分成3类：
A={i|i ≡1(mod 3)}={1,4,7,…,298},
B={i|i ≡2(mod 3)}={2,5,8,…,299},
C={i|i ≡0(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 个有标志顶点的数的数目等于2-n n ）
1）、写出右图所对应的序列；
2）、写出序列22314所对应的序列；
解：
1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子
节点相连接的线），而与这个去掉的叶子节点相邻的另外一个点值则记入序列。如上图所示，先去掉最小的叶子节点②，与其相邻的点为⑤，然后去掉叶子节点③，与其相邻的点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。
2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：7。我们再将给出序列22314写在第一行，插入后的递增序列写在第二行。如下图第一行所示：
??→????? ??--②⑤67112223344522314??→????
? ??--②⑥11223344672314 ??→????? ??--③②11233447314??→????
? ??--①③11344714
?
?→
?
??
?
?
?
?
-
-④
①
1447
4
??
?
?
?
?
47
。我们每次去掉第一行第一个数，并在第二行寻找第一个无重复的元素5并将它取出，
将⑤与②连接起来，并在第二行去掉第一行的第一个元素②，剩下的序列为1122334467，依次执行下去。最终剩下的两个元素（47）连在一起。则形成了以下的树。
例4：（圆排列问题：从n个字符中取r个不同的字符构成圆排列的个数为()()
n
r
r
r
n
P
≤
≤
,
。）
5对夫妇出席一宴会，围一圆桌坐下有多少种方案？要求每对夫妇相邻而坐，方案有多少种？
解：1）、此问便是考查圆排列的公式定义，由()()()n
r
r
r
n
P
r
n
Q≤
≤
=0
,
,可得，排列
方式有()()!9
10
!
10
10
10
,
10
10
,
10=
=
=
P
Q种。
2）、同样，先将5个丈夫进行圆排列则有24
5
!5
=种，再将5个妻子插到丈夫的空隙之中，每个妻子只有两种选择，要么在丈夫的左边，要么在右边。因此由52种插入的方法，所以一共有52
!4?种。有错误！
例5：（允许重复的排列）
已知重集{}d
c
b
a
S3,4,5,
6
=，做重集S的全排列，问有多少中排列方案？
解：设可重复{}k
k
a
n
a
n
a
n
S?
?
?
=,
,
,
2
2
1
1
，其中，
k
a
a
a,
,
,
2
1
为S中k个不同元
素，则S的个数为
k
n
n
n
n+
+
+
=
2
1
，S的全排列为：
!
!
!
!
2
1k
n
n
n
n
则据题意可得：方案数为
!3!4!5!6
!
18
?
?
?
。
列6：（允许重复的组合）
试问()4z
y
x+
+有多少项？
解：由于()()z
y
x
z
y
x+
+
=
+
+4()z
y
x+
+()z
y
x+
+()z
y
x+
+，相当于从右边每
个括号里取一个元素相乘，而元素可以对应相同（如4个括号我都取x ）或者不同。这就相当于将4个无区别的球放进3个有区别的盒子，由于在n 个不同元素中取r 个进行组合，允许重复，则组合数为()r r n C ,1-+。（或者说r 个无区别的球放进n 个有区别的盒子里，每个盒子球数不限，则共有()r r n C ,1-+种）。问题等价于从3个元素中取4个做允许重复的组合，15230!2!4!6464134===???
? ??=???? ??-+项。 例6：（线性方程的整数解个数问题）
已知线性方程b x x x n =+++ 21，n 和b 都是整数，1≥n ，求此方程非负整数解的个数？
解：方程的非负整数解{
}n ξξξ,,,21 对应一个将b 个无区别的球放进n 个有区别的盒子()n x x x ,,,21 的情况，允许一盒多球，故原式可以等价转化为将将1到n 的正整数取b 个作为允许重复的组合，其组合数为???
?
??-+b b n 1个。 例7：（不相邻的组合） 从{
}7,6,5,4,3,2,1=A 中取三个元素做不相邻的组合，有多少种方式？ 解：由于从{
}n A ,,2,1 =中，取r 个作不相邻的组合，其组合数为()r r n c ,1+-，因此在此题中3,7==r n ，组合数种类有1012120!2!3!5353137===???
? ??=???? ??+-种。 例8：（全排列的三种生成算法）
（1）、已知4000=m ，!74000!6<<，求m 对应的序列。
（2）、利用字典序法求求839746521的下一个排列。
解：（1）、由于0到1!-n 中的任何整数m 都可以唯一表示为()()!1!2!2!11221?+?++-+-=--a a n a n a m n n 其中i a i ≤≤0，11-≤≤n i ，可以证明从0到1!-n 的!n 个整数与()1221,,,,a a a a n n --一一对应，我们要得到这些值就得每次除以与其相
对应的数值，就可以得到与i a 相对应的余数值i r 。因为!74000!6<<，所以：
,!2!3!4!5!640001234561a a a a a a n +?+?+?+?+?==
,0,2!32!42!52!62000240002112345612r a a a a a a n n ==+?+?+?+?==??
????=??????=
,2,!3!4!3!5!3!666632000322345623r a a a a a n n ==+?+?+?==??
????=??????= ,2,!4!5!4!6166466643345634r a a a a n n ==+?+?==?????
?=??????= ,1,!5!63351665445645r a a a n n ==+?==??
????=??????= ,3,5633655656r a a n n ====??
????=??????= ,5,06566667r a n n ===??
????=??????=所以：!22!32!41!53!654000?+?+?+?+?=。 把n-1个元素的序列()1221,,,,a a a a n n --和n 个元素的排列建立一一对应关系，从而
得到一种生成排列的算法——序数法。将()1221,,,,a a a a n n --与给出序列相对应，例如给
出4213，那么对应()123,,a a a ，由大到小的计算当前数值位置右边比此位置数值大的数值的个数，例如最大的数为4，4这个数右边有3个数比它小，所以33=a ，同理，第二个大的数为3，在3这个数右边有0个比它小的数，所以02=a ，同理对应2这个数右边有一个数比他小，所以11=a 。综上所述，对应序列为()301。
同时，由()301也可以推出最大数4的右边有3个比它小的数，为：
第二个大的数3右边比他小的数的个数为0，因此，为： 第三个大的数2右边比他小的数有1个，而1的位置也
可以确定了因此为 （2）、字典序法首先从序列()n p p p ,,,21 后向前找出第一组i i p p <-1，记下此式1-i p 的值，然后有从后向前找第一个比1-i p 的值大的数k p ，并将1-i p 和k p 调换位置，然后再将原来1-i p （现在k p ）位置以后的全部序列倒序即可以了。如题中所示的序列839746521中，首先找出从右向左第一组i i p p <-1的1-i p ，此处为4，然后找到k p 为5，将它们两调换得到839756421，然后将5后面的数逆序得到839751246。
例9：（格路模型）
一场电影的票价是50元，排队买票的顾客中有n 位是持有50元的钞票，m 位是持有
100元的钞票。售票处没有准备50元的零钱。试问有多少种排队的方法方法使得购票能顺利进行，不出现超不出零钱的状况。假设每位顾客只限买一票，而且m n ≥。
解：在格路模型中，从()()n m ,0,0→的路径选择有()()m n m c m n m n m n m ,!!!+=???
? ??+=+种。因为这个问题可以看成是由m 个向右和n 个向上组成，就是一个可重复的全排列问题。当然，将这一模型推广以后就可以应用于此题了，我们将问题简化就可以得到卖票者从没有钱到把所有票都卖完，在这个期间他必须实现每次卖票成功（即有足够的零钱找给顾客）。在格路模型中，我们把x 轴看成是m 个100元，y 轴看成是n
个50元，最重要实现将这m 个100元和n 个50元收入囊中，
而且要满足不出现找不出50元钞票的情况。问题等价于从
()0,0到()n m ,的路径中，找出y>x 且不穿越（但可以接触）
y=x 线上点的路径。然而不允许接触的情况是从()1,0点出发到
()n m ,的所有路径减去从()1,0点出发经过y=x 的路径，如右
图所示，由对称性以及m n ≥可以知道，从()1,0出发经过y=x 的路径等于由()0,1出发到达()n m ,的路径，因为由()0,1出发到达()n m ,必须经过y=x 。所以，原问题可以转化为：路径数
=()()
1,1,1--+--+m n m c m n m c =()()()()!!1!
1!1!!1n m n m n m n m --+---+=()()()??
? ??----+n m n m n m 11!1!1!1=()()()??
? ??----+n m n m n m 11!1!1!1。然而，此处是可以接触y=x 的，因此我们可以将纵坐标向下移动一个单位如右图所示：即可以接触y=x 但是不可以穿过y=x-1。此时相当于从)0,0(到()n m ,点减去从)0,0(经过y=x-1到()n m ,点的路径，而这一路径与从()1,1-到()n m ,的路径数相等，所以路径数=()()1,,-+-+m n m C m n m C =()()!!1!
n m m m n n m ++-+。 例10：（若干等式及其组合意义）
分别解释下列组式子的组合意义。
1）、()()r n n C r n C -=,,即???
? ??-=???? ??r n n r n ；
2）、())1,1(),1(,--+-=r n C r n C r n C 即???
? ??--+???? ??-=???? ??111r n r n r n ； 3）、)0,()1,1()1,1(),(),1(n C n C r r n C r r n C r r n C ++++--+++=++ ；
4）、)(),,(),(),(),(r l r l r n C r n C r l C l n C ≥--=即???
? ??--???? ??=???? ?????? ??r l r n r n r l l n ; 5）、0,2),()2,()1,()0,(≤=++++m m m C m C m C m C m
； 6）、0),()2,()1,()0,(=±-+-n n C n C n C n C ；
7）、???
? ?????? ??++???? ??-???? ??+???? ?????? ??=???? ??+0110n r m r n m r n m r n m ； 解：
1）、()()r n n C r n C -=,,即???
? ??-=???? ??r n n r n 这个式子可以被看作是格路模型的应用，从()0,0到达()r n r -,在n 个格子上面先走r 个格子，剩下再走r n -个格子，这个和先走r n -个格子，再走r 个格子是一样的。
2）、())1,1(),1(,--+-=r n C r n C r n C 即???
? ??--+???? ??-=???? ??111r n r n r n ，这个式子组合意义之一便是格路模型中的意义，从()0,0到()r n r -,的路径数可以被看成是???
? ??r n ，从()0,0到()r r n ,1--的路径数可以被看成是???
? ??-r n 1，从()0,0到()1,--r r n 路径数可以被看成是???
? ??-1r n 。就是说我们从()0,0出发都是必须先经过()r r n ,1--或()1,--r r n 再到达()r n r -,的。还有一种模型便是从含有1a 的n 个数中取出r 个数有几种取法的问题，首先我们将取得的数分为两类：一类是取得的数中含有1a ，一类是不含有1a ，因此，含有1a 的有)1,1(--r n C 种取法（先将1a 取出，再从剩余的1-n 个数中取1-r 个）。不含有1a 的有),1(r n C -种取法。因此())1,1(),1(,--+-=r n C r n C r n C 。
3）、)0,()1,1()1,1(),(),1(n C n C r r n C r r n C r r n C ++++--+++=++ ，运用上
题中的模型即可。
4）、)(),,(),(),(),(r l r l r n C r n C r l C l n C ≥--=即???
? ??--???? ??=???? ?????? ??r l r n r n r l l n ，左边相当于从n 个小球中取出l 个小球，再从l 个小球中取出r 个，右边相当于从n 个小球中先取出
r 个小球,由于这里面有重复度为???
? ??--r l r n ，它等于从剩下的r n -个小球中取出r l -个小球，这样一组合就相等了
5）、0,2),()2,()1,()0,(≤=++++m m m C m C m C m C m
，二项式模型()m m m y m m x m y x ???
? ??++???? ??=+ 0。等式右边为将m 个无区别的球放入2个有区别的盒子，左边表示其中一个盒子分别装有0个，1个，···，m 个球的组合数纸盒。
6）、0),()2,()1,()0,(=±-+-n n C n C n C n C ；二项式定理，当x y -=时，
()n n n y n n x n y x ???? ??++????
??=+ 0=0。 7）、???
? ?????? ??++???? ??-???? ??+???? ?????? ??=???? ??+0110n r m r n m r n m r n m ，等式左边相当于在有m 个红球和n 个蓝球混合后从中取出r 个球，等式右边相当于在取得的r 个球中有0个红球和r 个蓝球，一个红球和1-r 个蓝球，···，r 个红球和0个蓝球。
第2章 递推关系与母函数
例1：（母函数与递推关系）
利用母函数法求解满足递推关系()???==≥+=--1
21021F F n F F F n n n 的Fibonacci 序列的解。 解：首先，我们根据题意设母函数为() +++=2210x F x F F x G ，则：由
2
34312320
12:)
::F F F x F F F x F F F x +=++=+= 可得：211)(x x x G --=
。 令x B x A x G 2
5112511)(--++-=，解得21==B A 。
因此，?????
? ??--++-=x x x G 251112511121)(，令251,251-=+=βα，则???
? ??-+-=x x x G βα111121)(，由 +++=-22111x a ax ax 可得， ()()()
+++++++=22221121)(x x x x x G ββαα= ()()()
+++++222221x x βαβα。 因此，递推关系式为2
n
n n F βα-=，由于0,1251→<-=n ββ， 所以，n n F ???? ??+=25121，即618.12
511=+=-n n F F ?1618.1-=n n F F ，121618.0---==-n n n n F F F F 。
例2：（Fibonacci 序列的若干不等式）
（1）、证明：1221-=++++n n F F F F ；
（2）、证明：n n F F F F 21231=+++- ；
（3）、证明：122221+=+++n n n F F F F F ；
证：（1）、由于序列为Fibonacci 序列，所以有：21--+=n n n F F F ，因此： 231F F F -=，342F F F -=，···， 12+--=n n n F F F ，所以，12224321-=-=++++++n n n F F F F F F F F 。
（2）、由于序列为Fibonacci 序列，所以有：21--+=n n n F F F ，因此：121==F F ，243F F F -=，365F F F -=，···， 22212---=n n n F F F ，所以有n n F F F F 21231=+++- 。
（3）、由于序列为Fibonacci 序列，所以有：21--+=n n n F F F ，因此：
()1322222F F F F F F -==，()2433323F F F F F F -==,···，()112
-+-==n n n n n n F F F F F F 即122221+=+++n n n F F F F F 。
例3：（线性常系数齐次递推关系）
第四届全国组合数学与图论会议纪要
第四届全国组合数学与图论会议纪要 为促进我国组合数学与图论学科的进一步发展，加强国内同行的学术交流与合作，第四届全国组合数学与图论大会于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
图论期末考试整理复习资料
目录 第一章图的基本概念 (2) 二路和连通性 (4) 第二章树 (4) 第三章图的连通度 (6) 第四章欧拉图与哈密尔顿图 (8) 一，欧拉图 (8) 二．哈密尔顿图 (10) 第五章匹配与因子分解 (14) 一．匹配 (14) 二．偶图的覆盖于匹配 (15) 三．因子分解 (16) 第六章平面图 (20) 二．对偶图 (24) 三．平面图的判定 (25) 四．平面性算法 (28) 第七章图的着色 (34) 一．边着色 (34) 二．顶点着色 (35)
第九章 有向图 (40) 二 有向树 (41) 第一章 图的基本概念 1. 点集与边集均为有限集合的图称为有限图。 2. 只有一个顶点而无边的图称为平凡图。 3. 边集为空的图称为空图。 4. 既没有环也没有重边的图称为简单图。 5. 其他所有的图都称为复合图。 6. 具有二分类（X, Y ）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子 集 X 和 Y ，使得每条边的一个端点在 X 中，另一个端点在Y 中。 7. 完全偶图：是指具有二分类（X, Y ）的简单偶图，其中 X 的每个顶点与 Y 的每个顶点 相连，若 |X|=m ，|Y|=n ，则这样的偶图记为 Km,n 8. 定理1 若n 阶图G 是自补的（即 ），则 n = 0, 1（mod 4） 9. 图G 的顶点的最小度。 10. 图G 的顶点的最大度。 11. k-正则图: 每个点的度均为 k 的简单图。 例如,完全图和完全偶图Kn,n 均是正则图。 12. 推论1 任意图中，奇点的个数为偶数。 ()G δ()G ?
13. 14.频序列：定理4 一个简单图G的n个点的度数不能互不相同。 15.定理5 一个n阶图G相和它的补图有相同的频序列。 16. 17. 18.对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1) 19.定义：联图在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个 顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G2 20.积图：积图设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 = v1和u2 adj v2) 或(u2 = v2 和u1 adj v1) 时就把u 和v 连接起来所得到的图G称为G1和G2积图。记为G = G1×G2 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 adj v1) 或(u1= v1 和u2 adj v2) 时就把u 和v 连接起来所得到的图G称为G1和G2的合成图。记为G=G1[G2]。
组合数学在生活中的应用
组合数学在生活中的应用
组合数学在生活中的应用
组合数学在生活中的应用 数计学院姓名：廖梓文班别： 11数本3班学号：2011224323 摘要本文从对组合数学的一些基本概念和方法入手,结合具体的应用举例和数学史上的著名故事作为论题进行研究,进行了较全面的资料搜集.使人们加深对组合数学的理解,并应用于生活. 关键词:组合数学;数学游戏 1 引言 本文通过具体的应用实例和数学史上的一些故事和难题,介绍了组合数学是如何在生活中应用的.在研究了一些典型的例子和趣味性的故事的基础上,系统的查阅了相关文献，并结合生活中涉及组合数学的相关知识进行阐述,具体说明了组合数学的基本方法及其在生活中的应用.这样就使组合数学显得更加形象,也使抽象的理论概念变得浅显具体,更易被初学者理解和接受,以至于可以激发人们在生活中应用组合数学的意识. 2 组合数学的历史 组合数学是一门既古老又年轻的数学分支。随着计算机的普及推广,组合数学这门古老的学科焕发出蓬勃的生机. 组合数学不仅在基础数学研究中具有极其重要的地位，在其他的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。 我国古人在《河图》《洛书》中便已经对一些有趣的组合问题给出了正确的解答。中国最早的组合数学理论可追溯到宋朝时期的”贾宪三角”, 后来被杨辉引用, 所以普遍称之为“杨辉三角”, 这在西方是1654年由帕斯卡提出，但比中国晚了400多年。近代，由于计算机的出现，组合数学这门学科得以迅猛发展，成为了一个重要的数学分支。近代图论的历史可追溯到18世纪的七桥问题—穿过K?nigsberg城的七座桥，要求每座桥通过一次且仅通过一次。Euler1736年证明了不可能存在这样的路线。 4.组合数学的基本解题方法
华中师范大学组合数学期末考试试卷(A)
-可编辑修改- 华中师范大学组合数学期末考试试卷（A ） 课程名称组合数学课程编号 任课教师 王春香 题型 填空题 证明题 计算题 应用题 总分 分值 20 20 40 20 100 得分 得分 评阅人 一、填空题：（20分）（共5题，每题4分） 1. 由n 个字符组成长为m 的字符串，则相同的字符不相邻的方案数为 n n m C 1+- 。 2. 5男4女，分成两队，每队4人，要求每队至少有1位女生的方案数： 1680 。 3．求12341234+++20,3105,x x x x x x x x =≥≥≥≥，，，的整数解的个数 144 。 4．平面上有n 条直线，其中无两条平行，无三线共点，则交点数为： n-1 。 5．50！尾部有 12 个数字0 。 得分 评阅人 二、证明题（20分）：（共2题，每题10分） 21211. 1n p n n p n p n =-????= ? ?-???? ∑证明： 院（系 ）： 专业： 年级： 学生 姓名： 学号： --- -- -- --- -- -- -- --- -- -- -- --- -- -- -- --- -- -- -- -- -- -- 密 -- -- -- -- --- -- -- -- --- -- -- -- --- -- -- - 封 --- -- -- --- -- -- -- --- -- -- -- -- -- 线 ---- -- -- -- --- -- -- -- --- -- -- -- --- -- -- -- --- -- -- -- --- -- -- -- --
-可编辑修改-
离散数学图论部分经典试题及答案
离散数学图论部分综合练习 一、单项选择题 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
同济大学组合数学期末试卷
1．用两种方法证明公式：. 2．将个相同的球放到个不同的盒子里，每个盒子至少有个球（），问有多少种放法？ 3．求解递推关系： 二．（10分）用集合可以组成多少个不同的位数？其中要求1和3每个出现偶数次. 三．（10分）求在1和1000之间不能被5，6和8整除的数的个数. 四．（10分）有级台阶，一个小孩从下往上走，每次只能跨一级或两级，问他从地面走到第级台阶有多少种不同的方法？ 五．（10分）设表示把元集划分成非 空子集的方法数，当元集时，求出方法数. 六．（10分）从4种水果中选出个，使得苹果数为偶数个，香蕉数为5的倍数，橘子数不超过4个，梨子数为0或1个，问选出个的选法数. 七．（18分）（1）用四颗珠子穿项链，现可对珠子染3种不同的颜色，问可得到多少个不同的项链？（注：项链可旋转或翻转） （2）设计一个由6个花瓣和1个中心花蕊组成的图案，这7个部分由3种不同的颜色组成，要求其中出现2蓝2红3黄，此花朵可以旋转，问可以有多少种不同的设计方案？ 保洁员协议书 甲方：村村民委员会 乙方：，身份证号： 为了确保本村的清洁卫生得到正常有序地运行，使全村的环境卫生保持清洁.干净。切实做好全村生活垃圾的收集处置工作。经甲.乙双方协商同意，特订如下协议： 一.垃圾收集范围： 屯主要道路的路边.溪边经常保持整洁，及时清理白色污染.无明显垃圾堆积物：清除屯主要道路两边杂草：对屯内公共树木养护：沟 乱刻画.乱散发. 止和清理。 二.保洁员报酬工资合计 周清洁2 月发放。 三.保洁所需一切工具均由乙方自己承担，乙方还要自备垃圾清运车辆。在工作期间注意自身安全，如发生意外，其责任自负，甲方不承担任何责任。 四.工作要求: 1.屯内道路路段保洁要求：对屯内道路及路两旁的沟.涵管必须清理疏通，道路两旁的绿化
图论与组合数学期末复习题含答案
组合数学部分 第1章 排列与组合 例1： 1)、求小于10000的含1的正整数的个数； 2、)求小于10000的含0的正整数的个数； 解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个 2)、“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有() ()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。 例2： 从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？ 解：将[1,300]分成3类： A={i|i ≡1(mod 3)}={1,4,7,…,298}, B={i|i ≡2(mod 3)}={2,5,8,…,299}, C={i|i ≡0(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 个有标志顶点的数的数目等于2-n n ） 1）、写出右图所对应的序列； 2）、写出序列22314所对应的序列； 解： 1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子 节点相连接的线），而与这个去掉的叶子节点相邻的另外一个点值则记入序列。如上图所示，先去掉最小的叶子节点②，与其相邻的点为⑤，然后去掉叶子节点③，与其相邻的点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。 2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：7。我们再将给出序列22314写在第一行，插入后的递增序列写在第二行。如下图第一行所示： ??→????? ??--②⑤67112223344522314??→???? ? ??--②⑥11223344672314 ??→????? ??--③②11233447314??→???? ? ??--①③11344714
组合数学前沿介绍
组
合
数
学
Combinatorics
马昱春 MA Yuchun myc@https://www.wendangku.net/doc/3614935740.html,
1
组
合
数
学
Combinatorics
组合数学:有人认为广义的组合数学就是离散数学，也有人认 为离散数学是狭义的组合数学和图论、代数结构、数理逻辑 等的总称。但这只是不同学者在叫法上的区别。总之，组合 数学是一门研究离散对象的科学。
https://www.wendangku.net/doc/3614935740.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.wendangku.net/doc/3614935740.html,/wiki/Combinatorics 2
组合数学与离散数学
? 狭义的组合数学主要研究满足一定条件的组态（ 也称组合模型）的存在、计数以及构造等方面的 问题。
– 组合数学的主要内容有组合计数、组合设计、组合矩 阵、组合优化等。
? 离散数学(Discrete mathematics)是数学的几个分 支的总称，以研究离散量的结构和相互间的关系 为主要目标，其研究对象一般地是有限个或可数 无穷个元素；因此它充分描述了计算机科学离散 性的特点。
– 离散数学通常研究的领域包括：数理逻辑、集合论、 关系论、函数论、组合学、代数系统与图论。 。
3
西安交通大学组合数学期末重点
组合数学期末重点 第一章：7 11 14 25 26 7. n 个男n 个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？ [解].(1)若第1个位置是男，有n ?n ?(n -1)?(n -1)???3?3?2?2?1?1=(n!)2种排法； 若第1个位置是女，也有(n!)2种排法； 故n 个男n 个女排成一男女相间的队伍，有2(n!)2种不同的排法。 因为若不记座位的差别，只记人与人之间的相对位置的变化，则每一种坐法可产生2n 个男女相间的排列，从而坐法为22 ])!1[()!1(!2)!(2-=-=n n n n n n 种， 若不记顺、逆时针则有坐法22])!1[(2 1 )!1(!2122)!(2-=-=?n n n n n n 种。 (2)若第1个座位坐男，有n 个可能，则第2个坐女为n 个可能，……，根据乘法原理，故有n ?n ?(n -1)?(n -1)???3?3?2?2?1?1=(n!)2种方案。同理，第1个座位坐女，也有(n!)2种方案。故有2(n!)2种方案。 11.凸10边形的任意三条对角线不共点。试求这凸10边形的对角线交于多少个点？又把所有的对角线分割成多少段？ [解].(参见柯召《组合数学》上册。P 34 例1.6.1) (2)从上。一个点引出的7条线中第一条线上有7个点，故将该线段分成8段；第二条线上有12个点，故将该线段分成13段，故从一个点出发的7条线上的段数为 第11题图1 第11题图2
8+13+16+17+16+13+8=91 故有10个点。故总的段数可为91?10=910。但有重复，重复数为2（因为每条线有两个端点）。故总的段数为 4552 910 =。 14.从26个英文字母中取出6个字母组成一字,若其中有2或3个母音.问分别可构成多少个字(不允许重复)? [解].英语中有6个元音字母a,e.i,(y),o,u,其余20个是辅音。 (1)若取出6个字母组成一字,其中有2个元音,可构成 1234561256123417181920!626420???????????????=???? ? ?????? ??=52 326 000 (2)若有三个元音,可构成 123456123456123181920!636320???????????????=???? ? ?????? ??=16 416 000； 另一种解法认为有5个元音，其余21个是辅音 (1)若取出6个字母组成一字,其中有2个元音,可构成 1234561245123418192021!625421???????????????=???? ? ?????? ??=43 092 000 (2)若有三个元音,可构成 1234561245123192021!635321?????????????=???? ? ?????? ??=9 576 000。 25.5台教学机器m 个学生使用，使用第1台和第2台的人数相等，有多少种使用方案？ [解].先从m 个学生中选取k 个使用第1台机器，再从剩下的m -k 个学生中选取k 个使用第2台机器，其余m -2k 个学生可以任意使用剩下的3台机器，按乘法原理，其组合数为C (m,k) C (m -k ,k )?3(m -2k )。这里k=0,1,2,?,q (?? ? ???=2m q )，于是，按加法原理，共有 ) 2(q k 3 ),(),(k m k k m C k m C -=?-∑种使用方案。 26.在由n 个0及n 个1构成的字符串中，任意前k 个字符中，0的个数不少于1的个数的字符串有多少？ [解].转化为格路问题（弱领先条件—参见P36例4该例是强领先条件）。即从(0,0)到(n,n)，只能从对角 线上方走，但可以碰到对角线。它可看作是从(0,1)到(n,n+1)的强领先条件（只能从对角线上方走，但不可以碰到对角线）的格路问题。更进一步的，它 可看作是从(0,0)到(n,n+1)的强领先条件的格路问题(n+1,n+1) (0,1) (1,0) (n,n+1) (n,n) (0,0) 第26题图1
电子科技大学2017年图论期末试卷
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?
组合数学在计算机中的应用
目录 摘要 (1) 1.组合数学概述 (1) 2.组合数学在生活中的应用 (1) 3.组合数学与计算机软件 (1) 3.1 信息时代的组合数学 (2) 3.2 组合数学在计算机软件的应用 (2) 3.3组合数学与计算机软件的关系 (2) 3.4组合数学在国外软件业的发展状况 (2) 4 Ramsey 数在计算机科学中的应用 (3) 4.1Ramsey 定理和Ramsey 数 (3) 4.2信息检索 (3) 参考文献 (5)
组合数学在计算机中的应用 摘要：介绍了组合数学的概念、起源与研究的主要内容,分析了组合数学的特点以及其在生活中的应用,阐述了组合数学与计算机软件的联系,并着重通过两个例子说明了Ramsey 数在计算机科学的信息检索中的重要应用。 关键词：组合数学;组合算法;Ramsey 数;信息检索; 1：组合数学概述 组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。 2：组合数学在生活中的应用 在日常生活中我们常常遇到组合数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。 当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。航空调度和航班的设定也是组合数学的问题。怎样确定各个航班以满足不同旅客转机的需要，同时也使得每个机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，怎样作最合理的调整，这些都是组合数学的问题。 组合数学在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。 总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。 3：组合数学与计算机软件 随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。
2015电子科技大学_图论期末考试复习题
2015电子科技大学 图论考试复习题 关于图论中的图，以下叙述不正确的是 A ．图中点表示研究对象，边或有向边表示研究对象之间的特定关系。 B ．图论中的图，画边时长短曲直无所谓。 C ．图中的边表示研究对象，点表示研究对象之间的特定关系。 D ．图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。 一个图中最长的边一定不包含在最优生成树内。 下面哪个图形不与完全二分图K 3,3同构？ A ． B ． C ． D ． 有10条边的5顶单图必与K 5同构。 完全二分图K m ,n 的边数是 A ．m B ．n C ．m +n D ．mn 无向完全图K n 的边数为 A ．n B ．n 2 C ．n (n -1) D ．n (n -1)/2 若一个无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有 条边。 对于两个图，如果顶点数目相等，边数相等，次数相等的顶点数目也相等，则这两个图同构。 有15个顶的单图的边数最多是 A ．105 B ．210 C ．21 D ．45 图G 如右，则dacbeb A ．是G 中的一条道路 B ．是G 中的一条道路但不是行迹 C ．是G 中的一条行迹但不是轨道 D ．不是G 的一条道路 图G 如右，则befcdef A ．是G 的一个圈 B ．是G 的一条道路但不是行迹 C ．是G 的一条行迹但不是轨道 D ．是G 的一条轨道但不是圈
v1 36 7 图G如右图所示，则ω (G)= A．1 B．2 C．7 D．8 下列图形中与其补图同构的是 A．B．C．D． 求下图中顶u0到其余各顶点的最短轨长度。 u0v1=8，u0v2=1，u0v3=4，u0v4=2，u0v5=7，v1v2=7，v1v3=2，v1v6=4，v2v4=2，v2v7=3，v3v5=3，v3v6=6，v4v5=5，v4v7=1， v5v 6 =4，v 5 v7=3，v6v7=6， 请画出6阶3正则图。 请画出4个顶，3条边的所有非同构的无向简单图。 设图G={V(G)，E(G)}其中V ={ a1, a2, a3, a4, a5}，E(G)={(a1, a2)，(a2, a4)，(a3, a1)，(a4, a5)，(a5, a2)}，试给出G的图形表示并画出其补图的图形。 一个图的生成子图必是唯一的。 不同构的有2条边，4个顶的无向简单图的个数为 A．1 B．2 C．3 D．4 画出5个具有5个结点5条边的非同构的无向连通简单图。 u0到v1的最短轨长度为6，u0到v2的最短轨长度为1，u0 到v3的最短轨长度为4，u0到v4的最短轨长度为2，u0到v5的最短轨长度为6 ，u0到v6的最短轨长度为9，u0到v7的最短轨长度为3。
组合数学-浅谈组合数学与计算机科学
浅谈组合数学与计算机科学 摘要：组合数学，又称为离散数学，是一门研究离散对象的科学。组合数学是计算机出现以后迅速发展起来的一门数学分支，随着计算机科学的日益发展，组合数学的重要性也日渐凸显。 关键词：组合数学计算机欧拉回路 Abstract: The combination of mathematics, also known as discrete mathematics, is a study of discrete objects. A combination of computer mathematics is a branch of mathematics developed rapidly since, with the increasing importance of the development of computer science, combinatorial mathematics has become more prominent. Key words: Combinatorics Computer Euler circuit 1.组合数学简述 组合数学是一门古老而又新兴的数学分支。我国古人早在《河图》、《洛书》中已对一些有趣的组合问题给出了正确的解答。近代随着计算机的出现,组合数学这门学科得到了迅猛的发展,成为了一个重要的数学分支。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。 组合数学主要研究符合一定条件的组态对象、计数及构造等方面的问题。离散构形问题是组合数学的主要研究内容，主要包括：①构形构形的存在性问题；②构形的构造性问题；③构形的计数问题；④构形的最优化问题。 现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等; 另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。 电子计算机处理的信息，都是仅用“0”与“1”两个简单数字表示的信息，或者是用这种数字进行了编码的信息。所以离散对象的处理就成了计算机科学的核心，而组合数学是一门研究离散对象的科学。现代数学的研究内容主要包括两个方面：一方面类是研究连续对象的，如分析、代数等，另一方面就是研究离散对象的组合数学。
组合数学试题
《组合数学》期末试题（A ）姓名班级学号成绩 一，把m 个负号和n 个正号排在一条直线上，使得没有两个负 号相邻，问有多少种不同的排法。 二，在1和100之间既不是某个整数的平方，也不是某个整数的 立方的数有多少个？ 三，边长为1的等边三角形内任意放10个点，证明一定存在两 个点，其距离不大于1/3。 四，凸10边形的任意三条对角线不共点，试求(1)这凸10边形的 对角线交于多少个点？(2)又把所有对角线分割成多少段？五，求和=?? ???∑k－（－）k+1111n k n k 六，求解递推关系--++=??==?12016930,1 n n n a a a a a 七，用红白蓝三种颜色对1×n 的方格涂色，每个方格只能涂一种颜色，如果要求偶数个方格涂成红色，问有多少种方法？ 八，用红、蓝二种颜色对1×n 的方格涂色，每个方格只能涂一种颜色，如果要求涂成红色的两个方格不能相邻，问有多少种方法？注，1-4、6题各15分，第5题10分，第7题8分，第八题7分。
北京邮电大学2005 ——2006 学年第1 学期 《组合数学》期末试题答案 一， (15) 解： 由于正负号不能相连，故先将正号排好，产生n+1个空档。 --------5分 则负号只能排在两个正号之间，这相当于从n+1个数中取m 个数的组合，故有---------10分 1n m +????? ?种方式。----15 备注：若写出m>n+1时为0，m=n+1时为1，给5分 二， （19分） 解：设A 表示是1-100内某个数的平方的集合，则 |A|=10, -----4分 设B 表示是1-100内某个数的立方的集合，则|B|=4, --8分 |A ∩B|=2, -----12分 由容斥原理得 100|||||| 100104288A B A B A ∩=??+∩=??+=B --------19分 三， （15分） 证明：将此三角形剖分成9个小的边长为1/3的等边三角形。 - ------5分 由鸽巢原理，必有两点在某一个小三角形内，----12分 此时，这两点的距离不超过小三角形边长1/3。从而得证。 -------15分 四， （15分） 解：（1）由于没有三条对角线共点，所以这凸多边形任取4点，组成的多边形内唯一的一个四边形，确定唯一一个交点，--5分 从而总的交点数为C(10,4)=210-------------10分 （2）如图，不妨取顶点1，考察由1出发的对角线被其他对角线 剖分的总数。不妨设顶点标号按顺时针排列，取定对角线1 i
图论与组合数学 教学大纲 2016 修改版
《图论与组合数学》教学大纲 一、课程名称：图论与组合数学 二、课程代码：021********* 三、课程英文名称：Graph Theory and Combinatorics 四、课程负责人：刘任任，肖芬，曹春红 五、学时与学分：48学时（理论40学时，实验8学时），3.0学分 六、课程性质：必修 七、适用专业：工科本科计算机科学与技术专业 八、选课对象：计算机科学与技术专业 九、预修课程：集合论与数理逻辑、C语言程序设计I、数据结构 十、课程教材与参考书目： 课程教材： 1.刘任任编著，《离散数学》，中国铁道出版社，2009年12月； 2.刘任任主编，《离散数学题解与分析》，中国铁道出版社，2010年10月。 参考书目： 1.Kneneth H. Rosen, Discete Mathematics and Its Applications, Fifth Edition,2003年； 2.Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall Inc., 2000年； 3.Kolman B., etc., Discrete Mathematical Structures，Prentice Hall Inc., 2001； 4.Brualdi, R.A. (美)，组合数学(第四版)，北京机械工业出版社，2005年2月； 5.卢开澄，组合数学，清华大学出版社， 6.孙吉贵等编著，《离散数学》，高等教育出版社，2002年； 7.陈莉等编著，《离散数学》，高等教育出版社，2002年。 十一、开课单位：信息工程学院 十二、课程与能力培养中的对应关系 1、能力1.2: 掌握计算机科学与技术专业所要求的数学和自然科学基本知识，能将其用于计算机复杂工程问题的分析与建模； 2、能力2.1：掌握文献检索、资料查询的基本方法，能够运用现代技术获取相关文献，具有资料阅读和文献研究能力，并用于计算机科学与技术相关的复杂工程问题的分析和推理； 3、能力2.2：通过理论与实践相结合的系统学习，能够识别复杂工程问题中所涉及的数学、自然科学及计算机科学与技术专业的相关理论知识。 十三、课程的目标 图论和组合数学是现代数学的重要分支，是研究离散结构的存在、计数、分析和优化等问题的一门科学，是计算机科学与技术专业的基础理论课程。通过本课程的学习，使学生掌握图论与组合数学的基本原理和方法，了解和掌握无向图、有向图、连通图、排列与组合、容斥原理、递推关系和生成函数等基本知识，灵活运用所学知识对一些简单问题进行建模并编程求解。
- 图论试卷A卷-14数本
- 图论试卷及参考答案A-13级数学本科
- 离散数学图论部分经典试题及答案
- 运筹学期末试题
- --运筹学期末考试试题及答案
- 电子科大研究生图论05-14年图论期末试题
- 图论期末复习题(16年)
- 《运筹学》期末考试试题及参考答案
- 运筹学2015学年期末考试题A卷与答案
- 图论期末复习题(16年)
- 图论试题(中法)
- 2011研究生图论期末试题
- 电子科技大学研究生试题图论及其应用参考答案完整版
- 集合论与图论 期末考试试题 A 卷,2008年1月
- 图论试卷及参考答案A-13级数学本科
- (完整版)图论期末复习题(16年)
- 电子科技大学2017年图论期末试卷
- 运筹学2016年学年期末考试题A卷及答案解析
- 北京大学集合论与图论SG2017-期末考试题试题-final-答案
- 电子科大研究生图论06-14年图论期末试题