图论(Graph Theory)是组合数学(MSC05)的一个分支,它研究由顶点(或节点)以及连接这些顶点的边所构成的图的数学属性和问题。图论在计算机科学、网络理论、社会学以及生物学等许多领域都有重要应用。
图论的起源通常被追溯到1736年,当时的莱昂哈德·欧拉解决了著名的“哥尼斯堡七桥问题”。这个问题涉及是否能够在不重复经过任一桥的情况下走遍连接哥尼斯堡市中心四块陆地的七座桥。欧拉的解决方法被视为图论的诞生。
在19世纪,图论作为一个独立的研究领域在数学家中逐渐受到关注,尤其是在解决拓扑学问题和四色问题(即任何平面地图是否可以用四种颜色来着色,使得相邻区域不同色)时。
在20世纪,图论的研究得到了极大的扩展。随着计算机科学的兴起,图论在算法理论、网络分析和数据库结构设计等领域扮演了重要角色。 图论还被应用于经济学、生物学(如在研究蛋白质相互作用的网络)、社会科学(如社会网络分析)等多个领域。