图论

　　图论（汉语拼音：Tulun；英语：Graph Theory），以图为研究对象的数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系、图论则是研究事物对象在上述表示法中具有的特征与性质的学科。图论的发展已有200多年的历史，它发源于18世纪普鲁士的柯尼斯堡。当地的居民想知道能否从任意一陆地出发，走遍联接该城的7座桥又回到原地？其条件是每座桥都经过一次并且只经过一次。（见七桥问题）很多人都曾试验过，但都失败了。L.欧拉把七桥问题化为一个数学问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解。这是图论发展的萌芽时期最具代表性的问题，那时不少图论问题都是围绕着游戏而产生的。从19世纪中叶开始图论进入第二个发展阶段，这个时期图论问题大量出现，诸如由“绕行世界”游戏发展起来的哈密顿问题、关于地图染色的四色问题以及与之相关联的图的可平面性问题等。这个时期也出现了以图为工具去解决其他领域中一些问题的成果，比如把树的理论应用到化学和电网络分析等。直到1936年D.柯尼希发表了图论的第一本专著《有限与无限图理论》，这时图论才成为一门学科，以后图论进入第三个发展阶段。由于生产管理、军事、交通运输和计算机网络等方面提出大量实际问题的需要，特别是许多离散化问题的出现，以及由于大型高速电子计算机而使许多大规模计算问题求解成为可能，图论的理论及其应用研究得到飞速发展。尤其是网络理论的建立，图论与线性规划、动态规划等优化理论和方法的互相渗透，促使和丰富了图论的内容和应用。它在通讯网络的设计分析、电网络分析、印刷线路板分析、信号流图与反馈理论、计算机流程图等众多领域都有成功的应用。图论讨论的问题主要有两种形式。一种是问“具有某种特征的对象是否存在？如果存在有几个？或者至少有几个？”另一种是问“怎样”构造一个满足某一性质的图或子图。这些问题体现在以下5个最有兴趣的研究领域，它们是：连通性、嵌入问题、染色问题、矩阵表示以及网络流。

基本概念

　　所谓图指的是一个有序对G＝（V，E），其中V是一个非空集合，称为顶点集合；E是V上的一个无序二元关系，称为边集合。称E中的每一条边和它所连接的顶点是关联的。如果某条边的两个端点重合，则称为环。如果联接两个顶点的边不止一条，则这些边称为多重边。无多重边的无环图称为简单图。如果图中任意两点间恰有一条边相联，则这样的图称为完全图。如果一个图的顶点集可以划分为两个子集，使得每一条边的两个端点分别属于这两个子集，则称该图为二部图。顶边相间的序列称为链，两端相重合的链叫做圈。以上定义的图又称无向图。将无向图各边定向之后，就构成有向图。有向图除顶点集外，还有弧集。每条弧从一个顶点（称为“头”）连接到另一个顶点（称为“尾”）。

连通性

　　如果对于图中的每一对顶点都存在一条链把它们联结起来，则称该图是连通的。连通性是图论研究的基本问题之一。以下列举的是有关连通性的典型问题：①欧拉路。在七桥问题中，用一个顶点代表一块陆地，当两个区域之间有桥相联时就在对应的两个顶点之间连接一条边。这样就得到与原来问题对应的一个图。所谓欧拉路指的是这样一条路，它包含该图的每一条边恰好一次。这个问题已经得到解答。欧拉路有不少应用，比如应用到城市街道单行线与双行线的合理布局，有助于控制交通运输的目的。②中国邮路问题。一个邮递员要走遍他负责的投递范围内的每一条街道，完成送信任务后回到邮局。他应按什么路线走才能使总路程最短？管梅谷教授最早提出这个问题并于1960年给出最优路线的条件和算法。因此国际上称此问题为中国邮路问题。③哈密顿问题。爱尔兰数学家W.R.哈密顿，在19世纪发明的绕行世界游戏引出了著名的哈密顿问题 。如果存在一条经过图G的所有顶点的简单圈，则称该图为H图。哈密顿问题就是要找出H图的特征描述，这个问题至今尚未彻底解决，此问题与四色问题及旅行售货问题密切相关，因此一直受到人们的关注。④树与图的支撑树。无圈的连通图称为树，包括图G的全部顶点的子图称为G的支撑图。如果支撑图是一棵树，则称它为支撑树。城市的交通网、电力网的布局可以归结为支撑树问题去解决，树还可以用来研究计算机的动态存贮分配和编码等。决策树是系统分析的重要工具。⑤匹配问题。安排一些人去做各种工作或者按照不同的计划要求把人们配成对，这些都属于匹配问题。它的一个基本问题是给定一个二部图，问不相邻的弧集最多能包含几条弧？这个问题可以转化为运输问题用线性规划方法求解，若用图论方法求解则更为简明方便。

嵌入问题与平面图

　　有一个古典难题，名叫“三井三屋”问题。问题是要求把3个井和3间屋的每一个连起来，使得连接的管线都不相交。如果这种图存在，则称它是一个平面图。一般地，如果一个图G可以画在一个曲面S上，使得任何两边都不相交，则称G可以嵌入到S内。如果一个图可以嵌入到平面内，则说它是一个可平面图。嵌入概念反映两个图之间的同构对应关系。三井三屋问题在平面上是无法实现的，即它是不可平面的。很多人致力于图的可平面性研究，1930年波兰数学家C.K.库拉托夫斯基提出可平面图的一个重要条件，1973年中国数学家吴文俊用代数拓扑方法给出了解决平面制定问题的新途径。平面问题的研究成果已经在交通网络和印刷线路的设计等方面得到应用。

染色问题

　　给定一个图，如果要求把所有顶点涂上颜色，使得相邻顶点具有不同的颜色，问最少需要几种不同的颜色？这个问题叫做图的点染色问题。如果对给定图的全部边都涂上颜色，使相邻的边有不同的颜色，问至少需要几种颜色？这个问题叫做边的染色问题，边的染色问题可以转化为点染色问题，它们都归属于将一个图划分为独立子集的理论。平面图的染色问题是与四色问题紧密相联的。19世纪中叶，四色问题以猜想形式被提出来，这个猜想是说平面上任何一个地图都能够只用4种颜色给各个国家染色 ，使得任何两个相邻的国家有不同的颜色，这里两个国家相邻是指它们有一段公共边界。100多年来数学家们一直没有攻克这个难题，直到1976年才由K.I.阿佩尔等人借助计算机给出一个浩繁的证明。由于染色问题反映了广泛而深刻的实际背景，它的研究带动了整个图论的发展。

图的矩阵表示

　　一个图可以用几何图形表示，这种表示有直观形象的优点。图还可以用矩阵表示，它给出一个代数结构，从而可以运用代数的技巧解决图论问题，而且有利于在计算机上进行运算。每一个无向图都可以规定一个关联矩阵来表示，图的顶点对应此矩阵的行，图的边则与矩阵的列相对应。当一个顶点与边关联时，关联矩阵的相应元素为1，否则元素为零。在此基础上还可以建立回路矩阵、割集矩阵等等反映图的各种特征性质的矩阵。凭借矩阵理论的强有力的支持，图的矩阵表示理论成果不断涌现。特别应当提到的是，20世纪70年代出现了图的拟阵理论，它的发展对图的研究起到突出的促进作用。