图论与网络 1数学的内容、方法与意义

组合数学概述 现代数学可以分为两大类：一类是研究连 续对象的，如分析、方程等；另一类就是 研究离散对象的组合数学。 现代数学可以分为两大类：一类是研究连 续对象的，如分析、方程等；另一类就是 研究离散对象的组合数学。 计算机出现以后，由于离散对象的处理是 计算机科学的核心，研究离散对象的组合 数学得到迅猛发展。 计算机出现以后，由于离散对象的处理是 计算机科学的核心，研究离散对象的组合 数学得到迅猛发展。 图论是组合数学的一个重要分支，也是最 活跃的一个分支。 图论是组合数学的一个重要分支，也是最 活跃的一个分支。 2

 近代图论的历史可追溯到 18 世纪的七桥问题 — 穿过 Königsberg 城 的七座桥，要求每座桥通过一次且仅通过一次。  Euler1736 年证明了不可能存在这样的路线。  如果一个图包含一条经过每条边恰好一次的闭途径，则称这个图 为欧拉图。  对任意的非空连通图，若它是欧拉的, 当且仅当它没有奇度点。 公认的第一个图论问题 3

图的定义和基本术语 1. 图是由顶点的有穷非空集合和顶点之间边的集 合组成，通常表示为： G= ( V ， E ) 其中： G 表示一个图， V 是图 G 中顶点的集合， E 是图 G 中顶点之间边的集合。 4

旅行售货员问题 对一般图, 我们就叫 Hamilton 圈 ; 如果图的每条边上赋一 个权值, 就叫旅行售货员问题, 即 TSP. 对一般图, 我们就叫 Hamilton 圈 ; 如果图的每条边上赋一 个权值, 就叫旅行售货员问题, 即 TSP. 大家如果用 Google 搜索一下 “TSP” ，获得约 86,500,000 条结果 （用时 0.06 秒） 大家如果用 Google 搜索一下 “TSP” ，获得约 86,500,000 条结果 （用时 0.06 秒）

四色问题 在日常生活中我们常常可以遇到组合数学的问题。 比如一个著名的世界难题 “ 四色猜想 ” ：一张地图， 用一种颜色对一个地区着色，那么一共只需要四 种颜色就能保证每两个相邻的地区颜色不同。 在日常生活中我们常常可以遇到组合数学的问题。 比如一个著名的世界难题 “ 四色猜想 ” ：一张地图， 用一种颜色对一个地区着色，那么一共只需要四 种颜色就能保证每两个相邻的地区颜色不同。

平面图和四色问题

中国邮递员问题 1962 年中国组合数学家管梅谷教授提出了著 名的 “ 中国邮递员问题 ” 。 1962 年中国组合数学家管梅谷教授提出了著 名的 “ 中国邮递员问题 ” 。 一个邮递员从邮局出发，要走完他所管辖 的每一条街道，然后返回邮局。那么如何 选择一条尽可能短的路线。 一个邮递员从邮局出发，要走完他所管辖 的每一条街道，然后返回邮局。那么如何 选择一条尽可能短的路线。 物流系统、多邮局多邮递员问题 物流系统、多邮局多邮递员问题

相识问题 1958 年，美国的《数学月刊》上登载着这样 一个有趣的问题： “ 任何 6 个人的聚会，其中 总会有 3 个人相互认识，或 3 个人相互不认 识 ” 。 1958 年，美国的《数学月刊》上登载着这样 一个有趣的问题： “ 任何 6 个人的聚会，其中 总会有 3 个人相互认识，或 3 个人相互不认 识 ” 。 用 6 个顶点表示 6 个人，用红色连线表示两 者相识，用蓝色连线表示两者不相识。于 是问题化为下述命题： 用 6 个顶点表示 6 个人，用红色连线表示两 者相识，用蓝色连线表示两者不相识。于 是问题化为下述命题：

相识问题 对 6 个顶点的完全图 K 6 任意进行红、蓝两边 着色，则图中一定存在一个同色三角形。 对 6 个顶点的完全图 K 6 任意进行红、蓝两边 着色，则图中一定存在一个同色三角形。

