第四届全国组合数学与图论会议纪要

抽屉原理在初等数学中的运用摘要：抽屉原理也称为鸽巢原理，它是组合数学中的一个最基本的原理.也是数学中的一个重要原理，抽屉原理的简单形式可以描述为：“如果把1+n 个球或者更多的球放进n 个抽屉，必有一个抽屉至少有两个球.”它的正确性十分明显，很容易被并不具备多少数学知识的人所接受，如果将其灵活地运用，则可得到一些意想不到的效果. 运用抽屉原理可以论证许多关于“存在”、“总有”、“至少有”的存在性问题。

学习抽屉原理可以用来解决数学中的许多问题，也可以解决生活中的一些现象。

如招生录取、就业安排、资源分配、职称评定等等，都不难看到抽屉原理的作用。

在解决数学问题时有非常重要的作用. 抽屉原理主要用于证明某些存在性问题及必然性题目，如几何问题、涂色问题等. 各种形式的抽屉原理在高等数学和初等数学中经常被采用，使用该原理的关键在于如何巧妙地构造抽屉，即如何找出合乎问题条件的分类原则，抽屉构造得好，可得出非常巧妙的结论.本文着重从抽屉的构造方法阐述抽屉原理在高等数学和初等数学（竞赛题）中的应用,同时指出了它在应用领域中的不足之处.关键词：抽屉原理；初等数学；应用一、 抽屉原理（鸽巢原理）什么是抽屉原理？先举个简单的例子说明，就是将3个球放入2个篮子里，无论怎么放，必有一个篮子中至少要放入2个球，这就是抽屉原理.或者假定有五个鸽子笼，养鸽人养了6只鸽子，当鸽子飞回巢中，那么一定至少有一个鸽笼里有两只鸽子，这就是著名的鸽巢原理.除了这种比较普遍的形式外，抽屉原理还经许多学者推广出其他的形式.比如陈景林、阎满富编著的中国铁道出版社出版的《组合数学与图论》一书中对抽屉原理给出了比较具体的定义，概括起来主要有下面几种形式:原理1 把多于n 个的元素按任一确定的方式分成n 个集合，则一定有一个集合中含有两个或两个以上的元素.原理2 把m 个元素任意放到n )(n m >个集合里，则至少有一个集合里至少有k 个元素，其中原理3 把无穷个元素按任一确定的方式分成有穷个集合，则至少有一个集合中仍含无穷个元素.卢开澄在《组合数学》（第三版）中将抽屉原理（书中称为鸽巢原理）又进行了推广[2].鸽巢原理：设k 和n 都是任意正整数，若至少有kn+1只鸽子分配在n 个鸽巢中，则至少存在一个鸽巢中有至少k+1只鸽子.二、抽屉的构造途径在利用抽屉原理解题时，首先要明确哪些是“球”，哪些是“抽屉”，而这两者通常不会现成存在于题目中，尤其是“抽屉”，往往需要我们用一些巧妙的方法去构造。

科大组合与图论专业三十五年------为科大校庆五十周年而写李乔、李炯生、徐俊明中国科学技术大学组合与图论专业从李乔发表的第一篇论文算起，经历了整整35年。

在这35年里，逐渐形成了自己的研究特色：组合矩阵论和组合网络理论。

发表学术论文300余篇，专著和教材16部。

获得1993年国家教委科技进步一等奖（合作）、2003年安徽省自然科学二等奖和2008年中国科学院首届教学成果二等奖。

培养硕士研究生57名，博士研究生26名，进站博士后5名，接收国内高校青年进修和访问学者9名。

回忆这段历史，科大组合学与图论专业的创立和发展大体上分为三个阶段。

一、创立阶段（1973-1985）中国科学技术大学数学系的组合学与图论研究始于上世纪七十年代初。

北京大学段学复教授向曾肯成建议：国内可由科大牵头研究组合与图论。

李乔和冯克勤凭借代数方面的深厚功底开始涉及组合与图论，在国内率先开展代数图论研究。

1973年，李乔在《中国科学技术大学学报》上发表的“关于偶图的极大对口”是本专业第一篇学术论文。

随后，李乔和冯克勤合作完成了 “关于树和其他图的联系矩阵”、“图的谱性质的若干结果”和“论图的最大特征根” 3篇论文，分别发表在《中国科学技术大学学报》（1976，1979）和《应用数学学报》（1979）上。

这些论文是国内代数图论研究最早的学术论文，现成为此研究领域的经典论文之一。

在此期间，李乔和冯克勤还从数学角度介入当时国内兴起的“量子化学的图论研究”，成为国内最早开展此项研究的学者。

1977年8月在上海举行的全国第一次量子化学学术会议上，李乔介绍了他与冯克勤在这方面的研究成果。

组合学是经典的数学分支，被人熟知。

图论是组合学的一个活跃分支，但当时数学界对它还不大了解。

1977年底，李乔对数学系师生做了题为《图论》的介绍性报告。

他以图论语言简洁证明“在任意六人中必存在三人, 要么都相识,要么都不相识”为开场，来介绍图论，生动有趣。

正是这个报告引起了不少人对图论的兴趣。

习题四4。

1。

若群G的元素a均可表示为某一元素x的幂,即a= x m，则称这个群为循环群.若群的元素交换律成立，即a , b G满足a b = b a则称这个群为阿贝尔(Abel）群，试证明所有的循环群都是阿贝尔群。

［证］.设循环群（G，)的生成元是x0ÎG。

于是,对任何元素a ，b G，m,nÎN，使得a= x0m , b= x0n，从而a b = x0m x0n= x0m +n (指数律)= x0n +m (数的加法交换律)= x0n x0m(指数律)= b a故运算满足交换律；即(G, )是交换群.4.2。

若x是群G的一个元素,存在一个最小的正整数m，使x m=e，则称m为x的阶，试证：C={e，x，x2, ，x m—1}是G的一个子群。

［证].(1)非空性C ：因为eÎG；（2）包含性C G:因为xÎG，根据群G的封闭性，可知x2, ，x m—1,(x m=)eÎG,故C G；（3)封闭性 a , b C a b C: a , b C，k，lÎN (0k〈m，0l〈m),使a = x k，b = x l，从而a b = x k x l = x(k+l）mod m C(因为0 （k+l) mod m〈m) ；(4)有逆元 a C a —1C： a C，kÎN (0k<m)，使a = x k, 从而a -1= x m—k C（因为0 m-k < m）。

