《前言组合数学概述.PPT》由会员分享，可在线阅读，更多相关《前言组合数学概述.PPT（60页珍藏版）》请在金锄头文库上搜索。
1、组合数学引论组合数学引论Introductory Combinatorics（第四版）（第四版）(美) Richard A . Brualdi 著 冯舜玺 罗平 裴伟东 译 卢开澄 冯舜玺 校 主讲教师： 李 向 军 2008年9月 于 南 昌 大 学1.第一章(Chapter 1)什么是组合数学?What is Combinatorics?2.组合数学概述组合数学概述n n现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等；另一类就是研究离散对象的组合数学。 n n计算机出现以后，由于离散对象的处理是计算机科学的核心，研究离散对象的组合数学得到迅猛发展。3.组合数学概述组合数学概述
2、n n吴文俊吴文俊院士指出：院士指出：“每个时代都有它特殊的要求，每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求分支，组合数学这个新的分支也是在时代的要求下产生的。下产生的。”，“信息技术很可能会给数学本身信息技术很可能会给数学本身带来一场根本性的变革，而组合数学则将显示出带来一场根本性的变革，而组合数学则将显示出它的重要作用。它的重要作用。” ” n nGian-Carlo RotaGian-Carlo Rota教授曾提出要向中国领导人呼吁，教授曾提出要向中国领导人呼吁，组合数学是计算机
3、软件产业的基础，中国最终一组合数学是计算机软件产业的基础，中国最终一定能成为一个软件大国，但是要实现这个目标的定能成为一个软件大国，但是要实现这个目标的一个突破点就是发展组合数学。一个突破点就是发展组合数学。 4. 组合数学是一个古老而又年轻的数学分支，据 传说，大禹在4000多年前就观察到了神龟背上的幻方。贾宪，北宋数学家（约11世纪）著有：黄帝九章细草、算法敩古集（又称“古算法导引” ），都已失传。杨辉著详解九章算法（1261年）中曾引贾宪的“开方作法本源图”（即指数为正数的二项式展开系数表 ， 现称“杨辉三角” ）和“增乘方法”（求高次幂的正根法）。前者比帕斯卡（Pascal）三角形早6
4、00年，后者比霍纳（William Geoge.Horner,1786-1837）的方法（1819年）早770年。组合数学的历史组合数学的历史5. 1666年莱布尼兹所著的组合数学论文一书问世，这是组合数学的第一部专著，书中首次使用了组合学（Combinatorics）一词。 组合数学于60年代以来迅速发展的原因有：一是计算机运行程序的算法中，运行时间效率和存储需求分析需要大量的组合数学思想；二是组合数学的思想和技巧不仅正在用于数学应用的传统自然科学领域，而且也越来越多地用于社会科学、生物科学、信息论等领域。 组合数学定义的一般描述：组合数学是研究离散结构的存在、计数、分析和优化等问题的一门科
5、学。组合数学的历史组合数学的历史6.我国古代的河洛图我国古代的河洛图(幻方幻方)问题问题n n传说在公元前传说在公元前2323世纪大禹世纪大禹治水的时候，在黄河支流治水的时候，在黄河支流洛水中，浮现出一个洛水中，浮现出一个 大乌大乌龟，甲上背有龟，甲上背有9 9种花点的图种花点的图案，人们将图案中的花点案，人们将图案中的花点数了一下，竞惊奇地发现数了一下，竞惊奇地发现9 9种花点数正巧是种花点数正巧是1 19 9这这9 9个个数，各数位置的排列也相数，各数位置的排列也相当奇妙，横的当奇妙，横的3 3行、纵的行、纵的3 3列以及两对角线上各自的列以及两对角线上各自的数字之和都为数字之和都为151
6、5。上图为三阶洛书7.幻方问题幻方问题n n组合数学中有许多象幻方这样精巧的结构。n n1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。神 农 幻 方2200BC 1 15 14 412 6 7 9 8 10 11 513 3 2 16 15世纪 阶 幻 方8.阿基米德手稿阿基米德手稿n n上图为一份用希腊文写在羊皮纸上的上图为一份用希腊文写在羊皮纸上的阿基米德阿基米德手稿副本手稿副本, ,最近科学家借助现代科技手段初步最近科学家借助现代科技手段初步破译了古希腊数学家阿基米德的这篇论文破译了古希腊数学家阿基米德的这篇论文, ,结结论是这篇被称作论是这篇被称作Stomac
7、hionStomachion的论文解决的是的论文解决的是组合数学问题。组合数学问题。 9.阿基米德手稿阿基米德手稿n n在论文中阿基米德是在计算把14条不规则的纸带拼成正方形一共能有多少种不同的拼法。这在现在被称为tiling问题。n n当今数学家借助计算机得出的答案是17152种拼法，这在当时是相当困难的。10.Periodic Tilings Non-Periodic TilingsPenrose Tilings Symmetric Tilings Symmetric Tilings 11.贾宪三角贾宪三角n n中国最早的组合数学中国最早的组合数学理论可追溯到宋朝时理论可追溯到宋朝时期的期
8、的” ”贾宪三角贾宪三角” ”, , 后后来被杨辉引用来被杨辉引用, , 所以普所以普遍称之为遍称之为” ”杨辉三角杨辉三角” ”, , 这在西方是这在西方是16541654年年由帕斯卡提出，但比由帕斯卡提出，但比中国晚了中国晚了400400多年。多年。11，11，2，11，3，3，11，4，6，4，11，5，10，10，5，11，6，15，20，15，6，112.七桥问题七桥问题n n近代图论的历史可追溯到近代图论的历史可追溯到1818世纪的世纪的七桥问题七桥问题穿过穿过KnigsbergKnigsberg城的七座桥，要求每座桥城的七座桥，要求每座桥通过一次且仅通过一次。通过一次且仅通过一次
9、。n nEulerEuler17361736年证明了不可能存在这样的路线。年证明了不可能存在这样的路线。13.Euler 定理定理n n如果一个图包含一条经过每条边恰好一次的闭途如果一个图包含一条经过每条边恰好一次的闭途径，则称这个图为径，则称这个图为欧拉图欧拉图。n n对任意的非空连通图，若它是对任意的非空连通图，若它是欧拉的欧拉的, ,当且仅当它当且仅当它没有奇度点。没有奇度点。KnigsbergKnigsberg桥对应的图桥对应的图14. 36 军官问题军官问题 (欧拉欧拉 1779) The Great Frederic的阅兵难题的阅兵难题-欧拉的困欧拉的困惑惑 拉丁方阵拉丁方阵:正交
10、拉丁方阵正交拉丁方阵:15.Euler 猜想猜想n n不存在6阶正交拉丁方n n不存在4k+2阶正交拉丁方现在的结论现在的结论n n对任正整数对任正整数 n2,6， 存在存在 n 阶正交拉丁方阶正交拉丁方16.组合数学的应用组合数学的应用n n组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科如计算机科学、编码和密码学、物理、化学、生物等学科中，甚至在企业管理，交通规划，战争指挥，金融分析，城市物流等领域均有重要应用。17.组合数学的应用组合数学的应用n n著名的组合数学家著名的组合数学家 Thomas Thomas TutteTutte 在组合数学界是泰斗在组合数学界是泰斗级的大师
11、。直到最近人们级的大师。直到最近人们才知道，原来他对提前结才知道，原来他对提前结束束“ “二战二战” ”有着突出贡献。有着突出贡献。n nTutteTutte 从德军的两条情报密从德军的两条情报密码出发，用组合数学的方码出发，用组合数学的方法，重建了敌人的密码机，法，重建了敌人的密码机，确定了德军密码的内部结确定了德军密码的内部结构，从而获得了极为重要构，从而获得了极为重要的情报。的情报。18.组合数学的应用组合数学的应用n n在美国有一家公司用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。n n在美国已有专门的公司用组合设计的方法开发软件，来解决工业界中的试验设计问题。n n德国
12、一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。 19.四色问题四色问题n n在日常生活中我们常常可以遇到组合数学的问题。在日常生活中我们常常可以遇到组合数学的问题。比如一个著名的世界难题比如一个著名的世界难题“ “四色猜想四色猜想” ” ：一张：一张地图，用一种颜色对一个地区着色，那么一共只地图，用一种颜色对一个地区着色，那么一共只需要四种颜色就能保证每两个相邻的地区颜色不需要四种颜色就能保证每两个相邻的地区颜色不同。同。20.四色问题四色问题n n18521852年，刚从伦敦大学毕业的年，刚从伦敦大学毕业的FrancisGuthrie提出了四
13、色猜想。提出了四色猜想。n n18781878年著名的英国数学家年著名的英国数学家Cayley向数学界征求向数学界征求解答。解答。n n此后数学家此后数学家 HeawoodHeawood 花费了毕生的精力致力于四花费了毕生的精力致力于四色研究，于色研究，于18901890年证明了五色定理（年证明了五色定理（每个平面图每个平面图都是都是5 5顶点可着色的顶点可着色的）。）。n n直到直到19761976年年6 6月，美国数学家月，美国数学家 K. AppelK. Appel与与 W. W. HakenHaken，在，在3 3台不同的电子计算机上，用了台不同的电子计算机上，用了12001200小小
14、时，才终于完成了时，才终于完成了“ “四色猜想四色猜想” ”的证明，从而使的证明，从而使 四色猜想四色猜想 成为了成为了四色定理四色定理。 21.中国邮递员问题中国邮递员问题n n1962年中国组合数学家管梅谷教授提出了著名的“中国邮递员问题”。n n一个邮递员从邮局出发，要走完他所管辖的每一条街道，然后返回邮局。那么如何选择一条尽可能短的路线。22.中国邮递员问题中国邮递员问题n n这个问题可以转化为：给定一个具有非负权的赋权图G，（1）用添加重复边的方法求G的一个Euler赋权母图G*，使得尽可能小。（2）求G*的Euler环游。n n这个问题可以由Fleury算法和1973年著名组合数学
15、家J.Edmonds和Johnson给出的一个好的算法解决。23.货郎担问题货郎担问题n n一个货郎要去若干城镇卖货，然后回到出发地，给定各城镇之间所需的旅行时间后，应怎样计划他的路线，使他能去每个城镇恰好一次而且总时间最短？24.货郎担问题货郎担问题n n用图论的术语说，就是在一个赋权完全图中，找出一个具有最小权的Hamilton圈（包含图G的每个顶点的圈)。n n这个问题目前还没有有效的算法。n nHamilton问题是图论的一个重要问题，图论中的许多问题，包括四色问题、图的因子问题，最终都与Hamilton问题有关。25.相识问题相识问题 n n1958年，美国的数学月刊上登载着这样一个
16、有趣的问题：“任何6个人的聚会，其中总会有3个人相互认识，或3个人相互不认识”。n n用6个顶点表示6个人，用红色连线表示两者相识，用蓝色连线表示两者不相识。于是问题化为下述命题：26.相识问题相识问题n n对6个顶点的完全图K6任意进行红、蓝两边着色，则图中一定存在一个同色三角形。27.Ramsey数数n n推广为一般问题：给定任意正整数a和b，总存在一个最小整数r(a,b)，使得r(a,b) 个人中或者有a 个人互相认识，或者有b 个人互相不认识。称r(a,b)为Ramsey数。28.Erds -Szekeres 定理定理 n nRamsey定理是由Erds和Szekeres于1935年提
17、出的。它是下述定理的一个推广：n n定理（Erds和Szekeres）：若a, b N，n=ab+1，且x1, , xn是任一n个实数的序列，则这个序列包含一个有a+1项的单调递增（递减）的子序列，或一个有b+1项的单调递减（递增）的子序列。29.Happy End 问题问题 n n对于对于n n33，处于平面上一般位置（任意三个顶点不共，处于平面上一般位置（任意三个顶点不共线）的线）的g(n)g(n)个顶点中，一定有个顶点中，一定有n n个顶点组成一个凸个顶点组成一个凸n n边边形。形。 5 5顶点一定含有一个凸四边形顶点一定含有一个凸四边形n nErdos Erdos 和和 Szekere
18、sSzekeres (1935) (1935) 证明了证明了 g g( (n n) ) 一定存在，并且一定存在，并且有有5个顶点时的情形30.机器证明机器证明吴消元法吴消元法n n1976年吴文俊教授开始进行研究几何定理的机器证明，并在很短的时间内取得重大突破。n n他的基本思想如下：引进坐标，将几何定理用代数方程组的形式表达；提出一套完整可行的符号解法，将此代数方程组求解。此两步中，一般第二步更为困难。31.机器证明机器证明吴消元法吴消元法n n周咸青周咸青利用并发展吴方法，编制出计算机软件，利用并发展吴方法，编制出计算机软件，证明了证明了500500多条有相当难度的几何定理，并在美多条有相
19、当难度的几何定理，并在美国出版了几何定理机器证明的专著。国出版了几何定理机器证明的专著。n n吴方法不仅可证明已有的几何定理，而且可以自吴方法不仅可证明已有的几何定理，而且可以自动发现新的定理。可以从动发现新的定理。可以从KerlerKerler定律推导牛顿定定律推导牛顿定律；解决一些非线性规划问题；给出律；解决一些非线性规划问题；给出PumaPuma型机型机器人的逆运动方程的解。器人的逆运动方程的解。n n吴文俊教授还将其方法推广到微分几何定理的机吴文俊教授还将其方法推广到微分几何定理的机器证明上。器证明上。32.网络流问题网络流问题n n随着中国经济快速的增长，城市化是未来中国的随着中国经
20、济快速的增长，城市化是未来中国的发展方向。人大通过的发展方向。人大通过的“ “十五十五” ”规划，把物流业规划，把物流业作为战略重点列入要大力发展的新兴服务产业。作为战略重点列入要大力发展的新兴服务产业。如何制定一个运输计划使生产地到销售地的产品如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。输送量最大。这就是一个网络最大流问题。 33.网络流问题网络流问题n n19561956年年FordFord和和FulkersonFulkerson提出了关于网络流问题提出了关于网络流问题的一个重要定理。的一个重要定理。n n最大流最小割定理最大流最小割定理：在任何网络中，
21、最大流的值：在任何网络中，最大流的值等于最小割的容量。等于最小割的容量。n n由这个定理可以引出求网络最大流的一个算法由这个定理可以引出求网络最大流的一个算法标号法标号法。n n19701970年，年，EdmondsEdmonds和和KarpKarp 对标号程序加以改进，对标号程序加以改进，使之成为一个好的算法使之成为一个好的算法。34.稳定的婚姻问题稳定的婚姻问题n n 组合数学中有一个著名定理：如果一个村子里每一个女组合数学中有一个著名定理：如果一个村子里每一个女孩都恰好认识孩都恰好认识k k个男孩，并且每一个男孩也恰好认识个男孩，并且每一个男孩也恰好认识k k个个女孩，那么每一个女孩都可
22、以嫁给她认识的一个男孩，女孩，那么每一个女孩都可以嫁给她认识的一个男孩，并且每一个男孩都可以娶一个他认识的女孩。（并且每一个男孩都可以娶一个他认识的女孩。（ k k 正则正则二部图，一定存在一个完美匹配二部图，一定存在一个完美匹配）35.稳定的婚姻问题稳定的婚姻问题n n但是这样的安排方法不一定是最好的。假如能找到两对夫妇，彼此都更喜欢对方的配偶，那么这样婚姻有潜在的不稳定性。n n用图论匹配理论中Gale-Shapley算法，可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现。36.稳定的婚姻问题稳定的婚姻问题n n这种组合数学的方法有这种组合数学的方法有 一个实际的用途：美国的一个实
23、际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请者排序。按这的志愿的先后次序，同时也给申请者排序。按这样的样的 次序考虑出的总的方案将没有医院和申请者次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。两者同时后悔的情况。 实际上，高考学生的最后录取方案也可以用实际上，高考学生的最后录取方案也可以用这种方法。这种方法。37.栈排序问题栈排序问题(Knuth, 1960s)n n模式:对任意一个排列,最小的元素用代替，次小的元素用代替以此类推，这样得到的排列叫的模式。n n例如914的模式为：31237925
24、的模式为：2451338.栈排序问题栈排序问题(Knuth, 1960s)n n避免排列：一个排列是避免的，当且仅当它的任意子序列中没有模式。n n例如132564是避免312的排列146235是包含312的排列39.栈排序问题栈排序问题(Knuth, 1960s)87654321避免312排列40.全一问题全一问题n n 假设博物馆里有若干个房间，每个房间里有一盏灯和一个开关，每次按下某个房间的开关，可以改变这个房间以及它相邻的房间的灯的状态。41.全一问题全一问题n n问是否可以找到一种开灯的方案，使得所有房间的灯由全亮变为全灭？这就是Sutner于1989年提出的“全一问题”（All-O
25、nesProblem)。42.最小全一问题最小全一问题n n求操作次数最少的解称为求操作次数最少的解称为最小全一问题最小全一问题。n n我们已经知道，对于一般图上的最小全一问题是我们已经知道，对于一般图上的最小全一问题是NPNP完备的。完备的。n n陈永川陈永川教授与他人合作找到了一个线性时间算法，教授与他人合作找到了一个线性时间算法，很好地解决了树和单圈图的最小全一问题。很好地解决了树和单圈图的最小全一问题。（SIAMJournalonComputingSIAMJournalonComputing，20042004）43.网络可靠性问题网络可靠性问题n n一个通讯网络怎样布局稳定性最好，而且
26、费用最节省？n n美国的贝尔实验室和IBM公司都有世界一流的组合数学家在研究这个问题，这个问题直接关系到巨大的经济利益。44.最短网络问题最短网络问题n n如何用最短的线路将三部电话连起来？如何用最短的线路将三部电话连起来？n n此问题可抽象为设此问题可抽象为设ABCABC为等边三角形，连接三顶点的为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如显然是二边之和（如ABABACAC）。）。ABC45.最短网络问题最短网络问题n n但若增加一个周转站（新点但若增加一个周转站（新点P P），连接，连接4
27、4点的新网络的最点的新网络的最短路线为短路线为PAPAPBPBPCPC。最短新路径之长。最短新路径之长N N比原来只连三比原来只连三点的最短路径点的最短路径OO要短。要短。n n这样得到的网络不仅比原来节省材料，而且稳定性也更这样得到的网络不仅比原来节省材料，而且稳定性也更好。好。 ABCP46.PollakGilbert猜想猜想n n由于最短网络在运输、通讯和计算机等现代经济与科技领域中都有重要的应用，对这个问题的研究也越来越深入。问题的对象已由三个点扩展到任意有限个点集。47.PollakGilbert猜想猜想n n斯坦纳（斯坦纳（SteinerSteiner）最小树）最小树是可以在给定的
28、点之外再增加若干个点(称为斯坦纳点斯坦纳点)，然后将所有这些点连起来。n n如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树最小生成树。n n在前面的例子中Steiner最小树的长为 而最小生成树的长为2。48.PollakGilbert猜想猜想n n1968年贝尔实验室数学中心主任波雷克(Pollak)和研究员吉尔伯特(Gilbert)提出如下猜想：n n平面上任意n点集，斯坦纳最小树长与最小生成树之长的比值的最小值是 。 n n这个猜想又被称为斯坦纳比猜想斯坦纳比猜想。49.PollakGilbert猜想猜想n nPollakPollakGilbertGilbert猜想
29、猜想起源于在美国贝尔电话公司起源于在美国贝尔电话公司发生的一个富有戏剧性的事件。发生的一个富有戏剧性的事件。n n19671967年前，贝尔公司按照连结各分部的最小生成年前，贝尔公司按照连结各分部的最小生成树的长度来收费。树的长度来收费。19671967年一家航空公司戳了贝尔年一家航空公司戳了贝尔公司一个大洞。当时这家企业申请要求贝尔公司公司一个大洞。当时这家企业申请要求贝尔公司增加一些服务点，而这些服务点恰恰位于构造该增加一些服务点，而这些服务点恰恰位于构造该公司各分部的斯坦纳最小树需增加的斯坦纳顶点公司各分部的斯坦纳最小树需增加的斯坦纳顶点上。这使得贝尔公司不仅要拉新线，增加服务网上。这使
30、得贝尔公司不仅要拉新线，增加服务网点，而且还要减少收费。这一意外事件迫使贝尔点，而且还要减少收费。这一意外事件迫使贝尔公司自此以后便采用了斯坦纳最小树原则公司自此以后便采用了斯坦纳最小树原则 。50.PollakGilbert猜想猜想n n19901990年，中科院应用数学所研究员年，中科院应用数学所研究员堵丁柱堵丁柱与美籍与美籍华人华人黄光明黄光明合作，证明了合作，证明了PollakPollakGilbertGilbert猜想猜想。在美国离散数学界引起轰动，被列为在美国离散数学界引起轰动，被列为1989198919901990年度美国离散数学界与理论计算机科学界的年度美国离散数学界与理论计算
31、机科学界的两项重大成果之一。两项重大成果之一。 n n在在不列颠百科全书不列颠百科全书19921992年鉴年鉴的数学评论中，的数学评论中，该成果被列为世界上当年六项数学成果首项。该成果被列为世界上当年六项数学成果首项。n n该成果被我国列为该成果被我国列为19921992年十大科技成就之一。年十大科技成就之一。 51.无尺度网络无尺度网络n n2020世纪世纪2020年代，由年代，由KarinthyKarinthy提出。提出。n n19501950年，年， PoolPool 和和 KochenKochen提出这样一个问题：提出这样一个问题：“ “两个毫无关系的人，要让他们互相认识，至少要两个毫
32、无关系的人，要让他们互相认识，至少要经过多少人？经过多少人？” ”n n美国哈佛大学社会心理学家美国哈佛大学社会心理学家S.MilgramS.Milgram在在19671967年年做过一项有趣的实验，据说他从内布拉斯加州的做过一项有趣的实验，据说他从内布拉斯加州的奥马哈随机选了奥马哈随机选了300300人，然后请他们每个人尝试寄人，然后请他们每个人尝试寄一封信到波士顿的一位证券业务员。寄信的规则一封信到波士顿的一位证券业务员。寄信的规则很简单，就是任何收信者只能把信寄给自己熟识很简单，就是任何收信者只能把信寄给自己熟识的人。的人。 52.重要结论重要结论n n“6度分离”对每个人来说，平均大约
33、只需要通过个人就能将信寄到目的地。n n研究无尺度网络，对于防备黑客攻击、防治流行病、和开发新药等，都具有重要的意义。n n在1999年，Barabasietal.发现在因特网上，任意两个网页间的链接最多为19次。(Nature401,1999)53.无尺度网络的一个例子无尺度网络的一个例子n n因特网是一个无尺度因特网是一个无尺度网络，左图的星爆形网络，左图的星爆形结构描绘了从某一测结构描绘了从某一测试站点到其他约十万试站点到其他约十万个站点的最短连结路个站点的最短连结路径。图中以相同的颜径。图中以相同的颜色来表示相类似的站色来表示相类似的站点。点。54.Szemerdi 定理定理n n若k
34、 为一个正整数并且0，则存在一个正整数 N = N(k,) ，使得集合1，2，N的每一个N 长的子集都包含 k 长的等差级数。n nN(k,) 有一个很有名的界55.Szemerdi 定理定理n n其中下界是由Behrend（对k=3的情形）和Rankin给出的，上界是由W.TimothyGowers给出的。n nGowers因为给出了这个上界而获得了1998年的Fields奖。56.生物数学生物数学n n目前，计算生物学、基因理论、生物信息学都是最前沿的研究领域。n n随着人类基因组计划的完成和其他基因计划的完成，所有公认的和潜在的蛋白质元都可以被确定，通过大规模的实验技术，可以生成大量的生
35、物学数据。57.生物数学生物数学n n如何处理这些数据来获得生物学的信息，这里如何处理这些数据来获得生物学的信息，这里组组合数学和随机图论都起到了关键的作用。合数学和随机图论都起到了关键的作用。n n如果将基因看作网络中的顶点，将他们之间的作如果将基因看作网络中的顶点，将他们之间的作用看作网络中的边，那么每一次大规模实验将给用看作网络中的边，那么每一次大规模实验将给我们带来关于基因交互作用网络的一些信息。这我们带来关于基因交互作用网络的一些信息。这个网络的拓扑性质是科学家们关心的焦点（如每个网络的拓扑性质是科学家们关心的焦点（如每一个顶点的度和网络中的最小距离问题是两个初一个顶点的度和网络中的
36、最小距离问题是两个初步的问题）。步的问题）。 58.生物信息学生物信息学n n组合数学和概率统计在生物信息学中有重要应用。n n美国科学院院士MichaelWaterman教授，曾鼓励我们借助组合数学的优势，开展生物信息学的研究。n n天津大学张春霆院士和北京师范大学王梓坤院士，北京大学钱敏平教授，南开大学沈世镒教授，59.课程主要内容课程主要内容 n n鸽巢原理和Ramsey定理n n组合数学基本计数法（排列与组合、生成排列和组合、二项式系数、特殊计数序列）n n容斥原理及应用n n生成函数与递归关系n nPolya计数法（Burnside定理和Polya计数公式）n n有向图及网络n n组合设计本章练习题书P13页：1，3，6，11，14，16，60.
