http://www.math15.com/wiki/index.php?doc-view-839.html

图论是研究由线连接的点集的理论。点集中的点称为结点，连接某些点对的线称为边。一些由结点及边构成的图称为线图。在线图中，结点的位置分布和边的长短曲直都可以任意描画，这并不改变实际问题的性质。我们关心的是它有多少个结点，在哪些结点间有边相连，以及整个线图具有的某些特性。

线图可以用来表示和研究一个系统的结构及它的性质。例如，若结点表示火车站，边表示火车站间的铁路线，我们便可以通过相应的线图来研究铁路网络中货物的运输问题。又如，若用结点表示电网络中的节点，用边表示节点间的电气元件，我们就能利用相应的线图对电网络进行拓扑分析。

图论起源很早，远在十八世纪就出现了图论问题，如著名的哥尼斯堡（Konigsberg）七桥问题就是当时很有名的图论问题。1736年，瑞士数学家列昂哈德·欧拉（Leonhard Euler）发表了图论的首篇论文，解决了哥尼斯堡七桥问题。由于欧拉的研究奠定了图论的基础，目前一般均公认欧拉为图论之父。

在19世纪和20世纪的前半期，图论中主要研究一些游戏问题，诸如迷宫问题、博弈问题和棋盘上马的行走路线等等。

1847年，克希荷夫应用图论的方法来分析电网络，奠定了现代网络理论的基础，这就是电工原理中的克希荷夫电流定律和克希荷夫电压定律，这是第一次将图论应用于工程技术领域。1857年，凯莱在试算饱和碳化氢的同分异性体时，提出了“树”的概念。在这段时间，对图论的发展另有两个里程碑。一个是莫别斯约于1840年提出的“四色猜想”，这个问题是说至多用四种不同颜色给平面或球面上的地图着色，就可以使互相接壤的国家由不同的颜色来区分（这个问题当时称为猜想，直到1976年才由美国人阿佩尔（K. Appel）和海肯（W. Haken>）用计算机运行1200多小时加以证明）。另一个是威廉·哈密尔顿爵士（Sir William Hamilton）于1859提出了周游世界问题。此后约有半个世纪研究图论的人不多，直到1936年哥尼格发表了第一本图论专著，从此图论成为一门独立的学科。

当应用图论来解决实际问题时，不管是电网络的分析、电路设计、数据的结构或社会科学方面的问题，几乎需要引出复杂的图形，这些图形，如果没有计算机的帮助实际上是不大可能分析的。近几十年来，图论盛行于世，高速数字计算机的出现是其原因之一。

图论的应用范围很广，它不但能应用于自然科学，也能应用于社会科学。它非但广泛应用于电信网络、电力网络、运输能力、开关理论、编码理论、控制论、反馈理论、随机过程、可靠性理论、化学化合物的辨认、计算机的程序设计、故障诊断、人工智能、印制电路板的设计、图案识辩、地图着色、情报检索，也应用于诸如语言学、社会结构、经济学、运筹学、兵站学、遗传学等等方面。

图论作为一个数学分支，有一套完整的体系和广泛的内容，这里只介绍图论的初步知识，其目的在于今后对计算机有关学科的学习和研究时，可以以图论的基本知识作为工具。