综合（1) (2）(3) (4），可知(C, )是(G, )的一个子群.4.3。

若G是阶为n的有限群，则G的所有元素的阶都不超过n。

[证］。

对任一元素xÎG，设其阶为m，并令C={e,x，x2，，x m-1},则由习题4.2.可知（C, )是（G, ）的一个子群，故具有包含性C G。

因此有m = ｜C｜£｜G｜= n所以群G的所有元素的阶都不超过n。

组合数学及其图论1、一个图G 是指一个有序三元组（V （G ），E （G ），G ϕ），其中G ϕ是：________________.关联函数2、是有40个点的简单图且 中任两个点之间有且只有1条路，则。

393、只有一个顶点所构成的图称为：________________平凡图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(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、___________________________的生成树称为最优生成树。

福建师范大学研究生考试、考查成绩登记表学院数学与计算机科学学院专业学科教学（数学）年级2015级研究生研究生姓名何媛媛学号20151226 导师潘彪课程名称现代数学概览课程类别（学位课、必修课、选修课）考试时间课内学时数总学时数学分数成绩评定结果任课教师主考教师（签名）考试考查补考张胜元对考生学习情况的简要评语：注：请主考教师将此表填写好，附在该学生试卷的首页，连同试卷交研究生秘书处。

考试成绩按百分法，考查成绩按五级制记分法，补考按实际成绩记载、成绩及格评定结果记“通过”、不及格记“不通过”、学位课程75分以上评为合格2015-2016学年第一学期全日制专业学位研究生期末课程论文课程名称：现代数学概览论文题目：图论问题在数学竞赛中的应用任课教师：张胜元老师学院：数学与计算机科学学院专业：学科教学（数学）学号：20151226姓名：何媛媛目录摘要 (1)前言 (2)1、竞赛数学中与图论有关的定理及其性质 (3)1.1简单图 (3)1.2完全图 (3)1.3欧拉图与哈密顿图 (3)1.4竞赛图 (3)2、竞赛数学中与图论有关的常见问题 (4)2.1图的连通性问题 (4)2.2图的遍历问题 (4)2.2.1欧拉问题 (4)2.2.2哈密顿问题 (4)3、解决数学竞赛图论问题的常用方法 (5)3.1存在性问题 (5)3.1.1抽屉原理 (5)3.1.2反证法 (6)3.1.3极端性原理 (6)3.1.4计数方法 (6)3.2组合最值问题 (7)3.2.1构造法 (7)3.2.2调整法 (7)小结 (8)图论问题在数学竞赛中的应用摘要图论问题最早起源于世纪初，随肴计算机等现代工丹的产生，图论又与计算机网络、结构化学等相联系，得到广泛的应用而作为竞赛数学中组合部分的一个分支，在解决问题方面，如果从图论的观点出发，往往给我们提供一个处理问题的角度本文运用文献分析法，结合国内外有关图论的赛题，探究了“图论与竞赛数学组合问题”的联系，搭建起图论研究与竞赛数学研究的桥梁关键词：图论问题竞赛数学解题方法前言经过多年的发展，竞赛数学所涉及的内容，大致可归结为六个方面、四大支柱、三大热点。

图论与组合数学期末复习试题含答案组合数学部分第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，再将给出序列按从⼩到⼤顺序依次排列并插⼊递增序列得到：112223344567。

国际组合数学学术会议暨中国第四届组合数学学术会议召开蜀山
【期刊名称】《自然杂志》
【年(卷),期】1990(000)010
【摘要】国际组合数学学术会议暨中国第四届组合数学学术会议于1990年8月20～24日在合肥市举行。

这次会议是由中国组合数学研究会和中国科学院合肥分院联合主办的。

出席这次会议
【总页数】1页(P678-678)
【作者】蜀山
【作者单位】
【正文语种】中文
【中图分类】N49
【相关文献】
1.中德石家庄组合数学国际学术会议取得圆满成功 [J], 无
2.第四届中国国际暨第七次全国口腔颌面外科学术会议在蓉召开 [J], 郑家伟
3.第六届中国血管病和动脉功能学术会议暨第四届国际血管健康学会亚太地区会议分别在广州、贵阳及北京召开 [J],
4.2013年第六届国际艾滋病影像学术会议暨第四届感染与传染病影像学新进展学术会议成功召开 [J],
5.2005年“第四届中国国际暨第七次全国口腔颌面外科学术会议”“第一届第四次全国口腔颌面肿瘤学术会议”“第五次全国唇腭裂学术会议”“第四次全国口腔颌面创伤学术会议”第二轮通知 [J], 无
因版权原因，仅展示原文概要，查看原文内容请购买。

数学学科中的数论与图论数论和图论是现代数学的两个重要分支，两者都有着广泛的应用和深刻的理论基础，因此在数学领域中扮演着不可或缺的角色。

本文将分别从数论和图论的角度入手，探讨它们在数学学科中的特点、应用和未来发展趋势。

一、数论数论是研究整数和其性质的数学分支，早期起源于人类对数学本质的探索和实践中对数字的认识和应用。

数论有着严密的逻辑结构和深远的历史文化底蕴，许多著名数学家曾在这个领域做出了卓越的贡献，如费马大定理、黎曼猜想、哥德尔不完全性定理等均为著名数论问题。

此外，数论在密码学、代数几何、代数数论、组合数学等领域中也有着广泛的应用。

其中，数论在密码学中的应用尤为重要。

密码学是研究通信安全、数据保护和信息隐藏的学科，旨在保护敏感信息的隐私和安全。

数论是密码学中最常用的数学工具之一。

公钥密码学中，大整数因子分解、离散对数问题等都是数论中的经典问题。

此外，一系列密码学协议和算法中也涉及到了数论的理论和方法，如RSA算法、椭圆曲线密码算法等。

这些算法都是基于数论的一些重要定理，如欧拉定理、勒让德符号等。

因此，数论是现代密码学中不可或缺的一环。

除此之外，数论还在代数几何、代数数论、组合数学等领域中发挥着重要的作用。

在代数几何中，数论常常与代数算法、模形式、椭圆曲线等有关。

在代数数论中，数论与代数数域、代数群、模空间等有着密不可分的联系。

在组合数学中，数论与离散对称性理论以及疏散多项式等问题有着千丝万缕的联系。

这些都给数论研究带来了许多新的思路和发展方向。

未来，随着科技的进步和应用场景的拓展，数论将会在更多领域中发挥着日益重要的作用。

同时，数学家们也将不断拓展数论的研究深度和广度，探寻其中的新的奥秘和应用价值。

二、图论图论是研究图和图中相关问题的数学分支，其中图是由结点和边组成的网络结构。

图论具有广泛的应用领域，包括计算机网络、运筹学、物理学、生物学等等。

图论中研究的具体问题包括最短路径、最小生成树、最大流等等。

树形结构公式全文共四篇示例，供读者参考第一篇示例：树形结构公式是一种数学公式表示方法，经常用于描述层次关系或者层次结构的数据。

在计算机科学中，树形结构公式被广泛应用于数据结构的表示和处理，例如XML、HTML等常用的数据格式都是基于树形结构的。

树形结构公式由树和节点两个基本元素构成。

树是一个由节点构成的集合，节点之间通过边相连。

树的每个节点都有一个父节点，除了树的根节点外，每个节点都有一个母节点。

树的根节点是整个树的起点，没有母节点的节点称为叶子节点，其他节点称为内部节点。

树形结构公式的表示方法通常采用括号表示法。

一个树形结构公式由节点的标签和节点的子树组成。

节点的标签用来表示节点所代表的对象或者数据，节点的子树用来表示节点的子节点。

一个节点的子树也可以是一个空的子树，表示该节点没有子节点。

下面是一个用树形结构公式表示的树：（A（B （C）（D））（E））在这个树形结构公式中，根节点的标签为A，有两个子节点，分别为B和E。

B节点有两个子节点C和D，E节点没有子节点。

这个树形结构公式表示了一个二叉树，根节点为A，左子树为B，右子树为E，B节点的左子树为C，右子树为D。

树形结构公式在计算机科学中有着广泛的应用。

树形结构数据可以用来表示组织结构、文件系统、文档结构等层次关系的数据。

在算法设计中，树形结构通常被用来表示递归结构，例如二叉树搜索、最小生成树等算法。

在数据库系统中，树形结构被用来表示索引结构，加快数据检索的速度。

树形结构公式是一种强大的表示方法，可以描述各种层次关系的数据，并且在计算机科学领域有着广泛的应用。

熟练掌握树形结构公式的表示方法和应用场景，对于提高算法设计和数据处理的能力有着重要的意义。

希望本文对您了解树形结构公式有所帮助。

第二篇示例：树形结构公式是一种用于描述数据组织和关系的重要数学工具。

在计算机科学、信息科学以及其它一些领域中，树形结构公式被广泛应用于数据的存储和处理。

与线性表不同，树形结构公式可以更加灵活地表达多层次、分支状、层级关系的数据，常常用于表示树状图、家族关系、文件系统、数据库索引等复杂结构。