《浅谈组合数学》PPT课件

《《浅谈组合数学》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浅谈组合数学组合数学概述现代数学根据所研究的对象可分为两类：连续数学：以微积分为基础，传统主流；离散数学：伴随计算机科学，方兴未艾。计算机出现以后，由于离散对象的处理是计算机科学的核心，研究离散对象的组合数学得到迅猛发展。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。组合数学概述组合数学（Combin

2、atorialMathematics)也称组合学(Combinatorics)或离散数学(DiscreteMathematics)组合数学是一门研究离散对象的科学，狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。1666年Leibniz著《Dissertatiodeartecombinatoria》,首次使用了组合一词。组合数学概述吴文俊院士指出，每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求下产生的。最近，吴文俊院士又指出，信息技术很可能会给

3、数学本身带来一场根本性的变革，而组合数学则将显示出它的重要作用。Gian-CarloRota教授曾提出要向中国领导人呼吁，组合数学是计算机软件产业的基础，中国最终一定能成为一个软件大国，但是要实现这个目标的一个突破点就是发展组合数学。组合数学历史及典型问题传说在公元前23世纪大禹治水的时候，在黄河支流洛水中，浮现出一个大乌龟，甲上背有9种花点的图案，人们将图案中的花点数了一下，竞惊奇地发现9种花点数正巧是1—9这9个数，各数位置的排列也相当奇妙，横的3行、纵的3列以及两对角线上各自的数字之和都为15。上图为三阶洛书幻方问题组合数学中有许多象幻方这样

4、精巧的结构。1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。神农幻方2200BC1151441267981011513321615世纪４阶幻方贾宪三角中国最早的组合数学理论可追溯到宋朝时期的”贾宪三角”,后来被杨辉引用,所以普遍称之为”杨辉三角”,这在西方是1654年由帕斯卡提出，但比中国晚了400多年。11，11，2，11，3，3，11，4，6，4，11，5，10，10，5，11，6，15，20，15，6，1七桥问题近代图论的历史可追溯到18世纪的七桥问题—Pregel河横穿Königsberg城，河上建有七座桥，能否设计

5、散步路线，走过所有七座桥，每座桥恰好经过一次而回到同一地点？Euler1736年证明了不可能存在这样的路线。Euler环游（一笔画）Euler于1736年给以否定：图有这样的路线当且仅当每个点连接偶数条边。图论的起源Euler定理如果一个图包含一条经过每条边恰好一次的闭途径，则称这个图为欧拉图。对任意的非空连通图，若它是欧拉的,当且仅当它没有奇度点。Königsberg桥对应的图三十六军官问题普鲁士腓特烈大帝在一次检阅中要求：从不同的6个军团各选6种不同军衔的6名军官共36人，排成一个6行6列的方队，使得各行各列的6名军官恰好来自不同的军团而且军衔

6、各不相同。Euler（1779）：办不到!但末能给出严格的证明。拉丁方阵与正交拉丁方阵每名军官对应一个有序对（军团，军衔）以9名军官为例：军团阵列军衔阵列并置阵列（拉丁方阵）（拉丁方阵）（正交拉丁方阵）36军官问题(欧拉1779)TheGreatFrederic的阅兵难题-------欧拉的困惑拉丁方阵:正交拉丁方阵:Euler猜想不存在6阶正交拉丁方不存在4k+2阶正交拉丁方现在的结论对任正整数n≠2,6，存在n阶正交拉丁方四色问题在日常生活中我们常常可以遇到组合数学的问题。比如一个著名的世界难题“四色猜想”：一张地图，用一种颜色对一个地区着色，

7、那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。四色问题1852年，刚从伦敦大学毕业的FrancisGuthrie提出了四色猜想。1878年著名的英国数学家Cayley向数学界征求解答。此后数学家Heawood花费了毕生的精力致力于四色研究，于1890年证明了五色定理（每个平面图都是5顶点可着色的）。直到1976年6月，美国数学家K.Appel与W.Haken，在3台不同的电子计算机上，用了1200小时，才终于完成了“四色猜想”的证明，从而使"四色猜想"成为了四色定理。四色定理Kemple（1879）：给出“证明”。Heawood（1890

8、）：指出漏洞。五色定理。Appel-Haken(1976)：给出计算机证明（1200小时100亿个判断）。（右图为Appe