Ramsey 数 推广为一般问题：给定任意正整数 a 和 b ， 总存在一个最小整数 r(a,b) ，使得 r(a,b) 个人中或者有 a 个人互相认识，或者 有 b 个人互相不认识。称 r(a,b) 为 Ramsey 数。 推广为一般问题：给定任意正整数 a 和 b ， 总存在一个最小整数 r(a,b) ，使得 r(a,b) 个人中或者有 a 个人互相认识，或者 有 b 个人互相不认识。称 r(a,b) 为 Ramsey 数。

稳定的婚姻问题 组合数学中有一个著名定理：如果一个村子里每一个 女孩都恰好认识 k 个男孩，并且每一个男孩也恰好认识 k 个女孩，那么每一个女孩都可以嫁给她认识的一个男 孩，并且每一个男孩都可以娶一个他认识的女孩。（ k 正则二部图，一定存在一个完美匹配）

稳定的婚姻问题 但是这样的安排方法不一定是最好的。假 如能找到两对夫妇，彼此都更喜欢对方的 配偶，那么这样婚姻有潜在的不稳定性。 但是这样的安排方法不一定是最好的。假 如能找到两对夫妇，彼此都更喜欢对方的 配偶，那么这样婚姻有潜在的不稳定性。 用图论匹配理论中 Gale-Shapley 算法，可 以找到一种婚姻的安排方法，使得没有上 述的不稳定情况出现。 用图论匹配理论中 Gale-Shapley 算法，可 以找到一种婚姻的安排方法，使得没有上 述的不稳定情况出现。

图论 图论是一个应用十分广泛而又极其有趣的学分支．物理、 化学、生物、科学管理、计算机等各个领域都可以找到图论 的足迹． 图论是一个应用十分广泛而又极其有趣的学分支．物理、 化学、生物、科学管理、计算机等各个领域都可以找到图论 的足迹． 图论与数学的其他分支如群论、矩阵论、概率论，拓扑、 数值分析、组合数学等都有着密切的驻系． 图论与数学的其他分支如群论、矩阵论、概率论，拓扑、 数值分析、组合数学等都有着密切的驻系． 基本图论的几个研究方向 : 基本图论的几个研究方向 : 1. 图的染色理论 : 如点染色、边染色、全染色等； 2. 图的因子理论：完美匹配、 ( g, f )— 因子等； 3. 图的控制理论：点控制，完全控制等； 4. 图的圈理论： Hamilton 圈，围长、周长、圈分解等； 5. 图的剖分理论：点或边剖分。 14

复杂网络研究的新纪元 20 世纪 60 年代以来，随机图理论在将近 40 年的时 间里一直是研究复杂网络结构的基本理论，但绝大 多数实际的复杂网络结构并不是完全随机的。 20 世纪 60 年代以来，随机图理论在将近 40 年的时 间里一直是研究复杂网络结构的基本理论，但绝大 多数实际的复杂网络结构并不是完全随机的。 在 20 世纪即将结束之际，对复杂网络的科学探索 发生了重要的转变，复杂网络理论研究也不再局限 于数学领域。人们开始考虑节点数量众多、连接结 构复杂的实际网络的整体特性，在从数学、物理学 到生物学的众多学科中掀起了研究复杂网络的热潮， 甚至于被称为 “ 网络的新科学 ” 。 在 20 世纪即将结束之际，对复杂网络的科学探索 发生了重要的转变，复杂网络理论研究也不再局限 于数学领域。人们开始考虑节点数量众多、连接结 构复杂的实际网络的整体特性，在从数学、物理学 到生物学的众多学科中掀起了研究复杂网络的热潮， 甚至于被称为 “ 网络的新科学 ” 。 15 推荐书 : 1) 链接 · 网络新科学 2) 网络战争 2) 网络战争

