组合数学的鼻祖.ppt
《组合数学的鼻祖.ppt》由会员分享,可在线阅读,更多相关《组合数学的鼻祖.ppt(48页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、图论与网络,1,数学的内容、方法与意义,组合数学概述,现代数学可以分为两大类:一类是研究连续对象的,如分析、方程等;另一类就是研究离散对象的组合数学。 计算机出现以后,由于离散对象的处理是计算机科学的核心,研究离散对象的组合数学得到迅猛发展。图论是组合数学的一个重要分支,也是最活跃的一个分支。,2,近代图论的历史可追溯到18世纪的七桥问题穿过Knigsberg城的七座桥,要求每座桥通过一次且仅通过一次。Euler1736年证明了不可能存在这样的路线。,如果一个图包含一条经过每条边恰好一次的闭途径,则称这个图为欧拉图。对任意的非空连通图,若它是欧拉的, 当且仅当它没有奇度点。,公认的第一个图论问
2、题,3,图的定义和基本术语,1. 图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为: G=(V,E)其中:G表示一个图,V是图G中顶点的集合,E是图G中顶点之间边的集合。,4,旅行售货员问题,对一般图,我们就叫Hamilton圈;如果图的每条边上赋一个权值,就叫旅行售货员问题,即TSP. 大家如果用Google搜索一下“TSP”,获得约 86,500,000 条结果 (用时 0.06 秒),四色问题,在日常生活中我们常常可以遇到组合数学的问题。比如一个著名的世界难题“四色猜想” :一张地图,用一种颜色对一个地区着色,那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。,平面图和四
3、色问题,中国邮递员问题,1962年中国组合数学家管梅谷教授提出了著名的“中国邮递员问题”。一个邮递员从邮局出发,要走完他所管辖的每一条街道,然后返回邮局。那么如何选择一条尽可能短的路线。物流系统、多邮局多邮递员问题,相识问题,1958年,美国的数学月刊上登载着这样一个有趣的问题:“任何6个人的聚会,其中总会有3个人相互认识,或3个人相互不认识”。用6个顶点表示6个人,用红色连线表示两者相识,用蓝色连线表示两者不相识。于是问题化为下述命题:,相识问题,对6个顶点的完全图K6任意进行红、蓝两边着色,则图中一定存在一个同色三角形。,Ramsey数,推广为一般问题:给定任意正整数a和b,总存在一个最小
4、整数 r(a,b),使得r(a,b) 个人中或者有 a 个人互相认识,或者有 b 个人互相不认识。称 r(a,b) 为Ramsey数。,稳定的婚姻问题,组合数学中有一个著名定理:如果一个村子里每一个女孩都恰好认识k个男孩,并且每一个男孩也恰好认识k个女孩,那么每一个女孩都可以嫁给她认识的一个男孩,并且每一个男孩都可以娶一个他认识的女孩。( k 正则二部图,一定存在一个完美匹配),稳定的婚姻问题,但是这样的安排方法不一定是最好的。假如能找到两对夫妇,彼此都更喜欢对方的配偶,那么这样婚姻有潜在的不稳定性。用图论匹配理论中Gale-Shapley算法,可以找到一种婚姻的安排方法,使得没有上述的不稳定
5、情况出现。,图论,图论是一个应用十分广泛而又极其有趣的学分支物理、化学、生物、科学管理、计算机等各个领域都可以找到图论的足迹 图论与数学的其他分支如群论、矩阵论、概率论,拓扑、数值分析、组合数学等都有着密切的驻系 基本图论的几个研究方向:图的染色理论:如点染色、边染色、全染色等;图的因子理论:完美匹配、( g, f )因子等;图的控制理论:点控制,完全控制等;图的圈理论:Hamilton圈,围长、周长、圈分解等;图的剖分理论:点或边剖分。,14,复杂网络研究的新纪元,20世纪60年代以来,随机图理论在将近40年的时间里一直是研究复杂网络结构的基本理论,但绝大多数实际的复杂网络结构并不是完全随机
6、的。 在20世纪即将结束之际,对复杂网络的科学探索发生了重要的转变,复杂网络理论研究也不再局限于数学领域。人们开始考虑节点数量众多、连接结构复杂的实际网络的整体特性,在从数学、物理学到生物学的众多学科中掀起了研究复杂网络的热潮,甚至于被称为“网络的新科学” 。,15,推荐书: 1) 链接网络新科学 2) 网络战争,复杂网络研究的新纪元,有两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志:一篇是美国康奈尔大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的题为“小世界”网络的集体动力学(Collective dyna
7、mic of “Small-World” Networks, 1998, 393(6684): 440-442)的文章;另一篇是美国Notre Dame大学物理系的Barabasi教授及其博士生Albert于1999年10月在Science杂志上发表的题为随机网络中标度的涌现(Emergence of Scaling in Random Networks,Science, 1999, 286(5439):509-512)的文章。这两篇文章分别揭示了复杂网络的小世界特征和无标度性质,并建立了相应的模型以阐述这些特性的产生机理。推荐书 1)小小世界:有序与无序之间的网络动力学 2) 复杂网络(郭雷
8、等著),16,Nature上的一篇文章,“小世界”网络的集体动力学,Nature上的一篇文章,“小世界”网络的集体动力学,Science上的一篇文章,随机网络中标度的涌现,中国人引文次数的最高记录,1. 美国(近十年论文总引用次数46,796,090)论文:ANALYSIS OF RELATIVE GENE EXPRESSION DATA USING REAL-TIME QUANTITATIVE PCR AND THE 2(T)(-DELTA DELTA C) METHO 被引次数:9,252领域:生物学与生物化学发表期刊:方法学(METHODS),8. 中国(近十年论文总引用数4,227,7
9、79)论文:CORONAVIRUS AS A POSSIBLE CAUSE OF SEVERE ACUTE RESPIRATORY SYNDROME被引次数:1,025领域:临床医学发表期刊:柳叶刀(THE LANCET),中国人引文次数的最高记录,王振义院士的Blood上牛文,1988年发表以来,已被引用1538次(Web of Science 数据),被引用次数:1256,彭实戈院士的论文,听说是历史上最牛的文章,PROTEIN MEASUREMENT WITH THE FOLIN PHENOL REAGENT, LOWRY, OH; ROSEBROUGH, NJ; FARR, AL, e
10、t al. JOURNAL OF BIOLOGICAL CHEMISTRY 193:1(1951) 265-275.该文的第一作者为 Oliver Howe Lowry (19101996) ,著名的Lowry蛋白定量法就是以此人的姓来命名的,上述论文也是Lowry蛋白定量法的理论基础,该文发表60年后该方法仍被全世界广泛应用。该文章发表时,Oliver Howe Lowry时任为位于美国圣路易斯的华盛顿大学(Washington University in St. Louis)的药理系的系主任。并与1955年到1958年间任该校的医学院院长。 Oliver Howe Lowry于1964年被
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 数学 鼻祖 开山祖师
限制150内