数学中“图论”的起源与发展 好的，我们开始学习“图论”这一词条。图论是数学中研究 图 的结构及其性质的学科。这里的“图”并非指图表或函数图像，而是由若干 顶点 以及连接这些顶点的 边 所组成的离散结构。我们将从它的经典起源讲起，逐步深入到其现代发展。 第一步：问题的起源——哥尼斯堡七桥问题 图论的诞生通常被追溯到一个具体而著名的问题： 哥尼斯堡七桥问题 。 背景 ：18世纪初，普鲁士的哥尼斯堡城（今俄罗斯加里宁格勒）有一条河穿过市区，河中有两个岛，岛与河岸之间由七座桥连接。当地居民流行一个消遣：能否从任意一点出发，恰好 每座桥只走一次 ，最后回到起点？ 欧拉的贡献 ：1736年，数学家莱昂哈德·欧拉接触到了这个问题。他没有像其他人一样去尝试所有可能的路径，而是进行了 关键抽象 。 抽象化过程 ： 欧拉意识到，岛和河岸的 具体形状和大小 是无关紧要的。他将四块陆地抽象为四个 点 （顶点）。 连接陆地的七座桥抽象为连接这些点的七条 线 （边）。 这样，整个城市地图就被抽象成了一个只包含点和连接线的 图 。 问题的解决与一般化 ：欧拉不仅证明了哥尼斯堡七桥问题 无解 ，更重要的是，他提出并证明了一个普遍的定理： 一个连通图（所有部分都连在一起）存在这样一种“一笔画”回路（后来称为“欧拉回路”）的充要条件是，每个顶点都与偶数条边相连。 意义 ：欧拉的工作标志着图论研究的开端。他成功地将一个具体的几何散步问题，转化为了一个只关心 连接关系 的组合问题，奠定了图论作为研究“关系”而非“度量”的数学分支的基础。 第二步：从游戏到严肃数学——早期的发展 在欧拉之后近一个世纪，图论的发展相对缓慢，主要与一些数学游戏和谜题相关。 哈密顿问题 ：1859年，威廉·汉密尔顿爵士提出了一个与欧拉回路不同的问题：能否找到一个路径， 访问一个正十二面体的每个顶点恰好一次 ，并最终回到起点？这个问题被称为“哈密顿回路”问题。它与欧拉回路（关注边）形成对比，关注的是 顶点 的遍历。 四色问题 ：1852年，弗朗西斯·古德里提出： 任何一张地图，只需四种颜色，就能保证有共同边界的国家颜色不同 。这个问题看似简单，却极其困难。它本质上也是一个图论问题，因为地图可以抽象为图（国家是顶点，有共同边界则连边，这种图称为“对偶图”）。四色问题悬而未决百余年，直到1976年才依靠计算机辅助得以证明，极大地刺激了对图着色理论的研究。 这些早期问题表明，图论最初源于对离散对象排列和连接规律的朴素好奇。 第三步：基础的确立——树的图论与矩阵表示 19世纪末至20世纪上半叶，图论开始形成系统的理论。 凯莱与树 ：数学家亚瑟·凯莱在研究有机化学中碳氢化合物同分异构体的计数问题时，独立地研究了 树 这种特殊的图（无环的连通图）。他利用图论方法成功计算了不同碳原子数的烷烃 \( C_ n H_ {2n+2} \) 的同分异构体数量，展示了图论在化学中的强大应用。 基尔霍夫与电路网络 ：1847年，古斯塔夫·基尔霍夫在研究 electrical 电路网络时，发展出了 电路定律 。他的分析依赖于图论的思想，即电路可以抽象为由支路（边）和节点（顶点）组成的图，并引入了“生成树”的概念来求解线性方程组。 矩阵表示 ：20世纪初，人们开始用 矩阵 来表示图，这为图论注入了强大的代数工具。 邻接矩阵 ：一个 n x n 的矩阵，如果顶点 i 和 j 之间有边相连，则矩阵的 (i, j) 元素为1，否则为0。这个矩阵包含了图的所有连接信息。 关联矩阵 ：表示顶点与边的关联关系。 通过研究这些矩阵的特征值、行列式等代数性质，可以推导出图的组合性质，形成了 代数图论 这一重要分支。 第四步：现代图论的诞生与蓬勃发展 20世纪30年代后，图论迎来了爆炸式增长，成为一门核心的数学学科。 极值图论 ：保罗·埃尔德什是这一领域的核心人物。极值图论研究的问题是：在给定的图必须满足某种条件（如不含某种特定子图）下，其边数的最大或最小值是多少？一个典型例子是 托兰定理 ，它精确地回答了：如果一个 n 个顶点的图不包含一个具有 k+1 个顶点的完全子图，那么它最多可以有多少条边？ 随机图论 ：同样由埃尔德什和阿尔弗雷德·莱利开创，研究当图的边是以某种概率随机生成时，图的整体性质（如连通性、出现特定子图的概率）如何变化。他们发现了许多性质存在一个 阈值函数 ，当概率超过这个阈值时，图几乎必然具有该性质。 图论算法的兴起 ：随着计算机科学的出现，图论找到了巨大的应用舞台。许多计算问题本质上都是图论问题。 最短路径算法 （如Dijkstra算法）：用于GPS导航、网络路由。 最小生成树算法 （如Kruskal算法）：用于网络设计、聚类分析。 网络流理论 ：用于运输优化、匹配问题。 图的深度分类 ： 平面图 ：能否在平面上画出一个图使得边互不交叉？库拉托夫斯基定理给出了一个简洁的判定条件。 完美图 ：这是一类具有优美性质的图，其着色数等于其最大团的大小。 强完美图定理 经过数十年努力才被证明，是对图结构深刻理解的里程碑。 总结 图论的演进路径清晰地展示了数学概念的发展模式：从一个具体的趣味问题（七桥问题）出发，通过 抽象化 提炼出核心数学结构（图）。随后，在解决其他学科（化学、电路）问题的过程中得到 应用和深化 ，并与其他数学分支（代数、概率） 交叉融合 ，最终在新技术（计算机科学）的推动下，成长为一门内容丰富、应用广泛的 现代数学核心分支 。今天，从社交网络到生物信息学，从芯片设计到推荐系统，图论都是理解和优化复杂系统关系的关键工具。