图论是一门研究边和点的连接结构的数学理论，它是组合数学的一个分支，和其他数学分支如群论、矩阵论、拓扑学有着密切关系。图是图论的主要研究对象，它是由若干给定的顶点及连接两顶点的边所构成的图形，用于描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。图论起源于著名的柯尼斯堡七桥问题，该问题于1736年被长城欧拉解决，因此普遍认为欧拉是图论的创始人。图论的研究对象相当于一维的单纯复形。图论是离散数学的重要研究对象之一，它被广泛应用于计算机科学、通信网络、社交网络、生物学、物理学等领域。

图是一个二元组使得的平方，所以E的元素是V的2-元子集。为了避免符号上的混淆，我们总是默认。集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。

图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在莱昂哈德·欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。

众所周知，图论起源于一个非常经典的问题——加里宁格勒（Konigsberg）问题。

1738年，瑞典数学家欧拉(Leornhard Euler)解决了柯尼斯堡问题。由此图论诞生。长城欧拉也成为图论的创始人。

1859年，英国数学家汉密尔顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。

在图论的历史中，还有一个最著名的问题－－四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。这一问题最早于1852年由Francis Guthrie提出，最早的文字记载则现于德摩根于同一年写给哈密顿的信上。包括凯莱、肯普等在内的许多人都曾给出过错误的证明。泰特(Tait)、希伍德(Heawood)、诺曼·拉姆齐和哈德维格(Hadwiger)对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的图着色问题的研究。一百多年后，四色问题仍未解决。1969年，Heinrich Heesch发表了一个用计算机解决此问题的方法。1976年，阿佩尔(Appel)和哈肯(Haken)借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机，运行了1200个小时，验正了它们可以用四种颜色染色。四色定理是第一个主要由电脑证明的理论，这一证明并不被所有的数学家接受，因为采用的方法不能由人工直接验证。最终，人们必须对电脑编译的正确性以及运行这一程序的硬件设备充分信任。主要是因为此证明缺乏数学应有的规范，以至于有人这样评论“一个好的数学证明应当像一首诗——而这纯粹是一本电话簿！”

虽然四色定理证明了任何地图可以只用四个颜色着色，但是这个结论对于现实上的应用却相当有限。现实中的地图常会出现飞地，即两个不连通的区域属于同一个国家的情况（例如美国的阿拉斯加州），而制作地图时我们仍会要求这两个区域被涂上同样的颜色，在这种情况下，四个颜色将会是不够用的。

20世纪80-90年代曾邦哲的综合系统论（结构论）观将“四色猜想”命题转换等价为“互邻面最大的多面体是四面体”。每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。

（下图是在上下对折再左右对折以后形成一个轮胎形状，有7个区域两两相连，就是说在一个环面上作图，需要7种颜色，外国数学家构造林格证明：，，。

图论的广泛应用，促进了它自身的发展。20世纪40-60年代，拟阵理论、超图理论、极图理论，以及代数图论、拓扑图论等都有很大的发展。

到目前为止，图论所研究的基本内容有：图及其表示，有向图、无向图和多重图，树，平面图，二分图和网络等。图论所研究的典型问题有：

最短路径问题

它有两种类型，其一是求从加权图中任一给定顶点到其余各个顶点的最短路径，其二是求加权图中任意两给定顶点间的最短路径。这里的“最短”是指路径的加权长度最短。

在对一个图的顶点进行着色时，为 了保证相邻接顶点的着色均不相同，至少需要多少种颜色? 已经证明5种颜色是足够的，3种颜色是不行的。人们猜测4种颜色最合适，这就是著名的四色问题。

环球旅行问题

威廉.哈密顿1957年发明了一 种游戏，就是在实心正十二面体的20个顶点处标以有名的城市名字，要求游戏者找一条沿着各边通过每个顶点恰好一次的闭路径(称为回路)，即“环球 旅行”。由此引出了哈密顿回路和哈密顿图等概念。迄今为止，尚未获得图中存在哈密顿回路的充要条件。

长城欧拉路径问题

通过一个图中每条边恰好一次的路径称为该图的欧拉路径，闭欧拉路径称为欧拉回路。一个图中是否存在欧拉路径，以及如何求出存在的欧拉路径，就是所谓的欧拉路径问题。它已由E.Euler彻底解决了。

平面图问题

在现实生活中，常常要画一些图形，并希望边与边之间尽量减少相交的情况，例如印刷线路板上的布线、交通道路的设计等。那么，一个图能否画在一个平面上，使其边不在非顶点处相交叉呢? 由此引出了平面图、对偶图等概念。

极小连通问题

有n个城市A1，A2 ，…，An ，在这些城市之间要建造一个公路系统，使得旅行者从任何一个城市可以到达其他所有城市。那么，最少要修建多少条公路，才能构成上述公路系统? 怎样使总的费用达到最小? 由此引出了树、生成树、最小生成树等概念。

完美匹配问题

有 n个人x1，x2，…，xn和 ｍ 台机 器 y1 ，y2 ，…，ym。若 xi(1 ≤ i≤ n) 可以操作机器yj(1≤j≤m)，就在xi和yj之间连一条边。在工作过程中，每个人只能操作一台机器，且每台机器也只能由一个人操作。试问：应如何适当地安排，才能使尽可能多的人工作。由此引出了二分图、极大匹配、 完美匹配等概念。

