图论起源于18世纪，1736年欧拉利用图论的思想解决了哥尼斯堡七桥问题以来，图论经历了漫长的发展道路，它被当成是数学家的智力游戏，解决了很多著名的难题。如，迷宫问题、匿门博弈问题、棋盘上马的路线问题、四色问题、哈密顿环球旅行问题以及中国邮递员问题等，曾经吸引了众多的学者。图论中许多的概念和定理的建立都与解决这些问题有关。1847年克希霍夫第一次把图论用于电路网络的拓扑分析，开创了图论面向实际应用的成功先例。此后，随着实际的需要和科学技术的发展，在近半个世纪内，图论得到了迅猛的发展，已经成了数学领域中最繁茂的分支学科之一。尤其在电子计算机问世后，图论的应用范围更加广泛，在解决众多自然科学、社会科学以及工程技术领域中国的问题时，扮演者越来越重要的角色，特别受到工程界和数学界的重视，称为解决许多实际问题的基本工具之一。在计算机科学中，它在形式语言、数据结构、分布式系统、操作系统及数据库研究中均有很重要的应用。