【科普】中外介绍：图论之父欧拉与七桥问题
中文摘自《网络科学与统计物理方法》第一章
国外请看后面附录。
追溯网络发展的足迹，网络科学是网络的新科学（New Science of Network）的简称，其发展史大致经历了三个时期（早期、中期和现代时期）[4，6]。
第一时期欧拉图论（早期1736-1966）：。
网络是首先得益于图论的发展。历史上，早在二百多年前，多位杰出数学家各自独立地建立和研究过图论，他们的贡献功不可没。关于图论的文字记载最早出现在欧拉1736年的论著中，正如在诸论已经指出，图论起源于著名的柯尼斯堡七桥问题，具有很强的实际背景]，图论起源于著名的柯尼斯堡七桥问题。哥尼斯堡是东普鲁士的首都，今俄罗斯加里宁格勒市，普莱格尔河横贯其中。十八世纪在这条河上建有七座桥，将河中间的两个岛和河岸联结起来。人们闲暇时经常在这上边散步，有人提出：能不能每座桥都只走一遍，最后又回到原来的位置。这个看起来很简单却很有趣的问题吸引了很多人去尝试各种各样的走法，然而无数次的尝试都没有成功。谁也没有做到，看来要得到一个明确、理想的答案决非那么容易。1736年，有人带着这个问题找到了当时的大数学家欧拉，欧拉经过一番思考后，很快就用一种独特的方法给出了解答。首先,欧拉首先把这个问题简化，他把两座小岛和河的两岸分别看作四个点，而把七座桥看作这四个点之间的连线，如图1-1右边所示，A、B、C，D表示陆地。欧拉图的研究开创了“图论”这门新的数学分支，因此，这是第一代科学家对网络的开创性贡献，于是欧拉被誉为图论之父。问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。即这个问题就简化成，能不能用一笔就把这个图形画出来。经过进一步的分析，欧拉得出结论——不可能每座桥都走一遍最后回到原来的位置，因为七桥连接的边是奇数的。并且给出了所有能够一笔画出来的图形应具有解的充分必要条件是图中所有节点的度必须都为偶数。显然七桥问题中存在节点的度为奇数情形，所以它是无解的。这是拓扑学的“先声”。欧拉在1736年解决了这个问题，他用抽象分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个「图」。欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使欧拉成为图论〔及拓扑学〕的创始人。在数学上，除了哥尼斯堡七桥问题，还有多面体的欧拉定理、四色问题等都是拓扑学发展史上著名的重要问题。
图1-1瑞士数学家莱昂哈德·欧拉(Leonhard Euler, 1707-1783)求解哥尼斯堡七桥问题示意图。欧拉是科学史上最多产的一位杰出的数学家，一生共写下了886本书籍和论文.并以惊人的顽强毅力和孜孜不倦的治学精神，在他双目失明后的17年间，口述了几本书和400篇左右的论文．19世纪伟大数学家高斯（Gauss，1777-1855年）评价是："研究欧拉的著作永远是了解数学的最好方法．"
第二时期（中期1967-1997）：随机图理论。
两位匈牙利著名的数学家Edos（爱多士）和Renyi，他们在20世纪50年代末和60年代建立了著名的随机图理论，用相对简单的随机图来描述网络，简称ER随机图理论，他们的最重要发现是ER随机图中许多重要性质都是随着网络规模的增大突然涌现的。爱多士被称为20世纪的欧拉，并于1984年获得沃尔夫奖，他是20世纪最杰出的数学家之一，他的一生“四海为家”，充满着传奇色彩，一生留下约1475篇文章。他们创立的ER随机图理论为图类的阈函数和巨大分支涌现的相变等提供了研究网络的一种重要的数学理论，，他还与那些伟大的理论物理学家和数学家，如爱因斯坦、哥德尔、奥本海默等有密切的学术交往。确实，用图论的语言和符号可以精确简洁地加以描述各种网络，图论不仅为数学家和物理学家提供了描述网络的共同语言和研究平台，而且至今图论的许多研究成果、结论和方法技巧仍然能够自然地应用到现在复杂网络的研究中去，成为网络研究的有力方法和工具之一。可见在长达40年来ER随机图对于图论理论的影响之大和如此广泛。
第三时期（现代时期1998-现在）：现代网络理论。
一直到1998年，首先冲破了ER理论的框框的人是，美国康奈尔（Cornell）大学理论和应用力学系的博士生Watts及其导师Strogatz在《Nature》杂志上发表了题为《“小世界”网络的群体动力行为》的论文[1]，提出了小世界网络模型。实际上这是20世纪60年代美国哈佛大学的心理学家Milgram曾经作过的著名的小世界实验的一种拓广。人们常有这么经验，当参加国内外会议或访问或旅游时，经常与遇到一些新朋友交谈时，你很快就发现：他认识你的朋友，你认识他的朋友的朋友，于是大家不约而同地脱口而出：这个世界真小啊！这就是“小世界效应（现象）”，这里包含了“六度分离”概念的基本思想。1967年，美国哈佛大学社会心理学教授斯坦利·米尔格兰姆，他从内布拉斯加州和堪萨斯州随机选择的三百多名志愿者，请他们邮寄一个信函。信函的最终目标是米尔格兰姆指定的而且志愿者们都不认识的一名住在波士顿的股票经纪人。米尔格兰姆让志愿者把信函发送给他们认为最有可能与目标建立联系的亲友，并要求每一个转寄信函的人都回发一个信件给米尔格兰姆本人。出人意料的是，有六十多封信最终到达了目标股票经济人手中，并且这些信函经过的中间人的数目平均只有5个。也就是说，陌生人之间建立联系的最远距离是6个人。同年5月，米尔格兰姆提出了著名的“六度分离”理论。
2001年后，为了进一步证明六度分离理论应用于复杂网络，哥伦比亚大学教授的Duncan Watts利用互联网，在157个国家内选择了48000名志愿者，让他们通过各自的人脉关系网将一封名为“Package”的电子邮件，发送给19个目标。Duncan Watts实验证明每个成功的发送基本上要经过6个人左右。
值得关心和惊奇的是，我国在一千多年前，唐朝著名诗人王勃在《送杜少府之任蜀州》中的 “海内存知已，天涯若比邻”，这句名诗，涵盖了你我他，从古到今，家喻户晓。我认为，实际上是中国人从人文和哲学上最先认识到了小世界现象，只不过现代科学进行科学实验论证罢了。
1999年美国圣母（Notre Dame）大学物理系的Barabasi教授及其博士生Albert在《Science》杂志上发表了题为《随机网络中标度的涌现》一文，提出了一个无标度网络模型，发现了复杂网络的无标度性质，并和M. Newmann.D. J. Watts共同编辑了“网络的结构与动力学”（The Structure and Dynamics，普林斯顿大学出版社, 普林斯顿, 2003年）专著，该书在国际上产生了广泛的影响，引起了全世界的高度重视。正是他在网络科学方面的杰出贡献，因此于2006年获得了匈牙利von Neumann（冯 纽曼）计算金奖。标志着复杂网络研究进入了网络科学的新时代[1-2]，由此诞生了一门崭新的科学：网络科学。复杂网络的两大发现，以及随后许多真实网络的实证研究表明，真实世界网络既不是规则网络，也不是随机网络，而是兼具小世界和无标度特性，具有与规则网络和随机图完全不同的统计特性。这在全世界学术界激起了千重浪，复杂网络文章铺天盖地，网络科学的综述和专著不断涌现[4-8]，从物理学到生物学，从社会科学到技术网络，从工程技术到经济管理等众多领域，受到了人们的空前的广泛关注和重视。
许多真实世界网络的实证研究不断表明，真实网络既不是规则网络，也不是随机网络，而是兼具小世界和无标度特性，具有与规则网络和随机图皆不同的统计特性。这在全世界学术界掀起了网络研究的热浪，复杂网络理论研究大大超出了数学的范畴，受到了从物理学到生物学，从社会科学到技术网络、工程技术和经济管理等众多领域人们的广泛关注，并且正在不断取得突飞猛进。
国际上，有许多学者对网络科学发展的三个时期都作出了杰出的和重要的贡献，我们在表1-1一览表中已经罗列出网络发展史上若干主要事件、人物及其贡献。
请看七桥问题国外介绍Euler_7[1].pdf
https://blog.sciencenet.cn/blog-266190-568941.html
上一篇：
致中国高等科学技术中心的汇报总结下一篇：
谈点开券有益和精读难