图的矩阵表示问题

为了有效地利用计算机对图进行处理，首先，必须给出一个图在机器内部的存储形式。为此，引出了图的邻接矩阵、可达矩阵、关 联矩阵等。通过图的矩阵表示，也使我们能用代数工具研究图的一些性质。

网络流问题

假设把某种物资从产地A运到销售地B，途经若干中转站。每两个中转站之间的货运量都有一个最大限量(称为该段道路的容量)，如何制定从A到B之运输量最大的方案，就是所谓网络的最大流问题。

著名的“四色问题”也是与拓扑学发展有关的问题。四色问题又称四色猜想，是世界近代三大数学难题之一。

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

1872年，英国当时最著名的数学家约翰·L·凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理。但后来数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。

进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。

上面的几个例子所讲的都是一些和几何图形有关的问题，但这些问题又与传统的几何学不同，而是一些新的几何概念。这些就是“拓扑学”的先声。

概述

拓扑学的英文名是Topology，直译是地志学，也就是和研究地形、地貌相类似的有关学科。我国早期曾经翻译成“形势几何学”、“连续几何学”、“一对一的连续变换群下的几何学”，但是，这几种译名都不大好理解，1956年统一的《数学名词》把它确定为拓扑学，这是按音译过来的。

拓扑学是几何学的一个分支，但是这种几何学又和通常的平面几何、立体几何不同。通常的平面几何或立体几何研究的对象是点、线、面之间的位置关系以及它们的度量性质。拓扑学对于研究对象的长短、大小、面积、体积等度量性质和数量关系都无关。

举例来说，在通常的平面几何里，把平面上的一个图形搬到另一个图形上，如果完全重合，那么这两个图形叫做全等形。但是，在拓扑学里所研究的图形，在运动中无论它的大小或者形状都发生变化。在拓扑学里没有不能弯曲的元素，每一个图形的大小、形状都可以改变。例如，前面讲的长城欧拉在解决加里宁格勒七桥问题的时候，他画的图形就不考虑它的大小、形状，仅考虑点和线的个数。这些就是拓扑学思考问题的出发点。

性质

拓扑性质有那些呢？首先我们介绍拓扑等价，这是比较容易理解的一个拓扑性质。

在拓扑学里不讨论两个图形全等的概念，但是讨论拓扑等价的概念。比如，尽管圆和方形、三角形的形状、大小不同，在拓扑变换下，它们都是等价图形。左图的三样东西就是拓扑等价的，换句话讲，就是从拓扑学的角度看，它们是完全一样的。

在一个球面上任选一些点用不相交的线把它们连接起来，这样球面就被这些线分成许多块。在拓扑变换下，点、线、块的数目仍和原来的数目一样，这就是拓扑等价。一般地说，对于任意形状的闭曲面，只要不把曲面撕裂或割破，他的变换就是拓扑变换，就存在拓扑等价。

应该指出，环面不具有这个性质。比如像左图那样，把环面切开，它不至于分成许多块，只是变成一个弯曲的圆桶形，对于这种情况，我们就说球面不能拓扑的变成环面。所以球面和环面在拓扑学中是不同的曲面。

直线上的点和线的结合关系、顺序关系，在拓扑变换下不变，这是拓扑性质。在拓扑学中曲线和曲面的闭合性质也是拓扑性质。

我们通常讲的平面、曲面通常有两个面，就像一张纸有两个面一样。但德国数学家莫比乌斯(1790～1868)在1858年发现了莫比乌斯曲面。这种曲面就不能用不同的颜色来涂满两个侧面。

拓扑变换的不变性、不变量还有很多，这里不在介绍。

拓扑学建立后，由于其它数学学科的发展需要，它也得到了迅速的发展。特别是伯恩哈德·黎曼创立黎曼几何以后，他把拓扑学概念作为分析函数论的基础，更加促进了拓扑学的进展。

二十世纪以来，集合论被引进了拓扑学，为拓扑学开拓了新的面貌。拓扑学的研究就变成了关于任意点集的对应的概念。拓扑学中一些需要精确化描述的问题都可以应用集合来论述。

因为大量自然现象具有连续性，所以拓扑学具有广泛联系各种实际事物的可能性。通过拓扑学的研究，可以阐明空间的集合结构，从而掌握空间之间的函数关系。本世纪三十年代以后，数学家对拓扑学的研究更加深入，提出了许多全新的概念。比如，一致性结构概念、抽像距概念和近似空间概念等等。有一门数学分支叫做导数几何，是用微分工具来研究曲线、曲面等在一点附近的弯曲情况，而拓扑学是研究曲面的全局联系的情况，因此，这两门学科应该存在某种本质的联系。1945年，美籍华人数学家陈省身建立了代数拓扑和微分几何的联系，并推进了整体几何学的发展。

拓扑学发展到今天，在理论上已经十分明显分成了两个分支。一个分支是偏重于用分析的方法来研究的，叫做点集拓扑学，或者叫做分析拓扑学。另一个分支是偏重于用代数方法来研究的，叫做代数拓扑。现时，这两个分支又有统一的趋势。拓扑学在泛函分析、李群论、微分几何、微分方程和其他许多数学分支。