浅谈组合数学.pptVIP

浅谈组合数学

南开大学组合数学中心陈永川2004年7月

组合数学概述现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等；另一类就是研究离散对象的组合数学。计算机出现以后，由于离散对象的处理是计算机科学的核心，研究离散对象的组合数学得到迅猛开展。

组合数学概述吴文俊院士指出，每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求下产生的。最近，吴文俊院士又指出，信息技术很可能会给数学本身带来一场根本性的变革，而组合数学那么将显示出它的重要作用。Gian-CarloRota教授曾提出要向中国领导人呼吁，组合数学是计算机软件产业的根底，中国最终一定能成为一个软件大国，但是要实现这个目标的一个突破点就是开展组合数学。

组合数学的历史传说在公元前23世纪大禹治水的时候，在黄河支流洛水中，浮现出一个大乌龟，甲上背有9种花点的图案，人们将图案中的花点数了一下，竞惊奇地发现9种花点数正巧是1—9这9个数，各数位置的排列也相当奇妙，横的3行、纵的3列以及两对角线上各自的数字之和都为15。上图为三阶洛书

幻方问题组合数学中有许多象幻方这样精巧的结构。1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。神农幻方2200BC1151441267981011513321615世纪４阶幻方

阿基米德手稿上图为一份用希腊文写在羊皮纸上的阿基米德手稿副本,最近科学家借助现代科技手段初步破译了古希腊数学家阿基米德的这篇论文,结论是这篇被称作Stomachion的论文解决的是组合数学问题。

阿基米德手稿在论文中阿基米德是在计算把14条不规那么的纸带拼成正方形一共能有多少种不同的拼法。这在现在被称为tiling问题。当今数学家借助计算机得出的答案是17152种拼法，这在当时是相当困难的。

PeriodicTilingsNon-PeriodicTilingsPenroseTilingsSymmetricTilingsSymmetricTilings

贾宪三角中国最早的组合数学理论可追溯到宋朝时期的”贾宪三角”,后来被杨辉引用,所以普遍称之为”杨辉三角”,这在西方是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世纪的七桥问题—穿过K?nigsberg城的七座桥，要求每座桥通过一次且仅通过一次。Euler1736年证明了不可能存在这样的路线。

Euler定理如果一个图包含一条经过每条边恰好一次的闭途径，那么称这个图为欧拉图。对任意的非空连通图，假设它是欧拉的,当且仅当它没有奇度点。K?nigsberg桥对应的图

36军官问题(欧拉1779)

TheGreatFrederic的阅兵难题-------欧拉的困惑

拉丁方阵:

正交拉丁方阵:

Euler猜测不存在6阶正交拉丁方不存在4k+2阶正交拉丁方现在的结论对任正整数n≠2,6，存在n阶正交拉丁方

组合数学的应用组合数学不仅在根底数学研究中具有极其重要的地位，在其它的学科如计算机科学、编码和密码学、物理、化学、生物等学科中，甚至在企业管理，交通规划，战争指挥，金融分析，城市物流等领域均有重要应用。

组合数学的应用著名的组合数学家ThomasTutte在组合数学界是泰斗级的大师。直到最近人们才知道，原来他对提前结束“二战”有着突出奉献。Tutte从德军的两条情报密码出发，用组合数学的方法，重建了敌人的密码机，确定了德军密码的内部结构，从而获得了极为重要的情报。

组合数学的应用在美国有一家公司用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。在美国已有专门的公司用组合设计的方法开发软件，来解决工业界中的试验设计问题。德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。

四色问题在日常生活中我们常常可以遇到组合数学的问题。比方一个著名的世界难题“四色猜测”：一张地图，用一种颜色对一个地区着色，那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。

四色问题1852年，刚从伦敦大学毕业的FrancisGuthrie提出了四色猜测。1878年