关于哥尼斯堡七桥问题的综述

计算机基础相关理论

关于哥尼斯堡七桥问题的综述

学生姓名：赵锋

学生学号：090741132

联系方式：13662061508

摘要：随着科学技术的不断发展，图论的理论和方法已经渗透到物理、化学、通讯科学、运筹学、遗传学、管理学、经济学、社会学等各门学科中，而且延伸出了超图理论、代数图论、随机图论、网络图论等分支，大大丰富了图论学科内容，促进了图论研究和应用。由于计算机科学技术的飞速发展和网络技术的广泛应用，图论作为计算机网络科学研究的基本工具和理论基础，会越来越受到人们的重视，不断推动图论学科继续向前蓬勃发展。本文通过阅读大量文献，总结出了图论的来源、应用及其未来的发展趋势。

关键词：哥尼斯堡七桥、图论、一笔画

计算机基础相关理论

关于哥尼斯堡七桥问题的综述

引言

经典问题往往以深入浅出的形式表达学科深奥的科学规律和本质内容，在学科研究中常常用来辅助说明思想、原理、方法和技术。出生于瑞士的伟大数学家欧拉（Leonhard Euler，1707—1783）于1736年发表了论文《与位置几何有关的一个问题的解》，文中提出并解决了七桥问题，为图论的形成奠定了基础。今天，图论已广泛应用在计算机学科、运筹学、控制论、信息论等学科中，成为对现实世界进行抽象的一个强有力的数学工具。

一、哥尼斯堡七桥问题的由来

哥尼斯堡就是现在的俄罗斯的加里宁格勒。哥尼斯堡在第二次世界大战前属于德国，是东普鲁士的首府，在历史上，哥尼斯堡的归属曾发生过几次变化。二战结束后，根据雅尔塔和波斯坦协议，东普鲁士部分领土划归苏联，是苏联作为战胜国享受的战利品。苏联把哥尼斯堡更名为加里宁格勒，斯大林没有把加里宁格勒划入刚刚并如苏联的立陶宛，而是划入俄罗斯联邦。加里宁格勒风景秀丽，气候宜人这里有着丰富的自然资源，是重要的军事基地，也是重要的海运港口。1991年苏联解体，波罗的海周边三国的立陶宛，拉脱维亚和爱沙尼亚独立，加里宁格勒就变成了俄罗斯的一块飞地。

普莱格尔河穿过美丽的哥尼斯堡城。普莱格尔河有两个支流，在城市中心汇成大河，中间是岛区，人们在河上建起了七座桥，使这里成为风景优美的人间仙境，如图1

所示。

由于岛上有古老的哥尼斯堡大学，有知名的教堂，有大哲学家康德的墓地和塑像，因此城中的居民，尤其是大学生们经常到河岸和上桥散步。在十八世纪初，有一天，有人突发奇想：如何才能走过七座桥，而每座桥都只能经过一次，最后又回到原来的出发点？当地的人们开始沉迷于这个问题，在桥上来来回回不知走了多少次，然而却始终不得其解，这就是著名的哥尼斯堡七桥问题的由来。

二、相应理论的开创——图论

通过数学建模，已经把实际问题转化成了数学问题。这时欧拉注意到，如果一个图形能一笔画成那么除去起点和终点外，其他的点都是经过点。而经过点是有进有出的点，即有一条线进这个点，就一定有一条线出这个点，不可能有进无出，如果有进无出，它就是终点；也不可能有出无进，如果有出无进它就是起点。因此，在经过点进出的线总数应该是偶数。

计算机基础相关理论

我们称在一个点进出线的总数是偶数的点为偶点；总数为奇数的点称为奇点。如果起点和终点是同一个点，那么它也属于有进有出的点，它也是偶点这样图上的点全是偶点。如果起点和终点不是同一个点，那么它们必定是奇点。因此，能够一笔画的图形最多只有两个奇点年 欧拉证明了自己的猜想，一次不重复。

