组合数学001x课件.ppt

组合数学的历史 歌尼斯堡七桥问题 近代图论的历史可追溯到18世纪的七桥问题—穿过K?nigsberg城的七座桥，要求每座桥通过一次且仅通过一次。 Euler1736年证明了不可能存在这样的路线。 Euler 定理 如果一个图包含一条经过每条边恰好一次的闭途径，则称这个图为欧拉图。 对任意的非空连通图，若它是欧拉的, 当且仅当它没有奇度点。 贾宪三角 中国最早的组合数学理论可追溯到宋朝时期的”贾宪三角”, 后来被杨辉引用, 所以普遍称之为”杨辉三角”, 这在西方是1654年由帕斯卡提出，但比中国晚了400多年。 36 军官问题 (欧拉 1779) 36军官问题 (欧拉，1781)：36名军官来自6个不同的军团，每个军团6名且分属6种不同的军阶．问能否将他们排成一个方阵，使得每行每列的6名军官正好来自6个不同军团? 正交拉丁方阵 拉丁方阵: 正交拉丁方阵:  地图四色问题 比如著名的世界难题“四色猜想” ：一张地图，用一种颜色对一个地区着色，那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。 组合数学的应用 组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科如计算机科学、编码和密码学、物理、化学、生物等学科中，甚至在企业管理，交通规划，战争指挥，金融分析，城市物流等领域均有重要应用。 组合数学的应用 著名的组合数学家 Thomas Tutte 在组合数学界是泰斗级的大师。直到最近人们才知道，原来他对提前结束“二战”有着突出贡献。 Tutte 从德军的两条情报密码出发，用组合数学的方法，重建了敌人的密码机，确定了德军密码的内部结构，从而获得了极为重要的情报。 组合数学的应用 在美国有一家公司用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。 在美国已有专门的公司用组合设计的方法开发软件，来解决工业界中的试验设计问题。 德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。 组合数学的应用 从A 地到E 地开车旅游。问应该选择什么路线，使总时间最短？ 第一讲: 引言、排列与组合 这一讲我们先介绍组合数学的研究对象，给出几个组合数学的典型问题, 然后学习排列与组合. 方法2： 设车的标号不妨用1,2,…,9来表示，它们的任何一个排列加上5个标志，便可准确地表达入口方案，如 1 2 | 3 | 4 5 | 6 | 7 8 | 9 1 | 2 3 | 4 | 5 6 | 7 | 8 9 从车的标志来说，都是1 2 3 4 5 6 7 8 9，但前者表示第1辆， 第2辆从第1入口处依次进场，第3辆从第2入口处进场等等； 后者表示第1辆从第1入口处进场，第2辆第3辆从第2入口处 依次进场等等 但5个标示符 |是没有区别的，若考虑14个元素的全排列，但有重复，其重复数是由于标识符|的排列，兑换相互位置对入场方案没有影响，故所求方案数为 N=14!/5! 上海火车站 上海市地图 * 某广场有6个入口处，每个入口处每次只能通过一辆汽车。有9辆要开进广场，试问有多少种入场方式? 解 方法1:第1辆车有6种选择方案,第2辆车可以有7种选择方案，这是因为当它选择与第1辆车相同的入口时，可以选择第1辆车在前的方案，还可以选择第1辆车在后的方案。第3辆车可以有8种方案，依此类推，可得 N=6x7x8x9x10x11x12x13x14=14!/5! 谢谢,再见! * * 问题3 36军官问题: 今有36名军官来自六个不同的团，具有六种不同的军阶，而且每个团每种军阶的军官各有一名，能否把他们排成一个6?6方阵，使得对每一个团与每一种军阶，在每一行或每一列都有一位军官来自这个团，也都有一位军官有此军阶？ * 如果每一个军官用一个有序对(i, j)来表示,其中i表示它们的军阶类别(i=1,?,6),而j表示他所在的团(j=1,2,?, 6),于是问题即要求将有序对(i, j) (i=1,2,?,6；j=1,2,?,6)排成一个6?6数组，使得每一行或每一列中整数1,2,?,6中任一数以某种次序出现于有序对的第一位置，又以另一种次序（不一定相同）出现于有序对的第二位置. * 可换一种方式考虑问题. 分别考虑军阶方阵与团队方阵, 于是问题就是是否存在两个6?6数组满足： (1) 每个数组中每一行或每一列中整数 1,2,?,6以某种次序出现; (2) 两个数组并置时, 所有的36个有序对 (i,j) (i=1,2,?,6; j=1,2,?,6)都将出现. 满足第一个条件的每个方阵称为拉丁方，满足第二个条件的两个拉丁方称