《图论及其应用》

《《图论及其应用》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论及其应用图论发展史图论在现代科学技术中有着重要的理论价值和广泛的应用背景，如：线性代数、密码学、物理化学、网络设计、计算机科学、信息科学、DNA的基因谱的确定和计数、工业生产和企业管理中的优化方法等都广泛的应用了图论及其算法。首先我们通过图的发展过程来了解一下图论所研究的内容。图论起源于18世纪的一个游戏----俄罗斯的哥尼斯堡七桥问题。（1736年瑞士数学家欧拉——图论之父）ABDC转化Euler1736年BDCA图论中讨论的图问题：是否能从A，B，C，D中的任一个开始走，通过每座桥恰好一次再回到起点？是否能从任意一个顶点开始，通过每条边恰好一次再回到起点？转化包含两个要素：对象（陆地

2、）及对象间的二元关系（是否有桥连接）七桥问题中国邮递员问题1962年中国数学家管梅谷提出图论中的“中国邮递员问题”。问题：一个邮递员从街区的某一点出发，经过街区每条街道至少一次又回到原出发点，如何设计投递路线，使总路程最短？Hamilton问题源于1856年，英国数学家Hamilton设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的二十座大城市（见图），提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。反映到图论上就是判断一个给定的图是否存在一条含所有顶点的回路。Hamilton问题四色问题是世界近代三大数学难题之一。四色问题的内容是：任何一

3、张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。它的提出来自英国。1852年，毕业于伦敦大学的弗南西斯·格思里发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢？四色问题1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。1890年，在牛津大学就读的年仅29岁的赫伍德以自己的精确计算指出了肯普在证

4、明上的漏洞。不久，泰勒的证明也被人们否定了。后来，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。后来美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，有人从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。1976年6月，美国伊利诺大学哈肯与阿佩尔在两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明，轰动了世界。然而，真正数学上的严格证明仍然没有得到！数学家仍为此努力，并由此

5、产生了多个不同的图论分支。几个事实：任意的6个人中，总有3个人互相认识或有3个人互不认识。任意的9个人中，总有3个人互相认识或有4个人互不认识。问题：对任意的自然数k和t，是否存在一个最小的正整数r(k,t)，使得每个至少有r(k,t)个人的团体，总有k个人互相认识或有t个人互不认识。拉姆瑟（F.P.Ramsey）在1930年证明了这个数r(k,t)是存在的，人们称之为Ramsey数。确定其精确值是个公开的难题。Ramsey问题Ramsey数R(p,q)p,q345678936914182328364182535–4149–6156–8469–115543–4958–8780–143101–

6、216121–3166102–165111–298127–495169–7807205–540216–1031232–17138282–1870317–35839565–6588Ramsey数的计算Ramsey数的计算是对人类智力的挑战！例如R(4,5)=25(1993年计算机11年的计算量)Erdös用如下比喻说明其困难程度：一伙外星人入侵地球，要求一年内求得R(5,5)，否则将灭绝人类！那么也许人类能集中所有计算机和专家来求出它以自保；但如果外星人问的是R(6,6)，那么人类将别无选择，只能拼死一战了。Ramsey理论的哲理意义完全的无序是不可能的(Completedisorderisi

7、mpossible)。任一足够大的结构中必定包含一个给定大小的规则子结构。无序无意的行为产生了有规律的后果，发人深思耐人寻味。古人在满天的星斗中发现野兽和众神群集于天空的图形，以为是造物主的杰作。但根据Ramsey定理，只要随机分布的星星数目足够多，就可以描绘出各种图形的轮廓。1994年StatisticalScience的一篇论文利用统计方法证明：圣经隐藏了许多讯息，而这些讯息是有意安排的，绝非文字排列偶然