组合数学及其图论
1、一个图G 是指一个有序三元组（V （G ），E （G ），G ?），其中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)/2
6、如果一条途径的_________与___________相同，就称这条途径为闭途径。
起点 终点
7、如果对图G=（V ，E ）的任何两个顶点u 与v ，G 中存在一条（u-v ）路，则称G 是___________否则称为是______________
连通图、 非连通图
8、设G 是P 阶连通图，则__________________.
q(G)≥p-1 9、若二分图
有Hamilton 回路，则
与
满足 。
10、若G 是2-边连通图，则G 有强连通的________________. 定向图
11、边数最少的连通图是 。
树
12、没有回路的连通图称为_______________.
树
13、的图是图或图。
平凡图，不连通图
14、树T的每一个非悬挂点都是T的 __________.
割点
15、二分图中若与满足，则必有完美对集。
16、给定一个图G，如果图G的一个生成子图T是一棵树，则称T是G的一个_______________.
生成树
17、设G是无环图，e是G的一条边，则
τ(G)=___________________________.
τ
（G－e）+τ
(G·e)
18、是阶简单图，则，等号成立当且仅当是图。
，完全图 2、
19、___________________________的生成树称为最优生成树。
连通赋权图中具有最小权
20、的一个对集是最大对集的充要条件是。
中无可扩路
21、一个有向图D，如果略去每条弧的方向时所得无向图是一棵树，就称D为_____________________.
有向树
22、经过G的每条边的迹称为G的Euler迹，如果这条迹是闭的，则称这条闭迹为G的 ________________.
Euler环游
23、是简单图且，则。
24、若 是 -正则图，则 。
25、简单图 满足 ，则 是 图。
不连通图， 平凡图 26、 的图
是 图或 图。
2
27、树 恰有两个悬挂点，则 。
连通
28、
有生成树的充要条件是 。 30
29、若
是有31个点的连通图且
中每条边都是割边，则
。
1 30、
阶图
是连通图，则
。
，
31、若
是
的一个对集，则
，等号成立当且仅当
是 对集。
完美对集
32、每位上的数字互异且非零的两位数共有____________个。 72
33、现在有10双不同的鞋。为了保证能够有一双鞋被选出，至少要从这20只鞋中取出____________只鞋。 11
34、712345()x x x x x ++++展开式中231345x x x x 的系数为____________。
420
35、序列 1, c, c 2, …, c n , …的生成函数是_______________。
1
()||11f x cx cx
=
<-;
36、数值函数f 和g 的卷积f *g 的通项f *g (r) = 。
0)
()(0
≥-∑=r i r g i f r
i .
37、叙述下列概念：发点，收点，中间点。
参考要点：D 包含两个特定的顶点x 和y ，x 设有向连通图D=（V ，A ）满足：仅有出弧而没有入弧，称为发点；y 仅有入弧而没有出弧，称为收点；D 中其余顶点既有出弧有入弧，称为中间点。
38、在一次围棋擂台赛中，双方各出n 名选手。规则是双方先各自排定一个次
序，设甲方排定的次序是1x ，,2x
，
n x ，乙方排定的次序为1y ，2y ，
n y 。1x 与1y 先比赛，胜的一位与对方下一位选手比赛。按这种方法直到有一方的
最后一位选手出场并输给对方，比赛结束。问最多进行几场比赛可定胜负（假定比赛无平局）。
参考要点：建立一个有向图D=（V ，A ），V={,,,,,,2121y y x x x n n y , }，
如果
i x 与i y 之间连一条弧，其方向从胜者指向负者。则D 的每一条弧对应
一场比赛，D 中弧的数目就是这次比赛的次数。根据规则，每一名选手至多输一场，所以D 中每个顶点的入度至多为1，但,n x n y 必有一个入度为1，另一个为0。
12))()((1
-≤+=∑=n y d x d A n
i i D i D ，即至多2n-1场比赛可定胜负。
39、用一些圆面覆盖平面上取定的2n 个点。试证：若每个圆面至少覆盖n+1个
点，则任两个点能由平面上的一条折线所连接，而这条折线整个地被某些圆面所覆盖。
参考答案：构造图G=（V ，E ）如下：V 就取平面上给定的2n 个点，两个不同的顶点如果含在同一个圆面上，就在这两个顶点之间连上一条边（边也含在这个平面上）。所得图是一个简单图，而且每个顶点的度至少是n ，即
??
?
?
??=≥22)(n n G δ，由推论，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、某编辑部收到由n 个人所寄的一些问题的解，他们发现每个人寄来四个不同问题的解，每个问题的解恰好由两个人同时给出。问他们共收到几个不同问题的解。
参考答案：首先建立图G=（V ，E ），G 的n 个顶点代表n 个人。两个不同的顶点
i
v 和
j
v 之间连接的边数等于这两个点所对应的两个人同时给出相同问题解的
个数。由条件，G 的每一条边对应一个问题的解，每个顶点的度为4。因而共收到q （G ）=2n 个不同问题的解。
42、有十七位学者，每一位都给其余的人写一封信，信的内容是讨论3个论文题目中的任一个，而且2个人相互通信所讨论的是同1个题目。证明至少有三位学者，他们之间通信所讨论的是同一个论文题目。 参考答案：做一个完全子图
17K ，它的17个顶点代表17位学者，把其中的边
染成3种颜色：如果两个学者讨论的是第i 个题目，就将连接相应的2个顶点的边染上第i 种颜色（i=1，2，3）。这样就得到3色完全图
17K 。由定理
172)1)3,3((32)1(323=+-=+-≤r r r 。因此，这个
3色完全图
17K 中有一个同色三角形。这个同色三角形所对应的3位学者之间通信所讨论
的是同一个论文题目。 43、证明
3,3K 和5K 是非平面图。
参考答案：
3,3K 含有
6个顶点，9条边，但最短回路长度为4，不满足
2
22)(---≤g g
p g g G q ，因此不是平面图。5K 有5个顶点，10条边，不
满足6)(3)
(-≤G p G q ，故不是平面图。
44、在一次象棋擂台赛中,双方各出n 名选手.比赛的规则是双方各自排定一个次序,设甲方排定的次序为x 1,x 2,…, x n ,乙方排定的次序为y 1,y 2,…,y n . x 1与y 1先比赛,胜的一位与对方输的下一位选手比赛.按这种方法进行比赛,直到有一方的最后一位选手出场比赛并且输给对方,比赛就结束,问最多进行几场比赛可定胜负(假定比赛不出现平局)?
参考要点：建立一个有向图D=(V,A),V={ x 1,x 2,…, x n , y 1,y 2,…,y n },如果x i 与y i 进行过一场比赛,就在x i 与y i 之间连一条弧.其方向从胜者指向负者,则D 的每一条弧对应一场比赛,D 中弧的数目就是这次比赛的次数.根据比赛的规则,每一名选手至多输一场,故D 中每个顶点的入度至多为1,但x n 与y n 必有一个入度为1,另一个为0.因此
|A|∑=-≤+=n
i i D i D n y d x d 112))()((
即至多进行2n-1场比赛就可以确定胜负。
45、平面上有n 条线段,n ≥3,其中任意3条都有公共端点.证明这n 条线段有一个公共端点。
参考要点：设G 是连通图,则G 中任意两个不同的顶点i v 与j v 之间有一条路连接.
若记这条路的长度为l ,显然1-≤p l .则1)
(≥≥l ij ij a r .而对于任意的)1(p i i ≤≤,
因G 连通,且3)(≥G p ,则有
0)()2(>=≥i G ii ii v d a r ,所以R(G)中没有零元素.
设i v 与j v 是G 中的任意两个不同的顶点.因为
0)1()2(≠+++=-p ij ij ij ij a a a r
存在11-≤≤p l ,)(0)1()(ij ij l ij a a a =≠,则在G 中有一条长为l 的途径连接i v 与j v .因
而从i v 与j v 有一条路,故G 是连通图。
46、证明任意六个人中有三个人互相认识，或有三个人互不认识。. 证：构图
如下：图的顶点代表这6个人，两个顶点相邻当且仅当对应的两个
人互相认识。则对于图中任意一个点
或
。不妨设
及它的3个邻点为
。若
中有任意两
个点，不妨设为
，相邻，则 对应的3个人互相认识；否则，
中
任意两个点不邻，即它们对应的3个人互不认识。 47、给定图
：
1、给出图 的一个生成树；
2、给出图 的点连通度；
3、给出图 的最大对集；
4、给出图
的一个最长回路；
5、给出图 的直径和半径。
答案
1、
2、3
3、
4、
5、2 ，2
48、试给出一个算法,求连通赋权图中最大权的生成树.
算法：
1)在中选取边，使尽可能的大；
2)若已经选定边，则在中选取边，
使满足以下两条：
I. 不含回路；
II. 在满足Ⅰ的前提下，使尽可能的大。
3）当2)不能继续执行时，停止。
49、设是连通简单图，证明中存在个顶点，使得
仍是连通图。
证：是连通简单图，设其最大度点为。设是关于的保距生成树，则，故中至少有个悬挂点，不妨设为，则连通，是的生成子图，即连通。
50、对下图，求一个最优生成树。
答案
51、证明任意六个人中有三个人互相认识，或有三个人互不认识。.
证：构图如下：图的顶点代表这6个人，两个顶点相邻当且仅当对应的两个人互相认识。则对于图中任意一个点或
。不妨设及它的3个邻点为。若中有任意两
个点，不妨设为，相邻，则对应的3个人互相认识；否则，中任意两个点不邻，即它们对应的3个人互不认识。
52、给定图
问：1、作图的一个最长回路；
2、给出图的一个生成树；
3、给出图的点连通度；
4、给出图的最大对集；
5、作出图的闭包。
答案
1、
2、
3、 3
4、
5、
53、试证明：如果无环图G的任意两顶点都被唯一的路相连，则G是树。
参考答案：证明：由于G中任意两顶点都被唯一的路相连，故G连通。
若G含有圈C，则C上的两点，在G中存在两条路相连，这与题设的“唯一”矛盾。故G中不含圈。
由树的定义知道：G是树。
54、有n张纸牌，每张纸牌的正反两面都写上1，2，......n的某一个数。
证明：如果每个数字都恰好出现两次，那么这些纸牌一定可以这样摊开，使朝上的面中1，2，3……n 都出现。
参考答案：证明：作一二分图G=（X ，Y ；E ），其中X={1，2，………n},Y={y 1
y 2 …….y n }表示这张牌。i 与yj 之间连接的边数等于数i 在纸牌yj 出现的次数，这样得到的图G 是一个2正则二分图。则G 中存在一个完美对集，设为M={1y 1i 2y 2i …….n y n i }则只要把纸牌y 1i 中的1朝上，y 2i 中的2朝下，y n i 中的n 朝上，这样摊开的纸牌就能使朝上的面中1，2，3……..n 都出现。
55、证明边长为2的正方形内任意5 证：构造抽屉如图，将5个点放在4个边长为1小正方形内，由抽屉原理，必
56、203,.254r r r a a r -≤≤?=??+≥?设数值函数求前向差
解：2
03,.254r r r a a r -≤≤?=??+≥?设数值函数求前向差
22002r a r ?=-=≤≤
4312523
16
a -?=+-= (1)1
252524r r r r a r -+---?=+-+=-≥
5611
{0,0,0,3
,2,2,...,2,...}16
r a ----∴?=---
57、设数值函数f = {1,2,22,23,...}，g = {1,3,32,33,...}，求3f-5g 的生成函数。
解：数值函数f = {1,2,22,23,...}和g = {1,3,32,33,...}的生成函数
223323()1222...1(2)(2)(2)...
1
.(|2|1)12F x x x x x x x x x =++++=++++=<- 223323()1333...1(3)(3)(3)...
1
.(|3|1)13G x x x x x x x x x
=++++=++++=<- 535
3()5().
1213f g F x G x x x
--=---所以3的生成函数为
58、设初始值h(0) = 0, h(1) = 1，h(2) = 2，求解递推关系
h(n) = h(n －1)+9h(n －2)－9h(n －3). (n = 3,4,...)
参考答案：特征方程为：x 3
- x 2
- 9x+9 = 0
解得特征根为1, 3,-3.因此
h(n) = A1n + B3n + C(-3)n
为一般解，由边界条件得
0331992A B C A B C A B C ++=??
+-=??++=?
解此线性方程组得唯一解
111
-,,4312
A B C ===-
因此所求的解为
111
()-3(3)4312
n n h n =+?-- 59、平面上给出25个点，其中没有任何3个点共线。这些点能确定多少条直线？多少个三角形？
解：由于没有3个点共线，所以每对点就确定一条直线，而直线的确定与两个点的次序无关，属组合问题，直线的总数为
2525!30022!23!??== ???
每三个点确定一个三角形，因此所确定的三角形总数为
2525!
230033!22!
??== ?
?? 60、一个面包店有6种不同类型的面包，这些面包以每打12个为单位向外出售。这个面包店能装配成多少打不同的面包（不考虑面包的顺序）？如果在每打中每种类型的面包至少有一个，那么又能装配成多少打不同的面包？
解：假设面包店每种面包都有很多（每种至少12个），由于每打中的面包与顺序无关，故为组合问题，能装配成不同的面包的打数即为6种类型的多重集（无穷重数）的12-组合数，其值为
12611717618812125+-??????
=== ? ? ???????
种。 如果在每打中每种类型的面包至少有一个，那么能装配成不同的面包的打数可以看成为6种类型的多重集（无穷重数）的6-组合数，其值为
6611111462665+-??????=== ? ? ???????
种。
61、试用生成函数求下式之和：123123n n n n n n ????????
?+?+?++? ? ? ? ????????? .
解：设 0()(1)n
i
n i n F x x x i =??==+ ???
∑
两边求导再乘 x 得:
10()(1)n
i n i n xF x i x n x x i -=??
'==+? ???
∑
令 x = 1 得:
1
12n
n i n i n i -=??= ?
??
∑. 62．网络专业的学生选修C++ 的有38人，选修VB 的有15人，选修DELPHI 的有20人，选修这三门课的同学总数为58人，且其中只有3人同时选修这三门课，试求同时选修两门课的同学有几人？
解：设A, B, C 分别为选修C++, VB, DELPHI 的同学的集合，则由
|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、设简单图G 中每个顶点的度至少是3，则G 含有长为偶数的回路。 证明：设t v v v P 10=是G 的一条最长路，则0v 的所有邻点全在P 内，设0v 的邻点为)1(,,,2121k i i i i i i v v v k <<<≤ ，其中3)(0≥=v d k G ，在G 中取三个回路
1030
1020
101222v v v v v C v v v v C v v v v C k k i i i i i +===
它们的长度分别为21122+-++i i i i k k 和，。这三个数至少有一个是偶数。即
321C C C ，，中至少有一个是长为偶数的回路。
证毕。
64、树T 的每一个非悬挂点都是T 的割点。
证明：设T 是p 阶树，u 是T 中一个非悬挂点，即2)(≥u d T 。不难看出u T -含1-p 个顶点，其边数为
)(1)()(u d p u d T q T T --=-=1)()()(--<--u T p u d u T p T ，
因而u T -不是树。显然u T -不含回路，所以u T -非连通，即u 是T 的割点。 证毕。 65、若连通图G 恰好有)0(2>k k 个奇点，则在G 中存在k 条边不交的迹
k Q Q Q ,,,21 ，使得
)()()()(21k Q E Q E Q E G E =。
证明：设G 的k 2个奇点为k k y y y x x x ,,,,,,,2121 ，在G 中增加k 条分别连接
i i y x 与的新边k i e i ,,2,1, =，所得图记为G '，则G '是一个Euler 图。记G '的一条Euler 环游为C '，然后在C '中删除新加的k 条边k e e e ,,,21 ，就将C '分成k 段，这k 段即为G 的k 条边不交的迹。
证毕。 66、若p 阶图G 没有孤立顶点，则p G G =+)()(00βα
证明：设I 是G 的最大独立集，K 是G 的最小点覆盖，则K G V -)(是G 的独立集，I G V -)(是G 的点覆盖，所以 K G V G p -=-)()(0αI ≤=)(0G β )()()(00G K I G V G p αβ=≥-=- 因此
p G G =+)()(00βα
67．在一次聚会上有10位男士和10位女士。这10位女士能够有多少种方法选择男舞伴开始第一次跳舞？如果每个人必须换舞伴，那么第二次跳舞又有多少种选择方法？
解：对于第一次跳舞，可以对10位男士和10位女士并排排列，如果10位男士不改变次序，10位女士一个全排列就是一种配对方式，共存在10! = 3628800可能的选择；
对于第二次跳舞，每位女士必须选择一位不是第一次与她跳舞的男舞伴，因此可能的选择方法数为移位排列数 1111111111
(10)10!(1)1!2!3!4!5!6!7!8!9!10!
D =-
+-+-+-+-+
= 1334961.
即第二次跳舞有1334961种选择方法。
68．求解满足初始值h 0 = 1, h 1 = 2, h 2 = 0的递推关系
123
223n n n n h h h h n ---=+-≥.
解：这个递推关系的特征方程
32220x x x --+=
的3个根为 1, -1, 2，递推关系的解为
1231231(1)2(1)2n n n n n n h c c c c c c =+-+=+-+
利用初始条件得c 1, c 2, c 3 满足的方程组为
12312312
31
2240
c c c c c c c c c ++=??
-+=??++=? 解得12321
2,,33
c c c ==-=-，因此递推关系的解为
21
1(1)233
n n n h =---?.
69、证明题 任取11个整数，求证其中至少有两个数，它们的差是10的倍数。 证明：设这11个整数为a 1, a 2, …, a 11,它们被10除之后其余数为0 ~ 9之间的整数，将0 ~ 9当作抽屉，由抽屉原理可知，在这11个整数中必有两个数，不妨设为a i , a j , 它们二者的余数相等，从而a i - a j =10 n (n 为一个整数)，即a i 与a j 的差是10的倍数。
作业题：
1. 用0～9这十个数码可以组成多少个没有重复数码的四位数？
2. 一教室有两排座位，每排8个，今有14名学生，5人总坐在前排，4人总在
后排，问学生入座有几种方式？
3.如果没有相邻的两个数在同一个集合里，由 {1, 2, ... , 20}中的数可形成三个数的集合有多少种？
4设S ={ a , b , c , d , e, f }，求S 的所有4－组合(按字典序排列)。 5. 在一次聚会中，6个人寄存帽子，如果散会时没有任何一个人得到他自己的帽子，问有几种交还方式？
6.试求多重集B = {3?a , 4?b , 5?c } 的10—重复组合数。
7.证明：在任意选取的12个正整数中，至少存在两个数，它们的差能被11整除。 8. 解非齐次递推关系
12018154,2
0,1
n n n a a a n a a ---+=≥??
==?
第四届全国组合数学与图论会议纪要 为促进我国组合数学与图论学科的进一步发展，加强国内同行的学术交流与合作，第四届全国组合数学与图论大会于2010年8月21日至25日在徐州师范大学举行。会议由中国组合数学与图论学会主办，徐州师范大学承办，并得到了徐州师范大学和国家自然科学基金委天元基金的大力资助。 会议期间，来自国内外约160所大学和研究院所的约400位专家、学者和研究生共聚一堂, 积极讨论，相互交流。福州大学范更华教授、同济大学邵嘉裕教授、中科院胡晓东教授、香港大学臧文安教授、南开大学高维东教授和北京交通大学常彦勋教授等作了6个大会报告（60分钟）。另外，分四个分组进行了13个特邀报告（30分钟）以及近120个小组报告（15分钟）。报告内容涉及组合数学与图论的各个领域。其中包括结构图论、随机图论、代数图论、化学图论、图的染色、组合设计、组合优化、组合计数、组合矩阵、复杂网络、网络优化、代数组合论与应用图论等众多领域。 开幕式由徐州师范大学数学科学学院院长刘笑颖教授主持，徐州师范大学党委书记徐放鸣教授首先致开幕词，接着，中国组合数学与图论学会的理事长陈永川发表了热情洋溢的讲话。
本次会议还举行了中国组合数学与图论学会理事会的换届选举。首先由上届正副理事长陈永川教授、李学良教授和王军教授（其中宝升教授因事缺席）提出新一届理事会的候选人名单。然后经理事会充分讨论，并进行民主投票选举，产生了51位新任理事，并随后由新一届理事会选举产生了新一届常务理事会与正副理事长。 与会代表衷心感谢本次会议的东道主徐州师范大学的校、院各级领导对本次会议的大力支持，衷心感谢会务组的全体同志为本次会议的顺利召开而付出的辛勤劳动。 经新一届常务理事会讨论，决定下一届全国组合数学与图论大会于2012年在洛阳师范学院举行。
组合数学在计算机中的应用 组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。随着计算机科学的发展,组合数学也在迅猛发展,而组合数学在理论方面的推进也促进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础,组合数学作为大多数计算机软件设计的理论基础,它的重要性也就不言而喻。 就从目前我们在学习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．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?
组合数学论文 现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好像是有思维的。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。 广义的组合数学就是离散数学，离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。 狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。 组合数学中有几个著名的问题： 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。 船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？ 这是线性规划的问题。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。 货郎问题：一个货郎要去若干城镇卖货，然后会到出发地，给定各个城镇之间的旅行时间，应怎么样计划他的路线，使他可以去每个城镇而且所用的时间最短。这个问题至今都没有有效的算法。 这几个问题将组合数学研究的问题具体表现出来，同时也可以看出他在我们生活中有着很重要的地位。 组合数学中主要可以分成以下几个部分：排列组合与容斥原理、二项式定理、递推关系与生成函数、polya定理。下面我将以这四个部分分别介绍组合数学的各方面问题。 1、排列组合与容斥原理： 排列组合里面的4个重要的基本原理：加法原理、乘法原理、减法原理、除法原理 前面两个最为基本，后面两个是根据前两个派生出来的。乘法原理有的时候的应用很巧妙，可以作为一种打开思路的办法。
组合数学部分 第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.doczj.com/doc/4f5062617.html,
1
组
合
数
学
Combinatorics
组合数学:有人认为广义的组合数学就是离散数学，也有人认 为离散数学是狭义的组合数学和图论、代数结构、数理逻辑 等的总称。但这只是不同学者在叫法上的区别。总之，组合 数学是一门研究离散对象的科学。
https://www.doczj.com/doc/4f5062617.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/4f5062617.html,/wiki/Combinatorics 2
组合数学与离散数学
? 狭义的组合数学主要研究满足一定条件的组态（ 也称组合模型）的存在、计数以及构造等方面的 问题。
– 组合数学的主要内容有组合计数、组合设计、组合矩 阵、组合优化等。
? 离散数学(Discrete mathematics)是数学的几个分 支的总称，以研究离散量的结构和相互间的关系 为主要目标，其研究对象一般地是有限个或可数 无穷个元素；因此它充分描述了计算机科学离散 性的特点。
– 离散数学通常研究的领域包括：数理逻辑、集合论、 关系论、函数论、组合学、代数系统与图论。 。
3
组合数学学习心得 在进入研究生学习的第一个学期就开设了组合数学这门课程，我感到很庆幸和开心，因为我在学完这门课程之后学到了很多东西，不仅仅是课本上的，还有许多在课本上是学不到了！ 组合数学，对大多数学生来说是一门十分困难的课程，由于自己本科学的是数学，所以学起来还好，也比较喜欢这门课程。组合数学可以一般描述为：组合数学是研究离散结构的存在，计数，分析，和优化等问题的一门学科。经验证发现的组合数学最有力的工具之一为数学归纳法。归纳是一个强有力的过程，在组合数学中尤其是如此。用数学归纳法证明一个结果常常比证明一个弱结果更容易。许多组合问题的解决常常需要某些特别的例证，而且有时需要结合使用一般的理论。我们必须学会建立数学模型，研究模型，抓住问题的要害，灵活的应用智慧来解决问题。“图论”是组合数学课程中比较重要的一部分。在刚接触到“图”这一章的时候我是抱着好奇之心去学习的，因为这章都是关于“图” ，想了解一下和几何图形的差别，所以觉得善长几何的我应该能够把它学好。但是不可否认，随着知识的深入，这一章一定会比前面的更难理解，更难学。因此上课的时候听得格外认真，课后还找了一些相关书籍阅览。在看过这些书籍以后，我才真正了解到它并不是枯燥乏味的，它的用途非常广泛，并且应用于我们整个日常生活中。比如：怎样布线才能使每一部电话互相连通，并且花费最小？从首府到每州州府的最短路线是什么？n 项任务怎样才能最有效地由 n 个人完成？管道网络中从源点到集汇点的单位时间最大流是多少？一个计算机芯片需要多少层才能使得同一层的路线互不相交？怎样安排一个体育联盟季度赛的日程表使其在最少的周数内完成？我们能用4种颜色来为每张地图的各个区域着色并使得相邻的区域具有不同的颜色吗？这些问题以及其他一些实际问题都涉及“图论” 。这里所说的图并不是几何学中的图形，而是客观世界中某些具体事物间联系的一个数学抽象，用顶点代表事物，用边表示各式物间的二元关系，如果所讨论的事物之间有某种二元关系，我们就把相应的顶点练成一条边。这种由顶点及连接这些顶点的边所组成的图就是图论中所研究的图。由于它关系着客观世界的事物，所以对于解决实际问题是相当有效的。总之，图论是数学科学的一个分支，而四色问题是典型的图论课题。通过对图论的初步理解和认识，我深深地认识到，图论的概念虽然有其直观、通俗的方面，但是这许多日常生活用语被引入图论后就都有了其严格、确切的含义。我们既要学会通过术语的通俗含义更快、更好地理解图论概念，又要注意保持术语起码的严格。 学习数学重要的是理解，而不是像其它科目一样死背下来，数学有一个特点,那就是”举一反三”。做会了一道题目，就可以总结这道题目所包含的方法和原理,再用总结的原理去解决这类题，收效就会更好.学习数学还有一点很重要，那就是从基本的下手，稳稳当当的去练，不求全部题都会做，只求做过的题不会忘，会用就行了。在做题的过程中，学习是一生的事情，不要过于着急，一步一个脚印的来,就一定会取得一想不到的效果。数学的学习是一个积累和运用的过程，因此，学好数学的一个必要前提便是要注重平时的积累和运用。而在日常时对于数学的学习还是有许多方法的。数学学习做题是极为必要的，因此做题之后的总结工作也是极为重要的，否则只能是杂而不精，无法将知识融会贯通，合理运用。 组合数学是一门既古老又年轻的数学分支。组合数学不仅在基础数学研究中具有极其重要的地位，在其他的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。如果说微积分和近代数学
第一部分：组合数学 第一章计数的基本原则 一．组合数学的历史和内容 1.历史：组合数学最早起源于中世纪的印度，在漫长的历史中，一 直发展缓慢。随着上一世纪计算机的出现，组合数学开始快速地发展。近几年，由于计算机安全领域受到重视以及组合数学在计算机安全领域的应用，组合数学受到越来越多的重视。 2.内容：组合数学主要包括以下几个内容： (1)组合分析（也称为组合计数理论） (2)组合优化（包括线性规划，整数规划等） (3)组合设计（包括区组设计等） (4)组合算法（例如：搜索算法，DFS算法与分支定界法，动态规 划等） *图论本是组合数学这个家族的一个主要成员，但它已成长壮大，独立成一门学科。 3. 本课程介绍的主要内容：组合计数理论 二．加法原则与乘法原则 1. 加法原则： 设事件A有m种产生方式，事件B有n种产生方式，则“事件A 或事件B”有m+n种产生方式。 例子：大于0而小于10的偶数有4个，即：{2，4，6，8}，大于0而小于10的奇数有5个，即：{1，3，5，7，9}。则大于0而小于10
的整数有：4+5=9个，即：{1，2，3，4，5，6，7，8，9}。 *如果A1,A2,?,A n是互不相交的有穷集，那么 |A1∪A2∪?∪A n|=|A1|+|A2|+?+|A n| 2.乘法原则： 若事件A有m种产生方式，事件B有n种产生方式，则“事件A 与事件B”有mn种产生方式。 例1：设一个符号由两个字符组成，第一个字符有a,b,c,d,e五种方式，第二个字符有1,2,3三种方式。则根据乘法原则，该符号具有5×3= 15种方式，即 a1,b1,c1,d1,e1;a2,b2,c2,d2,e2;a3,b3,c3,d3,e3. 例2：从A到B有3条不同的道路，从B到C有2条不同的道路，从A经B到C共有n=3×2=6条不同的道路。 例3：求比10000小的正整数中含有数字1的数的个数。 解：先求所有4位数中不含有数字1的个数，即求由{0，2，3，4，5，6，7，8，9} 9个数字组成的4位数的个数。每一位都有9种出现方式，根据乘法原则，由9个数字组成的4位数个数为：9×9×9×9= 6561，其中包含0000不是正整数。故比10000小不含数字1的4位正整数的个数=6561?1=6560. 所以小于10000含有数字1的4位数个数=9999?6560=3439.
目录 摘要 (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：组合数学与计算机软件 随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。
组合数学及其图论 1、一个图G 是指一个有序三元组（V （G ），E （G ），G ?），其中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)/2 6、如果一条途径的_________与___________相同，就称这条途径为闭途径。 起点 终点 7、如果对图G=（V ，E ）的任何两个顶点u 与v ，G 中存在一条（u-v ）路，则称G 是___________否则称为是______________ 连通图、 非连通图 8、设G 是P 阶连通图，则__________________. q(G)≥p-1 9、若二分图 有Hamilton 回路，则 与 满足 。 10、若G 是2-边连通图，则G 有强连通的________________. 定向图 11、边数最少的连通图是 。
树 12、没有回路的连通图称为_______________. 树 13、的图是图或图。 平凡图，不连通图 14、树T的每一个非悬挂点都是T的 __________. 割点 15、二分图中若与满足，则必有完美对集。 16、给定一个图G，如果图G的一个生成子图T是一棵树，则称T是G的一个_______________. 生成树 17、设G是无环图，e是G的一条边，则 τ(G)=___________________________. τ （G－e）+τ (G·e) 18、是阶简单图，则，等号成立当且仅当是图。 ，完全图 2、 19、___________________________的生成树称为最优生成树。 连通赋权图中具有最小权 20、的一个对集是最大对集的充要条件是。 中无可扩路 21、一个有向图D，如果略去每条弧的方向时所得无向图是一棵树，就称D为_____________________. 有向树 22、经过G的每条边的迹称为G的Euler迹，如果这条迹是闭的，则称这条闭迹为G的 ________________. Euler环游 23、是简单图且，则。
浅谈组合数学与计算机科学 摘要：组合数学，又称为离散数学，是一门研究离散对象的科学。组合数学是计算机出现以后迅速发展起来的一门数学分支，随着计算机科学的日益发展，组合数学的重要性也日渐凸显。 关键词：组合数学计算机欧拉回路 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”两个简单数字表示的信息，或者是用这种数字进行了编码的信息。所以离散对象的处理就成了计算机科学的核心，而组合数学是一门研究离散对象的科学。现代数学的研究内容主要包括两个方面：一方面类是研究连续对象的，如分析、代数等，另一方面就是研究离散对象的组合数学。
《图论与组合数学》教学大纲 一、课程名称：图论与组合数学 二、课程代码：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：通过理论与实践相结合的系统学习，能够识别复杂工程问题中所涉及的数学、自然科学及计算机科学与技术专业的相关理论知识。 十三、课程的目标 图论和组合数学是现代数学的重要分支，是研究离散结构的存在、计数、分析和优化等问题的一门科学，是计算机科学与技术专业的基础理论课程。通过本课程的学习，使学生掌握图论与组合数学的基本原理和方法，了解和掌握无向图、有向图、连通图、排列与组合、容斥原理、递推关系和生成函数等基本知识，灵活运用所学知识对一些简单问题进行建模并编程求解。
组合数学概述 组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。 组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。 在1997年11月的南开大学组合数学研究中心成立大会上，吴文俊院士指出， 每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求下产生的。最近，吴文俊院士又指出，信息技术很可能会给数学本身带来一场根本性的变革，而组合数学则将显示出它的重要作用。杨乐院士也指出组合数学无论在应用上和理论上都具有越来越重要的位置，它今后的发展是很有生命力，很有前途的，中国应该倡导这个方面的研究工作。万哲先院士甚至举例说明了华罗庚，许宝禄，吴文俊等中国老一辈的数学家不仅重视组合数学，同时还对组合数学中的一些基本问题作了重大贡献。迫于中国组合数学发展自身的需要，以及中国信息产业发展的需要，在中国发展组合数学已经迫在眉睫，刻不容缓。 2. 组合数学与计算机软件 随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。我在美国听到过一种说法，将来一个国家的经济实力可以直接从软件产业反映出来。我国在软件上的落后，要说出根本的原因可能并不是很简单的事，除了技术和科学上
数学科学学院 课程名称图论导引 题目图论在交叉学科中的应用姓名闫二路 学号 A01014134 专业数学与应用数学 授课老师汪毅
图论在交叉学科中的应用 [摘要]利用图论知识可以解决一些交叉学科中的实际问题。对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支，它是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如信息论，矩阵论都有着重要的联系。 [关键字] 树、即时码、hamilton圈、Hamilton路 1．即时码的树图构造法 即时码定义：在唯一可译变长码中，有一类码，它在译码时无须参考后续的码符号就能立即做出判断，译成对应的信源符号，则这类码称为即时码。 树的定义：一个图G若是无圈的且连通，则称图G是树。 为了联系树与即时码的关系我们引入关于判断树的一个定理； 定理1:图G是树当且仅当G的任何两个顶点都被唯一的路连接。 从上述定理1我们可以判断利用树构造的码为即时码，如下图构造的即时码：
从上面我们可以得到码字集合C1={000,001,010,011,100,101,110,111}，C2={00,01,02,10,11,12,20,210，211,212,220,221,222} 我们根据即时码的定义可得利用树构造的码都是即时码，我们也知道即时码一定是唯一可译码，因此树图能给我们带来比较方便的方法来构造即时码。 问题求解反思：我们从即时码的树图构造法中，我们得到:使用图论中的树我们能很容易得到信息论中即时码的一种构造方法，这里利用了交叉学科相互结合的思想，利用图我们能更好的理解一些实际问题，有利于我们的理解，从这个方面我们能得出图论在其他学科有着很重要的联系，有利于实际问题更好的解决。 2.Hamilton图的应用 Hamilton图的定义：一个含图G的每个顶点的圈称为是G的Hamilton 圈，这个含有Hamilton圈的图称为是一个Hamilton图。 Hamilton圈在现实中有着广泛的应用，当我们给出一个实际问题时，我们应该怎样Hamilton图来解决实际问题，这需要我们从联系实际
图论与组合数学
一、浅谈图论中邻接矩阵的应用 通过一个学期以来对图论与组合数学这门课程的学习和理解，从图论的理论到应用，更加加强了对这门学科的认识。图论与组合数学在我们日常生活中应用的非常广泛，并应用于很多领域，是现在的热门讨论与研究的前沿学科。通过这个学期老师的授课及讲解，我从中学到了很多，因此在学期末对所学的知识做出总结。主要介绍一下图论中邻接矩阵的应用。 使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题，是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。 首先介绍图论中邻接矩阵的一个重要定理: G 是一个图,V(G)为 G 的顶点集, E(G)为 G 的边集。设G 中有 n 个顶点，v 1,v 2,…,v n ;A=(a ij )n ×n 为 G 的邻接距阵, 其中 n j i G E v v G E v v a j i j i ij ,...,2,1,) (0)(1=??????∈= 定理 1:设 A (G)为图 G 的邻接距阵,则 G 中从顶点 vi 到顶点 vj,长度为 k 的道路的A k 条数为中的 i 行 j 列元素。 证:对 k 用数学归纳法 k =1时,显然结论成立;假设 k 时,定理A l .A= A l+1 成立,考虑 k +1的情形。 记 A l 的 i 行 j 列元素为l ≥2,因为所以 nj l in j l i j l i l ij a a a a a a a +++=+...2211) 1( (1) 而从v i ,v j 到长 k +1的道路无非是从v i 经 k 步到某顶点v l (1≤l ≤n),再从v l 走一步到v j ; 由归纳假设从v l 到v j 长为 k 的道路共计 而从v l 到v j 长为 1的道路为a ij 条,所以长为k+1的v l 经过k 部到v i 再一步到v j 的道路共有 ∑-+= n l lj k il l ij a a a 1 )()1(条。 锁具装箱问题 某厂生产一种弹子锁具,每个锁具的钥匙有 5个槽,每个槽的高度从 {1, 2, 3, 4, 5, 6}6个数 (单位略 )中任取一数由于工艺及其他原因,制造锁具时对 5个槽的高度还有两个限制:至少有 3个不同的数,相邻两槽的高度之差不能为 5,满足以上条件制造出来的所有互不相同的锁具称为一批。销售部门在一批锁具中随意地取每 60个装一箱出售。问每一批具有多少个,装多少箱。 分析：锁具装箱这个问题是一个排列组合的数学问题,但在这里我们用图论中的邻接矩阵方法来解决这个问题。每把锁都有 5个槽,每个槽有 6个高度,至少有三个不同高度的槽。且相邻槽高差不为 。我们先求出无相邻高5差为 5的锁具数量,再减去仅有一个、两个槽高的锁具数目。 先计算由 1, 2, 3, 4, 5, 6构成无 1, 6相邻的情况的数目。为此,构造一个 6节点的图:将 1, 2, 3, 4, 5, 6这 6个数作为 6个节点,当两个数字可以相邻时,这两个节点之间加一条边,每个节点有自己到自己的一条边。我们得到了锁具