图论的起源和发展

大众文艺理论研究图论的起源和发展李冰（河北省唐山第五中学063000）摘要：图论是数学领域中发展最快的分支之一，数学史上著名试求从图中的任一点出发，通过每条边一次，最后返回到该的七桥问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 欧拉只用了一步就证明了不重复地通过7座桥的路线是根点，这样的路径是否存在？于是问题就变得简洁明了多了，同时也本不存在的！这是拓扑学研究的先声。图的染色问题一直是图论研究更一般、更深刻。这样一来，七桥问题就转变为图论中的一个一笔的焦点问题。数学家赫伍德（Hedwood）成功地运用肯普的方法证明画问题。即能不能一笔不重复的画出图1．1(b)中的这个图形。了五色定理，即一张地图能够用五种或者更少的颜色染色。美国伊利原先人们是要求找出一条不重复的路线，欧拉想，成千上万诺斯大学的黑肯（W.Haken）和阿佩尔（Appel），经过四年的艰苦的人都失败了，这样的路线也许根本不存在。于是，欧拉接下来工作，终于完成了四色猜想的证明。正是上述那些似乎没有多大意义着手判断：这样不重复的路线究竟存不存在？由于这么改变了一的游戏的抽象与论证的方法，开创了图论科学的研究。下提问的角度，欧拉抓住了问题的实质。最后，欧拉认真考虑了关键词：团论；染色体；四色猜想一笔画图形的结构特征。欧拉发现，凡是能用一笔画成的图形，都有这样一个特点：图论是组合数学的—个分支，与其他的数学分支，如群论、每当用笔画一条线进入中间的一个点时，还必须画一条线离开这矩阵论、概率论、拓扑学、数值分析等有着密切的联系（参见文个点。否则，整个图形就不可能用一笔画出。也就是说，单独考献[1]）。图论中以图为研究对象，图形中我们用点 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示对象，察图中的任何一点（起点和终点除外），这个点都应该与偶数条两点之间的连线表示对象之间的某种特定的关系。事实上，任何线相连；如果起点与终点重合，那么，连这个点也应该与偶数条一个包含了某种二元关系的系统都可以用图形来模拟，而且它具线相连。有形象直观的特点。由于我们感兴趣的是两对象之间是否有某在七桥问题的几何图中，A、B、D三点分别与3条线相连，C种特定关系，所以图形中两点间连接与否尤为重要，而图形的位点与5条线相连。连线都是奇数条。因此，欧拉断定：一笔画出置、大小、形状及连接线的曲直长短则无关紧要。这个图形是不可能的。也就是说，不重复地通过7座桥的路线是20世纪后，图论的应用渗透到许多其他学科领域。从20世根本不存在的！天才的欧拉只用了一步就证明了这个难题，从这纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发里我们也可以看到图论的威力有多么的强大！展，使图论成为数学领域中发展最快的分支之一。欧拉对七桥问题的研究，是拓扑学研究的先声。一、图论的起源1750年，欧拉又发现了一个有趣的的现象。欧拉得到了后人图论是一个古老的但又十分活跃的数学学科，也是一门很以他的名字命名的“多面体欧拉公式”。正4面体有4个顶点、6有实用价值的学科，它在自然科学、社会科学等各领域均有很多条棱，它的面数加顶点数减去棱数等于2；正6面体有8个顶点、应用。近年来它受计算机科学蓬勃发展的刺激，发展极其迅速。12条棱，它的面数加顶点数减去棱数也等于2。接着，欧拉又考应用范围不断拓广，已渗透到诸如语言学、逻辑学、物理学、化察了正12面体、正24面体，发现都有相同的结论。于是继续深入学、电讯工程、计算机科学以及数学的其它分支中。研究这个问题，终于发现了一个著名的定理：1736年是图论的历史元年。这一年，欧拉（L•Euler）研究了哥尼斯堡城（Königsberg）的七桥问题，发表了图论的首篇论这个公式证明了多面体只有正四面体、正六面体、正八面文。欧拉也因此被称为图论之父。体、正十二面体、正二十面体五种。这个定理成为拓扑学的第一古老而美丽的哥尼斯堡城濒临蓝色的波罗的海，是著名的个定理，这个公式被认为开启了数学史上新的一页，促成了拓扑哲学家康德（ImmanuelKant）的出生地，城中有一条普莱格尔学的发展。（Pregel）河，河的两条支流在这里汇合，然后横穿全城，流入二、图论的发展大海。河水把城市分成4块，于是，人们建造了7座各具特色的从19世纪中叶开始，图论进入第二个发展阶段。这一时期桥，把哥尼斯堡城连成一体，如图1．1(a)所示。图论问题大量出现，诸如关于地图染色的四色问题、由“周游世早在18世纪，这些形态各异的小桥吸引了众多的游客，游人界”游戏发展起来的哈密顿(W.Hamilton)问题等。在陶醉于美丽风光的同时，不知不觉间，脚下的桥触发了人们的图的染色问题一直是图论研究的焦点问题。最早记载染色问灵感，一个有趣的问题在居民中传开。题的是英国伦敦大学（UniversityofLondon）的数学教授德•A摩根（D.Morgan）。1852年，一位刚从伦敦大学毕业的学生费南西斯•古色利（F.Guthrie）在研究英国地图时想到了一个奇怪的问题。这个CD问题被称为世界近代三大数学难题之一，这就是著名的“四色猜想”。问题的起源是这样的：古色利望着挂在墙上的英国地图发呆，他边数着英国的行政B区域，边查找它们的位置，同时还注意各区域的地图着色，看着图1．1(a)图1．1(b)看着他突然发现，该地图仅用四种不同的颜色便可以将地图中相邻的区域分开。古色利无法解释这一现象，于是他写信给仍在大谁能够从两岸A，B或两个小岛C，D中任一个地方出发一次学读书的弟弟，让他向该校有名的数学家德•摩根请教。摩根首走遍所有的7座桥，而且每座桥都只通过一次？这个问题似乎不先注意到：区分地图上的不同区域少于四种颜色不行。但遗憾的难，谁都乐意用这个问题来测试一下自己的智力。可是，谁也没是摩根本人也未能解决这个问题。于是向自己的好友、著名数学有找到一条这样的路线。这个问题极大的刺激了德意志人的好奇家哈密顿爵士请教。哈密顿接到摩根的信后，对四色问题进行论心，许多人热衷于解决这个问题，然而始终未能成功。“七桥问证。但直到1865年哈密顿逝世，问题也没有能够解决。题”难住了哥尼斯堡城的所有居民。哥尼斯堡城也因“七桥问1878年，英国数学家凯莱（Cayley）在伦敦数学年会上正题”而出了名。这就是数学史上著名的七桥问题。式提出该问题——平面或球面上的地图仅需四种颜色可以将任问题看来不复杂，但谁也解决不了，也说不出其所以然来。何相邻的两区域分开——且征求解答，人称“四色猜想”的问1736年，当时著名的数学家欧拉仔细研究了这个问题，他将上题便引起了世界数学界的重视。许多一流的数学家纷纷参加了述四块陆地与七座桥间的关系用一个抽象图形来描述(见图1．四色猜想的大会战。1878—1880年，著名的律师兼数学家肯普1(b))，其中A、B、C、D分别用四个点来表示，而陆地之间有桥（Kempe）和泰勒（Taylor）两人分别提交了证明四色猜想的论相连者则用连接两个点的连线来表示，这样，上述的哥尼斯堡七文，宣布证明了四色定理，大家都认为四色猜想从此也就解决桥问题就变成了由点和边所组成的如下问题：了。但是数学家赫伍德（Hedwood）仍然花费毕生精力致力于四34文艺评论大众文艺《崽崽》：透过亡灵告白的深情与思辨郭宇（上海大学文学院200444）摘要：发表于文学杂志《江南》的小说《崽崽》是一篇颇具创度的影响。作家莫言曾说，他“这种年纪的作家毫无疑问都受到意的意识流小说，该作是作者朱振武根据自己的亲身经历创作而成，了西方文学的影响，因为在80年代以前中国是封闭的，……改革讲述了一家三口和一只名叫崽崽的宠物小白兔之间感人至深的温情故开放以后大量的西方文学被翻译进来，我们有一个两三年的疯狂事。作者创作时有意在形式上进行探索，在内容上将“感情”进行到阅读时期，这种影响就自然而然地产生了，从而不知不觉地就底，并以颇富哲理意味的方式对人世间的种种现象发起思索与争鸣。把某个作家的创作方式转移到自己的作品中来了。”[3]朱振武作本文试图从形式上的锐意尝试、表层中的以情动人，以及深层下的思为莫言的同龄人，也是被西方文学滋润的一份子，加之又是研究辨色彩这三个方面对《崽崽》进行浅尝辄止的解读。美国文学的教授，因此他的创作也较多地带有西方文学影响的痕关键词：意识流；崽崽；朱振武迹。在《崽崽》这部作品中，最明显的一点则非意识流莫属。朱振武有意借鉴了意识流小说这一文体形式。小说通篇都一个睿智的爸爸、一个温柔的妈妈、一个活泼的姐姐，以是按照小兔子的心理活动的轨迹进行组织行文。作品伊始就是爸及一只调皮可爱的小白兔，构成了《崽崽》[1]最令人难忘和动容爸和妈妈的对话，但是却没有引号。而且不仅这里的对话没有引的画面。小说是作者朱振武[2]根据自己的亲身经历创作而成，讲号，全文中的对话都没有使用引号。这不是作者忘记了，或是编述了一家三口和一只名叫崽崽的宠物小白兔之间感人至深的温情辑不细心，而是作者有意舍弃了引号。一方面，因为文中的一切故事。作者创作时有意在形式上进行探索，大胆运用了意识流文都是小兔子的意识，记述的是小兔子的所见所闻所思所想，所以体，并借鉴了通俗小说中设置悬念的手法。在内容上，朱振武一为了强化作品是小兔子的心理活动这一特点，作者有意识地回避了方面将“感情”进行到底，使全文弥漫了浓浓的爱的气息，令人服务于对话的引号，将小兔子置于一种思想自由驰骋的状态之中。感动；另一方面，则充分展开思辨的翅膀，以颇富哲理意味的方另一方面，朱振武回避引号是和同样“摒弃”引号的女作家赵玫分式对人世间的种种现象发起思索与争鸣。因此，本文试图从形式享了相似的感受，引号的缺席能令作者的创作没有束缚，令作品的上的锐意尝试、表层中的以情动人，以及深层下的思辨色彩这三表述更加协调紧密，插叙对话和自然描述之间的转换更加灵活，个方面对《崽崽》进行浅尝辄止的解读。同时也让读者的阅读更为流畅。由于小说的主体内容是小兔子对形式上的锐意尝试于往昔的生活片段的回忆，因此意识流的使用完美地解决了文章作为全球畅销小说《达•芬奇密码》的中文译者，朱振武在中的碎片化内容的拼接问题，使散置的回忆自然地串联起来。解读该作品时指出了其成功的关键在于顺应了当下文学创作的雅在意识流作品中，视角是比较重要的一个因素。在《崽崽》俗合流的趋势。秉承这一见解，朱振武在《崽崽》的创作中选择中，作者选择了以一个亡灵的视角来讲述故事，但这个亡灵却了文学性较浓的意识流文体与通俗性较重的悬念手法相结合的外不是人，而是一只聪慧伶俐的小白兔，同时还辅以儿童的口吻观形式。和心理态势。崽崽深情地回忆了自已曾经在这个家庭生活的点点对于形式方面的探索是文学创作的一个重要组成部分，作滴滴。使用儿童视角和心理活动的一个最大的好处就是儿童的思为世界文学中的一员，中国当代作家也积极参与其中。自改革开想和认知具有极大的不确定性，所以可以更好地展现更多更深的放以来，西方的书籍和思想像其他东西一样大量地涌入国门，人矛盾和观点。不同的观点和事件可以同时在这一个孩子的心理进们，尤其是作家、学者开始如饥似渴地阅读这些于他们而言是万行对驳和展现，这一视角可以较好地服务于具有思辨性的内容。分新鲜宝贵的图书资源，那一代的人都潜移默化地受到了不同程以亡灵视角和儿童视角进行叙事的作品不在少数，但以一个死去色研究，前后整整60年，终于在1890年发表文章指出肯普证明中机取得的成果，他们还在寻找一种简洁明快的书面证明方法。的错误，不过，赫伍德却成功地运用肯普的方法证明了五色定在哈密顿的周游世界问题中，他用一个正十二面体(具有理，即一张地图能够用五种或者更少的颜色染色。不久，加拿大十二个五边形的面和二十个顶点)的二十个顶点表示世界上的数学家托特（Tóth）又举出反例，否定了泰勒的证明。后来，越二十座大城市，见图l.2。提出的问题是要求游戏者找一条沿来越多的数学家虽然对此绞尽脑汁，但仍一无所获。于是，人们十二面体的棱通过每个顶点恰好一次的闭路。图1．3所示的a，开始认识到，这个貌似简单容易的题目，其实是一个可以与费尔b，…s，t，a表示出了这样的一条闭路。由于运筹学、计算机马猜想相媲美的难题。科学和编码理论中的很多问题都可以转化为哈密顿问题，从而哈进入20世纪，科学家们对四色猜想的证明基本上是按密顿问题引起广泛的关注和研究。照肯普的想法在进行，并陆续有所进展。1913年，伯克霍夫我们看到，正是上述那些似乎没有多大意义的游戏的抽象与（Birkhoff）在肯普的基础上引进了一些新技巧；1939年，美国论证的方法，开创了图论科学的研究。遗憾的是，由于当时社会数学家富兰克林（Franklin）证明了22个以下区域都可以用四色生产落后，对图论知识的要求甚寡，这一学科的发展颇为迟缓，着色。随后又有人给出了更多区域的情形，直到1976年初，人们甚至处于停滞状态。两百年以后，即1936年，匈牙利著名图论学还是仅能对区域数是96的地图主色的四色猜想给出证明，但这些家柯尼系（König）发表《有限图与无限图理论》，这是图论的对区域数是自然数的情形来讲还远远不够。第一部专著，它 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 了图论二百年的主要成果，是图论的重要1976年6月，美国伊利诺斯大里程碑。此后的五十多年，图论经历了一场爆炸性的发展，终于学的黑肯（W.Haken）和阿佩尔成长为数学科学中一门独立的学科。它的主要分支有图论、超图（Appel），经过四年的艰苦工作，t理论、极值图论、算法图论、网络图论和随机图论等。近二十年在两台不同的电子计算机的帮助m来，图论在科学界可以说是异军突起，活跃非常。下，用了1200个小时，作了100亿次lnas的判断，终于完成了四色猜想的证kgo参考文献h明。四色猜想的计算机证明轰动的f[1]卜月华.图论及其应用.福建：东南大学出版社，2002.p世界，该证明不仅解决了一个历史jie[2]卢开澄.图论及其应用.北京：清华大学出版社,1984.一百多年的难题，而且有可能成为q[3]王树禾.图论及其算法.北京：中国科技大学出版社，1999.cd数学史上亿系列新思维的起点。不[4]邹庭容.数学文化欣赏.武汉：武汉大学出版社，2007.br过也有不少数学家并不满足于计算图l.2[5]王修智，展涛.数与形：数学卷.济南：山东科学技术出版社，2007.35