组合数学绪论20130301.

组合数学——绪论主讲教师魏毅强教授联系电话[e-mail]@tyut.edu.cn现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等；另一类就是研究离散对象的，如离散、组合数学等。计算机出现以后，由于离散对象的处理是计算机科学的核心，研究离散对象的组合数学得到迅猛发展。组合数学是一个古老而又年轻的数学分支。组合数学概述[e-mail]吴文俊院士指出，每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求下产生的。吴文俊院士又指出，信息技术很可能会给数学本身带来一场根本性的变革，而组合数学则将显示出它的重要作用。Gian-CarloRota教授曾提出要向中国领导人呼吁，组合数学是计算机软件产业的基础，中国最终一定能成为一个软件大国，但是要实现这个目标的一个突破点就是发展组合数学。组合数学概述[e-mail]上图为三阶洛书传说在公元前23世纪大禹治水的时候，在黄河支流洛水中，浮现出一个大乌龟，甲上背有9种花点的图案，人们将图案中的花点数了一下，竞惊奇地发现9种花点数正巧是1—9这9个数，各数位置的排列也相当奇妙，横的3行、纵的3列以及两对角线上各自的数字之和都为15。组合数学的历史[e-mail]519372486组合数学的历史幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。[e-mail]组合数学中有许多象幻方这样精巧的结构。1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。神农幻方4923578162200BC1151441267981011513321615世纪４阶幻方幻方问题[e-mail]中国最早的组合数学理论可追溯到宋朝时期的”贾宪三角”,后来被杨辉引用,所以普遍称之为”杨辉三角”,这在西方是1654年由帕斯卡提出，但比中国晚了400多年。11，11，2，11，3，3，11，4，6，4，11，5，10，10，5，11，6，15，20，15，6，1贾宪三角[e-mail]上图为一份用希腊文写在羊皮纸上的阿基米德手稿副本,最近科学家借助现代科技手段初步破译了古希腊数学家阿基米德的这篇论文,结论是这篇被称作Stomachion的论文解决的是组合数学问题。阿基米德手稿[e-mail]在论文中阿基米德是在计算把14条不规则的纸带拼成正方形一共能有多少种不同的拼法。这在现在被称为tiling（贴瓷砖）问题。当今数学家借助计算机得出的答案是17152种拼法，这在当时是相当困难的。阿基米德手稿[e-mail]-PeriodicTilingsPenroseTilingsSymmetricTilingsSymmetricTilings阿基米德手稿[e-mail]1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。组合数学的产生与发展[e-mail]七桥问题与Euler定理近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。Euler1736年证明了不可能存在这样的路线。[e-mail]如果一个图包含一条经过每条边恰好一次的闭途径，则称这个图为欧拉图。对任意的非空连通图，若它是欧拉的,当且仅当它没有奇度点。Königsberg桥对应的图七桥问题与Euler定理[e-mail]12211232313121243231434214132正交拉丁方阵:12331223112323131212331223123231311236军官问题与正交拉丁方拉丁方阵:TheGreatFrederic的阅兵难题---欧拉的困惑[e-mail]猜想不存在6阶正交拉丁方不存在4k+2阶正交拉丁方现在的结论对任正整数n≠2,6，存在n阶正交拉丁方36军官问题与正交拉丁方[e-mail]组合数学的应用组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科如计算机科学、编码和密码学、物理、化学、生物等学科中，甚至在企业管理，交通规划，战争指挥，金融分析，城市物流等领域均有重要应用。[e-mail]组合数学的应用著名的组合数学家ThomasTutte在组合数学界是泰斗级的大师。直到最近人们才知道，原来他对提前结束“二战”有着突出贡献。Tutte从德军的两条情报密码出发，用组合数学的方法，重建了敌人的密码机，确定了德军密码的内部结构，从而获得了极为重要的情报。[e-mail]组合数学的应用在美国有一家公司用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。在美国已有专门的公司用组合设计的方法开发软件，来解决工业界中的试验设计问题。德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。[e-mail]四色问题在日常生活中我们常常可以遇到组合数学的问题。比如一个著名的世界难题“四色猜想”：一张地图，用一种颜色对一个地区着色，那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。[e-mail]四色问题1852年，刚从伦敦大学毕业的FrancisGuthrie提出了四色猜想。1878年著名的英国数学家Cayley向数学界征求解答。此后数学家Heawood花费了毕生的精力致力于四色研究，于1890年证明了五色定理（每个平面图都是5顶点可着色的）。直到1976年6月，美国数学家K.Appel与W.Haken，在3台不同的电子计算机上，用了1200小时，才终于完成了“四色猜想”的证明，从而使四色猜想成为了四色定理。[e-mail]中国邮递员问题1962年中国组合数学家管梅谷教授提出了著名的“中国邮递员问题”。一个邮递员从邮局出发，要走完他所管辖的每一条街道，然后返回邮局。那么如何选择一条尽可能短的路线。[e-mail]中国邮递员问题这个问题可以转化为：给定一个具有非负权的赋权图G，（1）用添加重复边的方法求G的一个Euler赋权母图G*，使得尽可能小。（2）求G*的Euler环游。这个问题可以由Fleury算法和1973年著名组合数学家J.Edmonds和Johnson给出的一个好的算法解决。)(\)(*)([e-mail]货郎担问题一个货郎要去若干城镇卖货，然后回到出发地，给定各城镇之间所需的旅行时间后，应怎样计划他的路线，使他能去每个城镇恰好一次而且总时间最短？[e-mail]货郎担问题用图论的术语说，就是在一个赋权完全图中，找出一个具有最小权的Hamilton圈（包含图G的每个顶点的圈)。这个问题目前还没有有效的算法。Hamilton问题是图论的一个重要问题，图论中的许多问题，包括四色问题、图的因子问题，最终都与Hamilton问题有关。[e-mail]相识问题1958年，美国的《数学月刊》上登载着这样一个有趣的问题：“任何6个人的聚会，其中总会有3个人相互认识，或3个人相互不认识”。用6个顶点表示6个人，用红色连线表示两者相识，用蓝色连线表示两者不相识。于是问题化为下述命题：[e-mail]相识问题对6个顶点的完全图K6任意进行红、蓝两边着色，则图中一定存在一个同色三角形。[e-mail]数推广为一般问题：给定任意正整数a和b，总存在一个最小整数r(a,b)，使得r(a,b)个人中或者有a个人互相认识，或者有b个人互相不认识。称r(a,b)为Ramsey（拉姆齐）数。[e-mail]ös-Szekeres定理Ramsey定理是由Erdös和Szekeres于1935年提出的。它是下述定理的一个推广：定理（Erdös和Szekeres）：若a,b∈N，n=ab+1，且x1,…,xn是任一n个实数的序列，则这个序列包含一个有a+1项的单调递增（递减）的子序列，或一个有b+1项的单调递减（递增）的子序列。[e-mail]问题对于n≥3，处于平面上一般位置（任意三个顶点不共线）的g(n)个顶点中，一定有n个顶点组成一个凸n边形。5个顶点时的情形，5顶点一定含有一个凸四边形Erdos和Szekeres(1935)证明了g(n)一定存在，并且有1242)(22[e-mail]机器证明——吴消元法1976年吴文俊教授开始进行研究几何定理的机器证明，并在很短的时间内取得重大突破。他的基本思想如下：引进坐标，将几何定理用代数方程组的形式表达；提出一套完整可行的符号解法，将此代数方程组求解。此两步中，一般第二步更为困难。[e-mail]周咸青利用并发展吴方法，编制出计算机软件，证明了500多条有相当难度的几何定理，并在美国出版了几何定理机器证明的专著。吴方法不仅可证明已有的几何定理，而且可以自动发现新的定理。可以从Kerler定律推导牛顿定律；解决一些非线性规划问题；给出Puma型机器人的逆运动方程的解。吴文俊教授还将其方法推广到微分几何定理的机器证明上。机器证明——吴消元法[e-mail]网络流问题随着中国经济快速的增长，城市化是未来中国的发展方向。在“十二五”规划，把物流业作为山西战略重点列入要大力发展的新兴服务产业。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。[e-mail]网络流问题1956年Ford和Fulkerson提出了关于网络流问题的一个重要定理。最大流最小割定理：在任何网络中，最大流的值等于最小割的容