定义

特点

历史起源

著名理论

学科分支

推荐书籍

定义

中文名：图论

图论：英文名：Graph Theory，它是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有某种关系。

特点

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

历史起源

关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。后来，德国自然科学家基希霍夫对于电网络的研究导致他发现了图论的基本概念和定理；英国数学家凯莱为了计数有机化学中的同分异构而考虑到树；英国数学家哈密顿提出了一个与图论有关的难题；不久又出现了著名的四色猜想，这些工作都促进了图论的产生和发展。在20世纪内，图论中又有大量的新发现，并被应用到许多领域。

图论起源于著名的柯尼斯堡七桥问题。18世纪，在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸连接起来，如图1所示，A,B,C,D表示陆地：问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽象分析法将这个问题化为第一个图论问题，即把每一块陆地用一个点来代替，将每一座桥用连接相应的两个点的一条线来代替，从而相当于得到一个“图”（如图2），欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以按某种方式走遍（即一笔画）的判定法则。这项工作使欧拉成为图论（及拓扑学）的创始人。

1847年，德国学者基希霍夫在研究物理问题时建立了树的理论。他用一类线性方程组来描述一个电网络的每一条支路中和环绕每一个回路的电流。他像数学家一样抽象地思考问题：用一个只由点和线组成的相应的组合结构来代替原来的电网络，而并不指明每条线所代表的电器元件的种类。事实上，他把每个电网络用一个基本图来代替。为了解相应的方程组，他用一种结构方法指出，只要考虑一个图的任何一个“生成树”所决定的那些独立圈就够了。他的方法现已成为图论中的标准方法。

图3表示一个电网络N及基希霍夫为它设计的基本图G和一个生成树T。

1857年，英国数学家凯莱从事计数有给定的碳原子数n的饱和碳氢化合物 的同分异构物（如图4所示），独立地提出了树的概念。凯莱把这个问题抽象地叙述为：求有P个点的树的数目，其中每个点的度等于1或4，树上的点对应一个氢原子或一个碳原子。凯莱的工作是图的计数理论的起源。法国数学家若尔当在1869年作为一个纯数学对象独立地发现了树，他并不知道树与现代的化学学说有关。

图4 最小的饱和碳氢化合物

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

在图论的历史中，还有一个最著名的问题——四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。四色猜想有一段有趣的历史（见四色问题）。每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。

著名理论

20世纪以来，图论不断地发展和完善，并获得广泛的应用。1936年，德国社会心理学家莱温把图论应用于心理学研究。他提出，一个人的“生活空间”可以用一张平面地图来代表，其中各个区域代表一个人的各种活动。他所处理的实际上是图，其观点影响了当时的一批心理学家。他们提出了图的一种心理学解释，其中点代表人，而线代表人与人之间的关系，括爱、恨、交往与支配等。他们对图论有一些独到的发现。1960年，荷兰—美国物理学家乌伦贝克用图论来研究统计力学，他以点来代表分子，两个点间的连线表示分子间的相互作用。在杨振宁和李政道的工作中也有类似的解释，他们以点表示欧氏空间中的小立方体，每一个立方体可能被一个分子占有或不被分子占有，两个点的连线则表示两个空间都被占有。图论还被应用于概率论中的马尔可夫链的研究。例如，南斯拉夫—美国数学家弗勒引进了有向图：点代表事件，有向线表示两个事件直接相继有正的概率；有向图的一种类似的表示法还出现在数值分析的矩阵求逆和特征值计算之中，美国数学家瓦尔加在1962年建立的一种对方阵构造有向图的方法与处理马尔可夫链的方法相类似。在线性规划和运筹学的各领域中，也利用图论的方法来研究网络上流的形式，1962年以来已有许多工作。在纯粹数学中，图论被用来研究拓扑学中的单纯复形，美国数学家维布伦在20世纪20-30年代就做出了先驱性的贡献。他把一个图定义为维数等于1或0的一个复形，1维单形是一条线，只由点组成的复形是0维的。除了这些特殊情形外，每一个图都是一个1维复形。正因为这个原因，在1936年出现的第一本图论的书（柯尼希著）的副标题是“线复形的组合拓扑学”。

学科分支

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

推荐书籍

书 名：

1.图论 Graph theory 第3版

作　者： （德）迪斯特尔　著

出 版 社： 世界图书出版公司

出版时间： 2008-3-1 字　数： 版次： 1 页　数： 410 印刷时间： 2008-3-1 开　本： 16开 印次： 1 纸　张： 胶版纸

I S B N ： 9787506291859

所属分类： 图书 >> 自然科学 >> 数学 >> 代数 数论 组合理论

内容简介:Many authors begin their preface by confidently describing how their book arose. We started this project so long ago, and our memories are so weak, that we could not do this truthfully. Others begin by stating why they decided to write. Thanks to Freud, we know that unconscious reasons can be as important as conscious ones, and so this seems impossible, too. Moreover, the real question that should be addressed is why the reader should struggle with this text.

2.代数图论：

作者:Chris Godsi Gordon Royle

·出版社：世界图书出版公司

·页码：439 页

·出版日期：2004年04月

·ISBN：7506266180

·条形码：9787506266185

·版本：第1版

·装帧：平装

·开本：24开 Pages Per Sheet

内容简介：

Many authors begin their preface by confidently describing how their book arose. We started this project so long ago, and our memories are so weak, that we could not do this truthfully. Others begin by stating why they decided to write. Thanks to Freud, we know that unconscious reasons can be as important as conscious ones, and so this seems impossible, too. Moreover, the real question that should be addressed is why the reader should struggle with this text.

3.图论及其应用 J.A.邦迪 U.S.R.