1936年，欧拉证明了自己的猜想，一次不重复走完七座桥是根本不可能的。随即他发表了“一笔画定理”：

一个图形要能一笔画完，必须符合以下两个条件：

（1）图形是封闭连通的；

（2）图形中的奇点个数为0或1；

七桥问题中的四个点全是奇点（如图2），当然不能一笔画，即不可能一次无重复地走完七座桥。一般地说如果图中的点全是偶点，那么可以任意选择一个点作为起点，当然终点与起点重合能一笔画成，如果图中有两个奇点，那么可以任意选一个奇点作为起点，另一个奇点为终点可以一笔画成。

欧拉的这个研究成果，开创了图论这门新的学科，这门学科在计算机科学中有着广泛的应用。

三、图论的应用

1、一个部门中有25人，由于纠纷而使得关系十分紧张，是否可便每个人与5个人相处融洽？这看起来是社会学领域的间题，我们可以尝试多种方法，而其中的一种方法就是将其化为图。建立一个图的模型，最基本的问题是如何描述它—什么是结点，什么是边？在本问题中，没有太多的选择，只有人和纠纷。我们可试着用结点来代表人。用边来代表图中结点之间的关系，这是很常见的。在这里结点之间的关系是“关系是否融洽”，因此，若两个结点（人）关系融洽，那么就在它们之间加上一条边。

计算机基础相关理论

现在假设每个人与其他5个人关系融洽。例如，在图一上显示出我们所描述的图的一部分，小张与小王、小李、小赵、小黄和小吴关系融洽，再没有其他人。个人均是这种情况。这是否可能在图论中，一个重要的推论在任意图中，具有奇数度的结点个数必为偶数。现在 出现了矛盾：有25（奇数）个具有5（奇数）度的结点。因此，该间题是

不可能实现的。

2、举行一个国际会议，有a，b，c，d，e，f，g等7个人。已知下列事实：

a会讲英语；

b会讲英语和汉语；

c会讲英语、意大利语和俄语；

d会讲 日语和汉语；

e会讲德语和意大利语；

f会讲法语、日语和俄语；

g会讲法语和德语。

试问这7个人应如何排座位，才能使每个人都能和他身边的人交谈？

这个问题看起来很熟悉。我们还是用图解这个问题。依然是建立一个图的模型，确定结点和边。这里有“人和语言 ”，那么我们用结点来代表人，于是结点集合V={a、b、c、d、e、f、g}。对于任意的两点，若有共同语言，就在它们之间连一条无向边，可得边集E，图G=(V，E)，如图二：

如何排座位使每个人都能和他身边的人交谈？问题转化为在图G中找到一条哈密顿 回路的问题（哈密顿回路即是通过每个结点一次且仅一次的回路。而 即是图中的一条哈密顿

计算机基础相关理论

回路）。照此顺序排座位即可。

3、有三座城市C1、C2、C3以，要修建高速公路与另外三座城市C4，C5，C6直接相连通。能否设计一个公路网使任意两个高速公路之间彼此不交叉？

这是一个涉及交通方面的问题。很显然我们用结点代表城市，两城市之间修建高速公路，则在它们之间连一条无向边。图三所示是一个存在交叉的设计方案。

当你试着找出一个不存在交叉的设计方案时，很快就会发现不可能做到这一点。

我们给出一个定义：如果一个图能够在平面中画出来，且任意两条边不相交，则该图就是平面图。

在设计电路时要求相交的线尽可能的少，因此，电路设计者面临的主要问题就是平面性问题。

当在一个平面上画出一个连通的平面图时，该平面被分成几个连续的区域，这样的区域被称为面，我们称图G=(V，E)，点集V的个数为v，边集E的个数为e,若G是平面图,面的个数为f。早在1752年，欧拉证明了对于任何连通的平面图均满足等式：f=e-v+2。图三被我们称作k3.3，现在我们用来证明k3.3不是平面图。

假设k3.3是平面图，面数为f， …… 此处隐藏：2093字，全部文档内容请下载后查看。喜欢就下载吧 ……