《《浅谈组合数学》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《浅谈组合数学》PPT课件.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、浅谈组合数学浅谈组合数学组合数学概述组合数学概述n n现代数学根据所研究的对象可分为两类：现代数学根据所研究的对象可分为两类：连续数学：以微积分为基础，传统主流；连续数学：以微积分为基础，传统主流；离散数学：伴随计算机科学，方兴未艾。离散数学：伴随计算机科学，方兴未艾。n n计算机出现以后，由于离散对象的处理是计算机科学计算机出现以后，由于离散对象的处理是计算机科学的核心，研究离散对象的组合数学得到迅猛发展的核心，研究离散对象的组合数学得到迅猛发展。n n微积分和近代数学的发展为近代的工业革命奠定了基微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革础
2、。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。计算机好象是有思维的。组合数学概述组合数学概述n n组合数学（Combinatorial Mathematics)也称组合学(Combinatorics)或离散数学(
3、Discrete Mathematics)n n组合数学是一门研究离散对象的科学，狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。n n1666年Leibniz著Dissertatio de arte combinatoria,首次使用了组合一词。组合数学概述组合数学概述n n吴文俊吴文俊院士指出，每个时代都有它特殊的要求，院士指出，每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求分支，组合数学这个新的分支也是在时代的要求下产生的。下产生的。n n最
4、近，最近，吴文俊吴文俊院士又指出，信息技术很可能会给院士又指出，信息技术很可能会给数学本身带来一场根本性的变革，而组合数学则数学本身带来一场根本性的变革，而组合数学则将显示出它的重要作用。将显示出它的重要作用。n nGian-Carlo RotaGian-Carlo Rota教授曾提出要向中国领导人呼吁，教授曾提出要向中国领导人呼吁，组合数学是计算机软件产业的基础，中国最终一组合数学是计算机软件产业的基础，中国最终一定能成为一个软件大国，但是要实现这个目标的定能成为一个软件大国，但是要实现这个目标的一个突破点就是发展组合数学。一个突破点就是发展组合数学。组合数学历史及典型问题组合数学历史及典型
5、问题n n传说在公元前传说在公元前2323世纪大禹世纪大禹治水的时候，在黄河支流治水的时候，在黄河支流洛水中，浮现出一个洛水中，浮现出一个 大乌大乌龟，甲上背有龟，甲上背有9 9种花点的图种花点的图案，人们将图案中的花点案，人们将图案中的花点数了一下，竞惊奇地发现数了一下，竞惊奇地发现9 9种花点数正巧是种花点数正巧是1 19 9这这9 9个个数，各数位置的排列也相数，各数位置的排列也相当奇妙，横的当奇妙，横的3 3行、纵的行、纵的3 3列以及两对角线上各自的列以及两对角线上各自的数字之和都为数字之和都为1515。上图为三阶洛书幻方问题幻方问题n n组合数学中有许多象幻方这样精巧的结构。n n
6、1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。神 农 幻 方2200BC 1 15 14 412 6 7 9 8 10 11 513 3 2 16 15世纪 阶 幻 方贾宪三角贾宪三角n n中国最早的组合数学中国最早的组合数学理论可追溯到宋朝时理论可追溯到宋朝时期的期的”贾宪三角贾宪三角”,后后来被杨辉引用来被杨辉引用,所以普所以普遍称之为遍称之为”杨辉三角杨辉三角”,这在西方是这在西方是16541654年年由帕斯卡提出，但比由帕斯卡提出，但比中国晚了中国晚了400400多年。多年。11，11，2，11，3，3，11，4，6，4，11，5，10，10，5，11，6，1
7、5，20，15，6，1七桥问题七桥问题n n近代图论的历史可追溯到18世纪的七桥问题Pregel河横穿Knigsberg城，河上建有七座桥，能否设计散步路线，走过所有七座桥，每座桥恰好经过一次而回到同一地点？n nEuler1736年证明了不可能存在这样的路线。Euler环游（一笔画）环游（一笔画）n nEulerEuler于于17361736年给以否定：年给以否定：图有这样的路线当且仅当图有这样的路线当且仅当 每个点连接偶数条边。每个点连接偶数条边。n n图论的起源图论的起源Euler 定理定理n n如果一个图包含一条经过每条边恰好一次的闭途如果一个图包含一条经过每条边恰好一次的闭途径，则称
8、这个图为径，则称这个图为欧拉图欧拉图。n n对任意的非空连通图，若它是对任意的非空连通图，若它是欧拉的欧拉的,当且仅当它当且仅当它没有奇度点。没有奇度点。KnigsbergKnigsberg桥对应的图桥对应的图三十六军官问题三十六军官问题 n n普鲁士腓特烈大帝在一次检阅中要求：从不同的6个军团各选6种不同军衔的6名军官共36人，排成一个6行6列的方队，使得各行各列的6名军官恰好来自不同的军团而且军衔各不相同。n nEuler（1779）：办不到!但末能给出严格的证明。拉丁方阵与正交拉丁方阵 每名军官对应一个有序对（军团，军衔）以9名军官为例：军团阵列军团阵列 军衔阵列军衔阵列 并置阵列并置阵
9、列 （拉丁方阵）（拉丁方阵）（拉丁方阵）（拉丁方阵）（拉丁方阵）（拉丁方阵）（拉丁方阵）（拉丁方阵）（正交拉丁方阵）正交拉丁方阵）正交拉丁方阵）正交拉丁方阵）36 军官问题军官问题(欧拉欧拉 1779)The Great Frederic的阅兵难题的阅兵难题-欧拉的困惑欧拉的困惑 拉丁方阵拉丁方阵:正交拉丁方阵正交拉丁方阵:Euler 猜想猜想n n不存在6阶正交拉丁方n n不存在4k+2阶正交拉丁方 现在的结论现在的结论n n对任正整数对任正整数 n2,6，存在存在 n 阶正交拉丁方阶正交拉丁方四色问题四色问题n n在日常生活中我们常常可以遇到组合数学的问题。在日常生活中我们常常可以遇到组合
10、数学的问题。比如一个著名的世界难题比如一个著名的世界难题“四色猜想四色猜想”：一张：一张地图，用一种颜色对一个地区着色，那么一共只地图，用一种颜色对一个地区着色，那么一共只需要四种颜色就能保证每两个相邻的地区颜色不需要四种颜色就能保证每两个相邻的地区颜色不同。同。四色问题四色问题n n 18521852年，刚从伦敦大学毕业的年，刚从伦敦大学毕业的Francis Guthrie提提出了四色猜想。出了四色猜想。n n18781878年著名的英国数学家年著名的英国数学家Cayley向数学界征求解向数学界征求解答。答。n n此后数学家此后数学家 HeawoodHeawood 花费了毕生的精力致力于四花
11、费了毕生的精力致力于四色研究，于色研究，于18901890年证明了五色定理（年证明了五色定理（每个平面图每个平面图都是都是5 5顶点可着色的顶点可着色的）。）。n n直到直到19761976年年6 6月，美国数学家月，美国数学家 K.AppelK.Appel与与 W.W.HakenHaken，在，在3 3台不同的电子计算机上，用了台不同的电子计算机上，用了12001200小小时，才终于完成了时，才终于完成了“四色猜想四色猜想”的证明，从而使的证明，从而使 四色猜想四色猜想 成为了成为了四色定理四色定理。四色定理四色定理n nKempleKemple（18791879）：）：给出给出“证明证明”
12、。n nHeawoodHeawood（18901890）：）：指出漏洞。五色定理。指出漏洞。五色定理。n nAppel-Haken(1976)Appel-Haken(1976)：给出计算机证明给出计算机证明（12001200小时小时100100亿个判断）。亿个判断）。（右图为（右图为Appel Appel）Kirkman女生问题女生问题n nKirkman Kirkman（1806180618951895）18501850年：有年：有1515个女生，个女生，她们每天要做三人行的散她们每天要做三人行的散步，要使每个女生在一周步，要使每个女生在一周内的每天做三人行散步时，内的每天做三人行散步时，与
13、其她同学在组成三人小与其她同学在组成三人小组同行时，彼此只有一次组同行时，彼此只有一次相遇在同一小组，应怎样相遇在同一小组，应怎样安排？安排？n n组合设计的起源组合设计的起源Kirkman女生问题的一个解女生问题的一个解SunSunABCABCDEFDEFGHIGHIJKLJKLMNOMNOMonMonADHADHBEKBEKCIOCIOFLNFLNGJMGJMTueTueAEMAEMBHNBHNCGKCGKDILDILFJOFJOWedWedAFIAFIBLOBLOCHJCHJDKMDKMEGNEGNThuThuAGLAGLBDJBDJCFMCFMEHOEHOIKNIKNFriFriAJN
14、AJNBIMBIMCELCELDOGDOGFHKFHKSatSatAKOAKOBFGBFGCDNCDNEIJEIJHLMHLM中国邮递员问题中国邮递员问题n n1962年中国组合数学家管梅谷教授提出了著名的“中国邮递员问题”。n n一个邮递员从邮局出发，要走完他所管辖的每一条街道，然后返回邮局。那么如何选择一条尽可能短的路线。相识问题相识问题 n n1958年，美国的数学月刊上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3个人相互认识，或3个人相互不认识”。n n用6个顶点表示6个人，用红色连线表示两者相识，用蓝色连线表示两者不相识。于是问题化为下述命题：相识问题相识问题n n对对
15、6 6个顶点的完全图个顶点的完全图K K6 6任意进行红、蓝两边着色，任意进行红、蓝两边着色，则图中一定存在一个同色三角形。则图中一定存在一个同色三角形。n n五个点的则不然。五个点的则不然。nn 推广为一般问题则得到如下的Ramsey数问题：Ramsey定理定理n nRamsey(1903-1930)Ramsey(1903-1930)：给定任意：给定任意正整数正整数p p和和q q，总存在一个最小，总存在一个最小正整数正整数R(p,q)R(p,q)，使得，使得R(p,q)R(p,q)个人个人中或者有中或者有 p p 个人互相认识，或个人互相认识，或者有者有 q q 个人互不相识。个人互不相识
16、。n nR(p,q)R(p,q)称为称为RamseyRamsey数。数。n n只要人数足够多，则互相认识只要人数足够多，则互相认识的人会越来越多，或互不相识的人会越来越多，或互不相识的人会越来越多。的人会越来越多。Ramsey数数R(p,q)p,qp,q3 34 45 56 67 78 89 93 3 6 69 9141418182323282836364 41818 25 253535 41414949 61615656 84846969 1151155 5 43 43 49495858 87878080 143143101101 216216121121 3163166 6102102 1
17、65165111111 298298127127 495495169169 7807807 7205205 540540216216 10311031232232 171317138 8282282 18701870317317 358335839 9565565 65886588Ramsey数的计算数的计算n nRamseyRamsey数的计算是对人类智力数的计算是对人类智力的挑战！例如的挑战！例如R(4,5)=25R(4,5)=25 (1993 (1993年计算机年计算机1111年的计算量年的计算量)n nErdErd s s用如下比喻说明其困难用如下比喻说明其困难程度：一伙外星人入侵地球
18、，程度：一伙外星人入侵地球，要求一年内求得要求一年内求得R(5,5)R(5,5)，否则，否则将灭绝人类！那么也许人类能将灭绝人类！那么也许人类能集中所有计算机和专家来求出集中所有计算机和专家来求出它以自保；但如果外星人问的它以自保；但如果外星人问的是是R(6,6)R(6,6)，那么人类将别无选，那么人类将别无选择，只能拼死一战了。择，只能拼死一战了。最精美的组合定理最精美的组合定理RotaRota：如果要求在：如果要求在组合学中仅举出组合学中仅举出一个精美的定理，一个精美的定理，那么大多数组合那么大多数组合学家会提名学家会提名RamseyRamsey定理。定理。n n19841984年年Wol
19、fWolf奖得主奖得主ErdErd s sn n19971997年年FulkersonFulkerson奖得主奖得主KimKimn n19981998年年FieldsFields奖得主奖得主GowersGowersn n19991999年年WolfWolf奖得主奖得主LovaszLovaszn n20032003年年SteeleSteele奖得主奖得主GrahamGrahamn n20052005年年GG deldel奖得主奖得主AlonAlonn n20062006年年FieldsFields奖得主奖得主Tao Tao 均对均对RamseyRamsey理论有杰出贡献理论有杰出贡献Ramsey
20、理论的哲理意义理论的哲理意义n n完全的无序是不可能的完全的无序是不可能的(Complete disorder is impossibleComplete disorder is impossible)。任一。任一足够大的结构中必定包含一个给定大小的规则子结构。无序足够大的结构中必定包含一个给定大小的规则子结构。无序无意的行为产生了有规律的后果，发人深思耐人寻味。无意的行为产生了有规律的后果，发人深思耐人寻味。n n古人在满天的星斗中发现野兽和众神群集于天空的图形，以古人在满天的星斗中发现野兽和众神群集于天空的图形，以为是造物主的杰作。但根据为是造物主的杰作。但根据Ramsey Ramsey
21、定理，只要随机分布的定理，只要随机分布的星星数目足够多，就可以描绘出各种图形的轮廓。星星数目足够多，就可以描绘出各种图形的轮廓。n n19941994年年Statistical ScienceStatistical Science的一篇论文利用统计方法证明：圣经的一篇论文利用统计方法证明：圣经隐藏了许多讯息，而这些讯息是有意安排的，绝非文字排列隐藏了许多讯息，而这些讯息是有意安排的，绝非文字排列偶然造成的。偶然造成的。1997 1997 年年MichaelMichael Drosnin Drosnin的的The Bible CodeThe Bible Code 通过计算机扫读圣经中的通过计算机
22、扫读圣经中的304805304805个字母，发现圣经密码当中个字母，发现圣经密码当中传达的讯息除了拉宾被刺杀外，还包括美国肯尼迪和林肯两传达的讯息除了拉宾被刺杀外，还包括美国肯尼迪和林肯两位总统，以及印度总理甘地遇刺的事件，日本神户、美国旧位总统，以及印度总理甘地遇刺的事件，日本神户、美国旧金山的大地震、世界末日与广岛原子弹轰炸等，种种过去与金山的大地震、世界末日与广岛原子弹轰炸等，种种过去与未来发生的大事件。未来发生的大事件。稳定的婚姻问题稳定的婚姻问题n n 组合数学中有一个著名定理：如果一个村子里每一个女孩都恰好认识k个男孩，并且每一个男孩也恰好认识k个女孩，那么每一个女孩都可以嫁给她认
23、识的一个男孩，并且每一个男孩都可以娶一个他认识的女孩。（k 正则二部图，一定存在一个完美匹配）稳定的婚姻问题稳定的婚姻问题n n但是这样的安排方法不一定是最好的。假如能找到两对夫妇，彼此都更喜欢对方的配偶，那么这样婚姻有潜在的不稳定性。n n用图论匹配理论中Gale-Shapley算法，可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现。稳定的婚姻问题稳定的婚姻问题n n这种组合数学的方法有一个实际的用途：美国的这种组合数学的方法有一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请者排序。按这的志愿的先
24、后次序，同时也给申请者排序。按这样的次序考虑出的总的方案将没有医院和申请者样的次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。两者同时后悔的情况。实际上，高考学生的最后录取方案也可以用实际上，高考学生的最后录取方案也可以用这种方法。这种方法。栈排序问题栈排序问题(Knuth,1960s)n n模式:对任意一个排列,最小的元素用代替，次小的元素用代替以此类推，这样得到的排列叫的模式。n n例如914的模式为：31237925 的模式为：24513栈排序问题栈排序问题(Knuth,1960s)n n避免排列：一个排列是避免的，当且仅当它的任意子序列中没有模式。n n例如 132564是避
25、免 312的排列 146235是包含312的排列栈排序问题栈排序问题(Knuth,1960s)8 7 6 5 4 3 2 1避免312排列组合数学的应用组合数学的应用n n组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科如计算机科学、编码和密码学、物理、化学、生物等学科中，甚至在企业管理，交通规划，战争指挥，金融分析，城市物流等领域均有重要应用。组合数学的应用组合数学的应用n n著名的组合数学家著名的组合数学家 Thomas Thomas TutteTutte 在组合数学界是泰斗在组合数学界是泰斗级的大师。直到最近人们级的大师。直到最近人们才知道，原来他对提前结才知道，原来他对提前
26、结束束“二战二战”有着突出贡献。有着突出贡献。n nTutteTutte 从德军的两条情报密从德军的两条情报密码出发，用组合数学的方码出发，用组合数学的方法，重建了敌人的密码机，法，重建了敌人的密码机，确定了德军密码的内部结确定了德军密码的内部结构，从而获得了极为重要构，从而获得了极为重要的情报。的情报。组合数学的应用组合数学的应用n n在美国有一家公司用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。n n在美国已有专门的公司用组合设计的方法开发软件，来解决工业界中的试验设计问题。n n德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关
27、注。应用促进理论发展应用促进理论发展n n36个军官问题这个纯粹来自智力游戏的题目孕育着艰深的数学问题。Euler猜想直到二十世纪中叶才获得解决，有两个原因：一是理论上的准备。这类问题用初等方法很难解决，二十世纪代数和几何的发展为解决问题提供了必要工具（如Galois域上的射影几何即有限几何等）；二是生产实际的推动。数理统计学家Fisher将正交拉丁方用于试验设计，例如，用二种原料合成某染料，每种原料有3个水平，怎样安排试验能使每种原料的各种水平各碰一次？这正好是3阶的正交拉丁方阵问题。Fisher的试验设计是一股巨大的推动力量，把一种数学游戏变成了节约人力物力的具有重大价值的科学方法。源出于
28、游戏受惠于数学落脚于应用n n“KirkmanKirkman女生问题女生问题”引出组合数学的一个重要分支引出组合数学的一个重要分支组合设计。对这些数学游戏，一旦当人们认识到组合设计。对这些数学游戏，一旦当人们认识到它们在数学和其他科学上的深刻含义后，便又促使它们在数学和其他科学上的深刻含义后，便又促使人们对它进行更深入的研究，从而丰富了数学学科人们对它进行更深入的研究，从而丰富了数学学科的内容和知识。该问题就是最典型的组合设计问题。的内容和知识。该问题就是最典型的组合设计问题。其本质就是如何将一个集合中的元素组合成一定的其本质就是如何将一个集合中的元素组合成一定的子集系以满足一定的要求。表面上
29、看来，子集系以满足一定的要求。表面上看来，KirkmanKirkman女生问题是纯粹的数学游戏，然而它的解却在医药女生问题是纯粹的数学游戏，然而它的解却在医药试验设计上有很广泛的运用。试验设计上有很广泛的运用。德国组合数学家利用德国组合数学家利用组合设计的方法研究药物结构，为制药公司节省了组合设计的方法研究药物结构，为制药公司节省了大量的费用。在美国也有专门的公司用组合设计的大量的费用。在美国也有专门的公司用组合设计的方法开发软件，来解决工业界中的试验设计问题。方法开发软件，来解决工业界中的试验设计问题。网络流问题网络流问题n n随着中国经济快速的增长，城市化是未来中国的随着中国经济快速的增长
30、，城市化是未来中国的发展方向。人大通过的发展方向。人大通过的“十五十五”规划，把物流业规划，把物流业作为战略重点列入要大力发展的新兴服务产业。作为战略重点列入要大力发展的新兴服务产业。如何制定一个运输计划使生产地到销售地的产品如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。输送量最大。这就是一个网络最大流问题。网络流问题网络流问题n n19561956年年Ford Ford 和和Fulkerson Fulkerson 提出了关于网络流问题的提出了关于网络流问题的一个重要定理。一个重要定理。n n最大流最小割定理最大流最小割定理：在任何网络中，最大流的值：在任何网
31、络中，最大流的值等于最小割的容量。等于最小割的容量。n n由这个定理可以引出求网络最大流的一个算法由这个定理可以引出求网络最大流的一个算法标号法标号法。n n19701970年，年，EdmondsEdmonds和和KarpKarp 对标号程序加以改进，对标号程序加以改进，使之成为一个好的算法使之成为一个好的算法。网络可靠性问题网络可靠性问题n n一个通讯网络怎样布局稳定性最好，而且费用最节省？n n美国的贝尔实验室和IBM公司都有世界一流的组合数学家在研究这个问题，这个问题直接关系到巨大的经济利益。最短网络问题最短网络问题n如何用最短的线路将三部电话连起来？n此问题可抽象为设ABC为等边三角形
32、，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如ABAC）。ABC最短网络问题最短网络问题n但若增加一个周转站（新点P），连接4点的新网络的最短路线为PAPBPC。最短新路径之长N比原来只连三点的最短路径O要短。n这样得到的网络不仅比原来节省材料，而且稳定性也更好。ABCP无尺度网络无尺度网络n n2020世纪世纪2020年代，由年代，由KarinthyKarinthy提出。提出。n n19501950年，年，PoolPool 和和 KochenKochen提出这样一个问题：提出这样一个问题：“两两个毫无关系的人，要让他们互相认识，至少要经个毫无关系的人，要让
33、他们互相认识，至少要经过多少人？过多少人？”n n美国哈佛大学社会心理学家美国哈佛大学社会心理学家S.MilgramS.Milgram在在19671967年做年做过一项有趣的实验，据说他从内布拉斯加州的奥过一项有趣的实验，据说他从内布拉斯加州的奥马哈随机选了马哈随机选了300300人，然后请他们每个人尝试寄一人，然后请他们每个人尝试寄一封信到波士顿的一位证券业务员。寄信的规则很封信到波士顿的一位证券业务员。寄信的规则很简单，就是任何收信者只能把信寄给自己熟识的简单，就是任何收信者只能把信寄给自己熟识的人。人。重要结论重要结论n n“6度分离”对每个人来说，平均大约只需要通过个人就能将信寄到目的
34、地。n n研究无尺度网络，对于防备黑客攻击、防治流行病、和开发新药等，都具有重要的意义。n n在1999年，Barabasi et al.发现在因特网上，任意两个网页间的链接最多为19次。(Nature 401,1999)生物数学生物数学n n目前，计算生物学、基因理论、生物信息学都是最前沿的研究领域。n n随着人类基因组计划的完成和其他基因计划的完成，所有公认的和潜在的蛋白质元都可以被确定，通过大规模的实验技术，可以生成大量的生物学数据。生物数学生物数学n n如何处理这些数据来获得生物学的信息，这里如何处理这些数据来获得生物学的信息，这里组组合数学和随机图论都起到了关键的作用。合数学和随机图
35、论都起到了关键的作用。n n如果将基因看作网络中的顶点，将他们之间的作如果将基因看作网络中的顶点，将他们之间的作用看作网络中的边，那么每一次大规模实验将给用看作网络中的边，那么每一次大规模实验将给我们带来关于基因交互作用网络的一些信息。这我们带来关于基因交互作用网络的一些信息。这个网络的拓扑性质是科学家们关心的焦点（如每个网络的拓扑性质是科学家们关心的焦点（如每一个顶点的度和网络中的最小距离问题是两个初一个顶点的度和网络中的最小距离问题是两个初步的问题）。步的问题）。中国的组合数学中国的组合数学河图洛书九宫图河图洛书九宫图n n易曰：河出图，洛出书，圣人则之。河图洛书是最早的幻方。易曰：河出图
36、，洛出书，圣人则之。河图洛书是最早的幻方。n n“二、九、四；七、五、三；六、一、八二、九、四；七、五、三；六、一、八”-大戴礼记大戴礼记 明堂明堂 n n黄帝内经黄帝内经 灵枢灵枢的的九宫八风九宫八风篇。篇。n n“九宫者，即二四为肩，六八为足，左三右七，戴九履一，五居中央九宫者，即二四为肩，六八为足，左三右七，戴九履一，五居中央 ”-(-(汉汉)徐岳撰徐岳撰 (北周北周)甄鸾注甄鸾注 n n杨辉杨辉续古摘奇算法续古摘奇算法(1275)(1275)进一步给出了四阶幻方构造方法。此外，进一步给出了四阶幻方构造方法。此外，他还构造出了五阶、六阶、七阶、八阶、九阶和十阶幻方他还构造出了五阶、六阶、
37、七阶、八阶、九阶和十阶幻方(百子图百子图 )。四九二三五七八一六幻方的转播幻方的转播n n1212世纪的阿拉伯文献世纪的阿拉伯文献里有六阶幻方的记载里有六阶幻方的记载n n印度印度12-1312-13世纪时的世纪时的JainaJaina幻方（右下）幻方（右下）n n1515世纪幻方传往欧洲世纪幻方传往欧洲n n西方最早的幻方出现西方最早的幻方出现在德国在德国DD rer 1514rer 1514年年的名画的名画”忧郁者忧郁者”中。中。n n19771977年美国旅行者年美国旅行者1 1号和号和2 2号宇宙飞船带号宇宙飞船带去去JainaJaina幻方。幻方。杨辉三角杨辉三角n n杨辉（南宋）著
38、杨辉（南宋）著详详解九章算法解九章算法(1261(1261年年)中曾引贾宪（北宋）中曾引贾宪（北宋）的的“开方作法本源开方作法本源”图。图。n n杨辉在承上启下、数杨辉在承上启下、数学教育方面有突出贡学教育方面有突出贡献。献。n nPascalPascal三角三角(1654(1654年年)可上可上溯至溯至15371537年年朱世杰恒等式（元）朱世杰恒等式（元）n n朱世杰是中国传统数学中水平最高者之一。朱世杰是中国传统数学中水平最高者之一。他在他在四元玉鉴四元玉鉴（13031303）得到：）得到：n nZeilberger:Chus 1303 Identity Implies Zeilberg
39、er:Chus 1303 Identity Implies Bombieris 1990 Norm-Inequality,1994Bombieris 1990 Norm-Inequality,1994李善兰恒等式（清）李善兰恒等式（清）n n李善兰（李善兰（1811-18821811-1882）是开展）是开展现代数学研究的第一位中国现代数学研究的第一位中国数学家。他从研究中国传统数学家。他从研究中国传统的垛积问题入手，获得了一的垛积问题入手，获得了一些相当于现代组合数学中的些相当于现代组合数学中的成果。如在成果。如在垛积比类垛积比类中中提出提出 Erds-Ko-Rado定理定理n nFrank
40、l-GrahamFrankl-Graham：ErdErd s-s-柯召柯召-Rado-Rado定理是定理是组合数学中的一个主要结果，开辟了极组合数学中的一个主要结果，开辟了极值集合论迅速发展的道路。值集合论迅速发展的道路。n n柯召柯召(1910-2002)(1910-2002)：1935-19381935-1938在英国在英国ManchesterManchester大学期间与大学期间与ErdErd s s相识，该结相识，该结果在果在19381938年得到，于年得到，于19611961年发表。年发表。n nErdErd s s（1913-19961913-1996）是数学史上著作数）是数学史上
41、著作数仅次于仅次于EulerEuler的传奇人物（约的传奇人物（约15001500篇），篇），他曾说在他所有著作中，含有上述结果他曾说在他所有著作中，含有上述结果的论文是被同行们引用次数最多的。的论文是被同行们引用次数最多的。Gould-Hsu反演公式反演公式n n19731973年年Duke Math.J.Duke Math.J.上发表了上发表了GouldGould与徐利治的论文与徐利治的论文“Some Some new inverse series relationsnew inverse series relations”，这是，这是中美关系正常化开始后两国学中美关系正常化开始后两国学者
42、合作发表的第一篇论文。者合作发表的第一篇论文。n nGould-HsuGould-Hsu反演公式可用于证明反演公式可用于证明和发现恒等式，也可以应用于和发现恒等式，也可以应用于算法分析和插值方法中。算法分析和插值方法中。中国邮递员问题中国邮递员问题n n管梅谷（管梅谷（19601960）：）：邮递员从邮局出发送信，邮递员从邮局出发送信，要求对辖区内每条街都至要求对辖区内每条街都至少通过一次再回邮局，怎少通过一次再回邮局，怎样选择一条最短路线样选择一条最短路线?n n现实生活中很多问题可以现实生活中很多问题可以转化为中国邮递员问题。转化为中国邮递员问题。n n有好算法！有好算法！论不相交斯坦纳三
43、元系大集论不相交斯坦纳三元系大集n n陆家羲陆家羲(1935(19351983)1983)，包头九中物理教师，包头九中物理教师n n19611961年完成论文年完成论文“冠克满系列和斯坦纳系冠克满系列和斯坦纳系列的制作方法列的制作方法”，三次投稿国内杂志未，三次投稿国内杂志未中。前者中。前者19711971年为国外学者解决发表，惜年为国外学者解决发表，惜哉！哉！n n19831983年和年和19841984年在年在J.Combin.Theory Ser.AJ.Combin.Theory Ser.A 上上发表题为发表题为 “On large sets of disjoint On large s
44、ets of disjoint Steiner triple systemsSteiner triple systems ”的六篇论文。的六篇论文。n n以以“论不相交斯坦纳三元系大集论不相交斯坦纳三元系大集”系列系列论文获论文获19871987年国家自然科学一等奖。年国家自然科学一等奖。Gilbert-Pollak猜想猜想n n19901990年，堵丁柱和黄光明合作证年，堵丁柱和黄光明合作证明了明了 Gilbert-PollakGilbert-Pollak猜想猜想(1968)(1968)。n n被列为被列为19891989年年-1990-1990年度美国离散年度美国离散数学界和理论计算机科学
45、界重大数学界和理论计算机科学界重大成果。成果。n n被被不列颠百科全书不列颠百科全书19921992年鉴年鉴列为列为6 6项数学成果的第一项。项数学成果的第一项。n n堵丁柱获得中国科学院自然科学堵丁柱获得中国科学院自然科学一等奖、国家科技进步二等奖和一等奖、国家科技进步二等奖和中国青年科学家奖中国青年科学家奖 。机器证明机器证明吴消元法吴消元法n n1976年吴文俊教授开始进行研究几何定理的机器证明，并在很短的时间内取得重大突破。n n他的基本思想如下：引进坐标，将几何定理用代数方程组的形式表达；提出一套完整可行的符号解法，将此代数方程组求解。此两步中，一般第二步更为困难。机器证明机器证明吴
46、消元法吴消元法n n周咸青周咸青利用并发展吴方法，编制出计算机软件，利用并发展吴方法，编制出计算机软件，证明了证明了500500多条有相当难度的几何定理，并在美多条有相当难度的几何定理，并在美国出版了几何定理机器证明的专著。国出版了几何定理机器证明的专著。n n吴方法不仅可证明已有的几何定理，而且可以自吴方法不仅可证明已有的几何定理，而且可以自动发现新的定理。可以从动发现新的定理。可以从KerlerKerler定律推导牛顿定定律推导牛顿定律；解决一些非线性规划问题；给出律；解决一些非线性规划问题；给出PumaPuma型机型机器人的逆运动方程的解。器人的逆运动方程的解。n n吴文俊教授还将其方法
47、推广到微分几何定理的机吴文俊教授还将其方法推广到微分几何定理的机器证明上。器证明上。组合数学的内容组合数学的内容组合数学的研究内容组合数学的研究内容n n组合数学研究的中心问题是按照一定的规划来安组合数学研究的中心问题是按照一定的规划来安排一些与物件有关的问题。排一些与物件有关的问题。1.1.存在问题存在问题当符合要求的安排并非显然存在或当符合要求的安排并非显然存在或不存在时，首要的问题是证明或否定它的存在不存在时，首要的问题是证明或否定它的存在.2.2.计算问题或分类问题计算问题或分类问题当符合要求的安排显然当符合要求的安排显然存在，或者已证明它存在时，求出这类安排的各存在，或者已证明它存在时，求出这类安排的各抒己见，或者把它分类抒己见，或者把它分类.3.3.构造问题（组合设计）构造问题（组合设计）把满足某种条件的安把满足某种条件的安排构造出来排构造出来.4.4.优化问题优化问题给出最优标准，找出满足给定条件给出最优标准，找出满足给定条件的最优安排的最优安排.组合数学的分支组合数学的分支n n组合分析n n代数组合n n极值集论n n图 论n n组合设计n n组合优化n n组合算法