复杂网络研究的新纪元 有两篇开创性的文章可以看作是复杂网络研究新纪元开始 的标志：一篇是美国康奈尔大学理论和应用力学系的博士生 Watts 及其导师、非线性动力学专家 Strogatz 教授于 1998 年 6 月 在 Nature 杂志上发表的题为《 “ 小世界 ” 网络的集体动力学》 有两篇开创性的文章可以看作是复杂网络研究新纪元开始 的标志：一篇是美国康奈尔大学理论和应用力学系的博士生 Watts 及其导师、非线性动力学专家 Strogatz 教授于 1998 年 6 月 在 Nature 杂志上发表的题为《 “ 小世界 ” 网络的集体动力学》 (Collective dynamic of “Small-World” Networks, 1998, 393(6684): ) 的文章；另一篇是美国 Notre Dame 大学物理系的 Barabasi 教授及其博士生 Albert 于 1999 年 10 月在 Science 杂志上 发表的题为《随机网络中标度的涌现》 (Emergence of Scaling in Random Networks ， Science, 1999, 286(5439): ) 的文章。 这两篇文章分别揭示了复杂网络的小世界特征和无标度性质， 并建立了相应的模型以阐述这些特性的产生机理。 推荐书 1 ）小小世界：有序与无序之间的网络动力学 推荐书 1 ）小小世界：有序与无序之间的网络动力学 2) 复杂网络（郭雷等著） 2) 复杂网络（郭雷等著） 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,779 ） 论文： 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, et al. JOURNAL OF BIOLOGICAL CHEMISTRY 193:1(1951) 该文的第一作者为 Oliver Howe Lowry (1910–1996) ，著名的 Lowry 蛋白定量 法就是以此人的姓来命名的，上述论文也是 Lowry 蛋白定量法的理论基础 ，该文发表 60 年后该方法仍被全世界广泛应用。该文章发表时， Oliver Howe Lowry 时任为位于美国圣路易斯的华盛顿大学（ Washington University in St. Louis ）的药理系的系主任。并与 1955 年到 1958 年间任该校的医学院院 长。 Oliver Howe Lowry 于 1964 年被选为美国科学院院士。但 Lowry 终生并没 有由于该方法的巨大贡献而获诺贝尔奖 被引用次数：

几篇与网络有关的论文的引用次数

几篇与网络有关的论文的引用次数 Statistical mechanics of complex networks, R Albert … - Reviews of modern physics, 2002, 被引用次数： 9131 The structure and function of complex networks, J Newman - SIAM review, 2003,- 被引用次数： 6475 Error and attack tolerance of complex networks, R Albert, H Jeong … - Nature, 2000 被引用次数： 2619 Exploring complex networks, SH Strogatz - Nature, 2001 被引用次数： 3465 Network motifs: simple building blocks of complex networks, R Milo, S Shen-Orr, S Itzkovitz, N Kashtan … - Science, 2002 被引用次数： 2281 Emergence of scaling in complex networks, AL Barab á si - Handbook of graphs and networks, 1999 被引用次数： 2123 Complex networks: Structure and dynamics, S Boccaletti, V Latora, Y Moreno, M Chavez … - Physics reports, 2006 被引用次数： 2475 Uncovering the overlapping community structure of complex networks in nature and society, G Palla, I Der é nyi, I Farkas … - 被引用次数： 1169 Hierarchical organization in complex networks, E Ravasz … - Physical Review E, 被引用次数： 890

复杂网络的研究统计 SCI papers: Small-World Networks

复杂网络的研究统计 27 EI papers ： Scale-Free Networks

现实生活中无处不存在着复杂网络 28 互联网

现实生活中无处不存在着复杂网络 29 互联网

现实生活中无处不存在着复杂网络 互联网 互联网 交通网 交通网 电网 电网 水网 水网 广播电视网 广播电视网 通讯网 通讯网 社会关系网 社会关系网 交通网 30

现实生活中无处不存在着复杂网络 交通网 31

现实生活中无处不存在着复杂网络 通信网 32

现实生活中无处不存在着复杂网络 社会关系网 33

现实生活中无处不存在着复杂网络 京城四少关系图 34

现实生活中无处不存在着复杂网络 电网 35

现实生活中无处不存在着复杂网络 大规模集成电路 36

科学研究中也存在许多复杂网络 Global organization of metabolic fluxes in the bacterium Escherichia coli, NATURE |VOL 427 | 26 FEBRUARY 2004 |

科学研究中也存在许多复杂网络 38

科学研究中也存在许多复杂网络

科学研究中也存在许多复杂网络

基因调控网络 基因调控网络

Protein 3D Structure Detection X-ray diffraction X- 射线衍射法 Expensive Slow

