图论［GraphTheory］是数学的一个分支.它以图为研究对象.图论中的图是由若

　　干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的

　　某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系

　　.

　　图论本身是应用数学的一部份,因此,历史上图论曾经被好多位数学家各自独立地

　　建立过.关於图论的文字记载最早出现在欧拉1736年的论着中,他所考虑的原始问

　　题有很强的实际背景.

　　图论起源於着名的柯尼斯堡七桥问题.在柯尼斯堡的普莱格尔河上有七座桥将河中

　　的岛及岛与河岸联结起来,如下图所示,A、B、C,D表示陆地.

　　问题是要从这四块陆地中任何一块开始,通过每一座桥正好一次,再回到起点.然

　　而无数次的尝试都没有成功.欧拉在1736年解决了这个问题,他用抽象分析法将这

　　个问题化为第一个图论问题：即把每一块陆地用一个点来代替,将每一座桥用联接

　　相应的两个点的一条线来代替,从而相当於得到一个「图」（如下图）.欧拉证明

　　了这个问题没有解,并且推广了这个问题,给出了对於一个给定的图可以某种方式

　　走遍的判定法则.这项工作使欧拉成为图论［及拓扑学］的创始人.

　　1859年,英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体,它的

　　20个顶点标出世界着名的20个城市,要求游戏者找一条沿着各边通过每个顶点刚好

　　一次的闭回路,即「绕行世界」.用图论的语言来说,游戏的目的是在十二面体的

　　图中找出一个生成圈.这个问题后来就叫做哈密顿问题.由於运筹学、计算机科学

　　和编码理论中的很多问题都可以化为哈密顿问题,从而引起广泛的注意和研究.

　　在图论的历史中,还有一个最着名的问题——四色猜想.这个猜想说,在一个平面

　　或球面上的任何地图能够只用四种颜色来着色,使得没有两个相邻的国家有相同的

　　颜色.每个国家必须由一个单连通域构成,而两个国家相邻是指它们有一段公共的

　　边界,而不仅仅只有一个公共点.四色猜想有一段有趣的历史.每个地图可以导出

　　一个图,其中国家都是点,当相应的两个国家相邻时这两个点用一条线来连接.所

　　以四色猜想是图论中的一个问题.它对图的着色理论、平面图理论、代数拓扑图论

　　等分支的发展起到推动作用.

　　图论的广泛应用,促进了它自身的发展.20世纪40-60年代,拟阵理论、超图理论

　　、极图理论,以及代数图论、拓扑图论等都有很大的发展