1浅谈组合数学.ppt

组合数学的分支 组合分析 代数组合 极值集论 图 论 组合设计 组合优化 组合算法 * 栈排序问题(Knuth, 1960’s) 模式: 对任意一个排列π , 最小的元素用１代替，次小的元素用２代替……以此类推，这样得到的排列叫π的模式。 例如 　　　914的模式为：312 　　　37925 的模式为： 24513 栈排序问题(Knuth, 1960’s) 避免３１２排列：一个排列是避免３１２的，当且仅当它的任意子序列中没有３１２模式。 例如 　　　π＝ 132564是避免 312的排列 π＝ 146235是包含312的排列 栈排序问题(Knuth, 1960’s) 8 7 6 5 4 3 2 1 避免312排列 组合数学的应用 组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科如计算机科学、编码和密码学、物理、化学、生物等学科中，甚至在企业管理，交通规划，战争指挥，金融分析，城市物流等领域均有重要应用。 组合数学的应用 著名的组合数学家 Thomas Tutte 在组合数学界是泰斗级的大师。直到最近人们才知道，原来他对提前结束“二战”有着突出贡献。 Tutte 从德军的两条情报密码出发，用组合数学的方法，重建了敌人的密码机，确定了德军密码的内部结构，从而获得了极为重要的情报。 组合数学的应用 在美国有一家公司用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。 在美国已有专门的公司用组合设计的方法开发软件，来解决工业界中的试验设计问题。 德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。 应用促进理论发展 36个军官问题这个纯粹来自智力游戏的题目孕育着艰深的数学问题 。Euler猜想直到二十世纪中叶才获得解决，有两个原因：一是理论上的准备。这类问题用初等方法很难解决，二十世纪代数和几何的发展为解决问题提供了必要工具（如Galois域上的射影几何即有限几何等）；二是生产实际的推动。数理统计学家Fisher将正交拉丁方用于试验设计，例如，用二种原料合成某染料，每种原料有3个水平，怎样安排试验能使每种原料的各种水平各碰一次？这正好是3阶的正交拉丁方阵问题。 Fisher的试验设计是一股巨大的推动力量，把一种数学游戏变成了节约人力物力的具有重大价值的科学方法。 源出于游戏受惠于数学落脚于应用 “Kirkman女生问题”引出组合数学的一个重要分支—组合设计。对这些数学游戏，一旦当人们认识到它们在数学和其他科学上的深刻含义后，便又促使人们对它进行更深入的研究，从而丰富了数学学科的内容和知识。该问题就是最典型的组合设计问题。其本质就是如何将一个集合中的元素组合成一定的子集系以满足一定的要求。表面上看来，Kirkman女生问题是纯粹的数学游戏，然而它的解却在医药试验设计上有很广泛的运用。德国组合数学家利用组合设计的方法研究药物结构，为制药公司节省了大量的费用。在美国也有专门的公司用组合设计的方法开发软件，来解决工业界中的试验设计问题。 网络流问题 随着中国经济快速的增长，城市化是未来中国的发展方向。人大通过的“十五”规划，把物流业作为战略重点列入要大力发展的新兴服务产业。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。 网络流问题 1956年Ford 和Fulkerson 提出了关于网络流问题的一个重要定理。 最大流最小割定理：在任何网络中，最大流的值等于最小割的容量。 由这个定理可以引出求网络最大流的一个算法——标号法。 1970年，Edmonds和Karp 对标号程序加以改进，使之成为一个好的算法。 网络可靠性问题 一个通讯网络怎样布局稳定性最好，而且费用最节省？ 美国的贝尔实验室和IBM公司都有世界一流的组合数学家在研究这个问题，这个问题直接关系到巨大的经济利益。 最短网络问题 如何用最短的线路将三部电话连起来？ 此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。 A B C 最短网络问题 但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长N比原来只连三点的最短路径O要短。 这样得到的网络不仅比原来节省材料，而且稳定性也更好。 A B C P 无尺度网络 20世纪20年代，由Karinthy提出。 1950年， Pool 和 Kochen提出这样一个问题：“两个毫无关系的人，要让他们互相认识，至少要经过多少人？” 美国哈佛大学社会心理学家S. Milgram在1967年做过一项有趣的实验，据说他