你知道如下问题吗 ?  地球上任意两个人之间要通过多少个朋友才能互相认识 ?  万维网 (WWW) 上从一个页面到另一个页面平均需要点击 多少次鼠标 ?  层出不穷的计算机病毒是如何在互联网 (internet) 上传播 的 ?  各种传染病 ( 艾滋病、非典型性肺炎和禽流感等 ) 是如何 在人类和动物中流行的 ?  应该如何建立合理的公共卫生与安全网络 ?  为什么流言蜚语会散布得很快 ?  全球或地区性金融危机是如何发生的 ?  局部故障是如何触发大面积停电事故的 ?  大城市的交通堵塞问题是如何引起的 ?  为什么大脑能够具有思维的功能 ?  将来的交通工具还需要自己来驾驶吗？ 43

一个社会网络就是一群人或团体按 某种关系连接在一起而构成的一个系统。 这里的关系可以多种多样，如个人之间 的朋友关系、同事之间的合作关系、家 庭之间的联姻关系和公司之间的商业关 系等等。右图反映的就是澳大利亚堪培 拉的一个社会关系网络。以朋友关系为 例，很多人可能都有这样的经历：偶尔 碰到一个陌生人，同他聊了一会儿后发 现你认识的某个人居然他也认识，然后 一起发出 “ 这个世界真小 ” 的感叹。那么 对于地球上任意两个人来说，借助第三 者、第四者这样的间接关系来建立起他 们两人的联系，平均需要通过多少人 呢 ?20 世纪 60 年代美国哈佛大学的社会 心理学家 Stanley Milgram 通过一些社会 调查后给出的推断是：地球上任意两个 人之间的平均距离是 6 。也就是说，平 均中间只要通过 5 个人，你就能与地球 上任何一个角落的任何一个人发生联系。 六度分离推断 (Six degrees of separation) 44

世界上任何两台计算机至多通过四台服务器就可以连通 ! 45

 如果把人的电子邮件地址作为一个点, 两个 有联系的人的地址联一条边 ( 电邮地址簿 ), 则 这个图的直径为 4, 即任何两点的距离至多为 4.  根据计算机病毒传播的途径和方法不一样, 网络拓扑结构也是有变化的.  复杂网络上的传播机理和动力学分析 -- 各种传染病 ( 艾滋病、非典型性肺炎和禽流感等 ) 是如何在 人类和动物中流行的 ? -- 为什么流言蜚语会散布得很快 ? 46

20 世纪 60 年代末，哈佛大学的研究生 Mark Granovetter 带着这些问 题，开始了他的研究课题。他在波士顿地区采访了近 100 个人，并向 200 多个人发出了问卷。这些被调查者，要么刚刚改变了工作，要么最近才 被雇佣，而且都是专业技术人士，也就是说，他的调查范围不包括蓝领 工人。 Granovetter 发现，人们在找寻工作时，那些关系紧密的朋友 ( 强连 接 ) 反倒没有那些关系一般的甚至只是偶尔见面的朋友 ( 弱连接 ) 更能够发 挥作用。事实上，关系紧密的朋友也许根本帮不上忙。下面是 Granovetter 论文中给出的一个例子，类似的例子在我们身边也非常多， 例如： Edward 在上高中的时候，他认识的一个女孩邀请他参加了一个 聚会。在聚会上， Edward 遇到了比他大十岁的那个女孩的大姐的男朋友 。三年以后，当 Edward 辞去了工作后，他在当地的住所偶遇到了这位只 有一面之交的朋友。在交谈中，这个人提起说他所在的公司现在需要一 个制图员，于是 Edward 申请了这个工作，并顺利地被聘用了。 Granovetter 的这篇标题为《弱连接的强度》 (The Strength of Weak Ties) 的论文最初于 1969 年 8 月投给了《美国社会学评论》杂志，但 4 个月后就 被退稿。四年之后，这篇论文才在《美国社会学》杂志发表。现在它已 被认为是有史以来最有影响的社会学论文之一。

 网络的小世界性：尽管网络很大，但是任意两人之间的平 均距离却惊人的小。  网络的可搜索性：尽管链接两个人的路径的数目可能很大 且不同路径的长度差异也可能很大，但是人们是有可能找 到链接自己与某个陌生人之间的较短路径的 ( 见：《 “ 小世 界 ” 网络的集体动力学》 ) 。  Watts(Identity and search in social networks, Science, 2002,296: ) 对社会网络作了进一步的研究。  社会网络搜索： Kleinbeig 网格搜索、层次树结构网络模型  搜索策略：广度有限搜索、随机游走搜索、最大度搜索等  WS 小世界网络 48