数据结构图论学习报告

学习报告报告题目：图论的前世今生报告要求涵盖以下内容：1.图论的起源图论起源于著名的柯尼斯堡七桥问题。

在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。

然而无数次的尝试都没有成功。

欧拉在1736年解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个“图”（如下图）。

欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。

这就是后来的欧拉路径和欧拉回路。

这项工作使欧拉成为图论〔及拓扑学〕的创始人。

2.图论的发展图论是数学领域中发展最快的分支之一，它以图为研究对象。

图论中的图是有若干给定的点及连接两点的线所构成的图形，这种图形常用来描述某些事物之间的某种特定关系，用来代表事物，用连接两点的线表示相应两个事物间具有这种关系。

图论本身是应用数学的一部分，因此，历史上图论曾经被好多位数学家各自独立的建立过。

关于图论的文字记载最早出现在欧拉1736年的论文中，他所考虑的原始问题有很强的实际背景。

数学史上著名的七桥问题欧拉只用了一步就证明了不重复地通过7座桥的路线是根本不存在的!这是拓扑学研究的先声。

图的染色问题一直是图论研究的焦点问题。

数学家赫伍德成功地运用肯普的方法证明了五色定理，即一张地图能够用五种或者更少的颜色染色。

美国伊利诺斯大学的黑肯和阿佩尔，经过四年的艰苦工作．终于完成了四色猜想的证明。

正是上述那些似乎没有多大意义的游戏的抽象与论证的方法，开创了图论科学的研究。

四色猜想的提出来自英国。

1852年，毕业于伦敦大学的弗南西斯?格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。

”这个现象能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。

兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。

1852年10月23日，他的弟弟就这个问题的证明请教了他的老师、著名数学家德?摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家汉密尔顿爵士请教。

汉密尔顿接到摩尔根的信后，对四色问题进行论证。

但直到1865年汉密尔顿逝世为止，问题也没有能够解决。

图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段：第一阶段是从1736年到19世纪中叶。

当时的图论问题是盛行的迷宫问题和游戏问题。

最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题。

东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔河的两岸，河中有一个岛，于是城市被河的分支和岛分成了四个部分，各部分通过7座桥彼此相通。

如同德国其他城市的居民一样，该城的居民喜欢在星期日绕城散步。

于是产生了这样一个问题：从四部分陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。

这就是有名的哥尼斯堡七桥问题。

哥尼斯堡七桥问题看起来不复杂，因此立刻吸引所有人的注意，但是实际上很难解决。

瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。

这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父。

欧拉把七桥问题抽象成数学问题---一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解。

Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在？Euler证明这样的回路是不存在的。

第二阶段是从19世纪中叶到1936年。

图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。

一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。

同时出现了以图为工具去解决其它领域中一些问题的成果。

1847年德国的克希霍夫将树的概念和理论应用于工程技术的电网络方程组的研究。

1857年英国的凯莱也独立地提出了树的概念，并应用于有机化合物的分子结构的研究中。

1936年匈牙利的数学家哥尼格写出了第一本图论专著《有限图与无限图的理论》。

标志着图论作为一门独立学科。

第三阶段是1936年以后。

由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展。

特别是电子计算机的大量应用，使大规模问题的求解成为可能。

实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的，需要计算机的帮助才有可能进行分析和解决。

目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用。

进入20世纪以来, 科学家们对四色猜想的证明基本上是按照肯普的想法在进进行。

电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的过程。

1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，做了100亿判断，终于完成了四色定理的证明。

不过不少数学家并不满足与计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。

我们看到，正是上述那些似乎没有多大意义的游戏的抽象与论证的方法，开创了图论科学的研究。

遗憾的是，由于当时社会生产落后，对图论知识的要求甚寡，这一学科的发展颇为迟缓，甚至处于停滞状态。

此后的一百多年，图论经历了一场爆炸性的发展，终于成长为数学科学中一门独立的学科。

它的主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。

近几十年来，图论在科学界可以说是异军突起，活跃非常。

3.图论与数学的关系图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。

关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。

4.图论在计算机科学中的应用计算机鼓轮设计设计旋转鼓轮，要将鼓轮表面分成16个扇区，如图3.4（a）所示，每块扇区用导体（阴影区）或绝缘体（空白区）制成，如图3.4（b）所示，四个触点a、b、c和d与扇区接触时，接触导体输出1，接触绝缘体输出0。

鼓轮顺时针旋转，触点每转过一个扇区就输出一个二进制信号。

问鼓轮上的16个扇区应如何安排导体或绝缘体，使得鼓轮旋转一周，触点输出一组不同的二进制信号？显然，图3.4（b）所示，旋转时得到的信号依次为0010，1001，0100，0010，…，在这里，0010出现了两次，所以这个鼓轮是不符合设计要求的。

按照题目要求，鼓轮的16个位置与触点输出的16个四位二进制信号应该一一对应，亦即16个二进制数排成一个循环序列，使每四位接连数字所组成的16个四位二进制子序列均不相同。

这个循环序列通常称为笛波滤恩（DeBruijn）序列。

如图3.4（c）所示，16个扇区所对应的二进制循环序列正是笛波滤恩序列。

我们构造一个有8个顶点的有向图，顶点为8个三位二进制数000,001,010,011,100,101,110,111，可分别记为v0,v1,v2,v3,v4,v5,v6,v7，下标正好是顶点的十进制表示。

如果某个顶点vi的二进制表示的后两个数字与另一个顶点vj 的二进制表示的前两个数字相同，则由向引一条有向边ek，k是十进制数，对应i和j二进制表示将重合的数字只算一次的四位二进制数。

例如，e 1=<v,v1>=<000,001>=0001，e7=<v3,v7>=<011,111>=0111,…。

这样构造出一个连通有向图G，如图3.5所示。

图3.5每个顶点的出席均与入度相同，故为有向欧拉图，含有一条有向欧拉回路，回路中每条边均标记着一个不同的四位二进制数，可见，对应于图的欧拉回路，存在一个16个二进制数组成的循环序列，其中每4个接连的二进制子序列均不相同。

例如，对应于欧拉有向回路:e 0e1e3e7e15e14e12e9e2e5e11e6e13e10e4e8e对应于上述的欧拉有向回路的16个二进制数组成的循环序列是：0001111001011010把这个序列排成一个圆圈，与所求的鼓轮相对应，就得到鼓轮设计。

用类似的方法，我们可以证明：存在一个2n个二进制数组成的循环序列，其中2n个由n个接连的二进制数组成的子序列均不相同。

这个序列对应的欧位有向图称为笛波滤恩图，记作G2,n .图3.5中的图记为G2,4。