最后更新: 2025-04-21 09:12 查看: 268 次反馈刷题

哥尼斯堡（Könisberg）七桥问题

## 图论问题起源

18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如概述图）。有个人提出一个问题：**一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。** 这个问题当时难住了很多人。
 ![图片](/uploads/2025-01/bd6991.jpg){width=500px}

## 欧拉的解决方案
后来大数学家欧拉把它转化成一个几何问题——**一笔画问题**。 
 ![图片](/uploads/2025-04/9ee584.jpg)
 1736 年，年仅 29 岁的瑞士数学家欧拉（Enler）就哥尼斯堡七桥问题发表了图论的首篇论文，论证了哥尼斯堡七桥问题无解。欧拉指出，如果从 A 岸出发，A 岸有 3 座桥，经过其中的一座桥离开，再经过另一座桥回来，因为要求经过每座桥一次且仅仅一次，所以在经过第 3 座桥离开之后就无法回来；处在其他地点出发的情形也是相似的。因此哥尼斯堡七桥问题无解，欧拉也因此成为了图论的创始人。

为了叙述方便及今后的需要，我们先提出几个概念，本节后面会继续研究这个问题。
图 $G=(V, E)$ 的一条通路，就是边的一个序列（ $e_{i_1} e_{i_2} \cdots$ $e_{i_m}$ ），使得 $e_{i_j}$ 和 $e_{i_{j+1}}$ 首尾衔接；也可以是顶点序列（ $v_{i_1} v_{i_2} \cdots$ $\left.v_{m+1}\right)$ ，使得 $v_{i_j}$ 和 $v_{i_{i+1}}$ 相邻．通路长度定义为通路中所含边的条数。

如果一条通路首尾重合，则称它为**闭路**或**回路**．在一条通路中，若每一边不重复出现，则称它为**简单通路**．同样，在一条回路中，若它的每一边不重复出现，则称该回路为**简单回路**．

在一条通路中，若每个顶点仅出现一次，则称该通路为基本通路或链。在一条回路中，除首尾两个顶点外，每个顶点只出现一次，称该回路是基本回路或圈。显然，基本通路必是简单通路，基本回路必是简单回路，反之却未必成立。

图 $G$ 中两个顶点 $v_i$ 和 $v_j$ 之间，如果存在一条通路，则称 $v_i, v_j$ 是**连通**的．若 $G$ 中任意两个顶点均连通，则称 $G$ 是连通图，否则称**非连通**图。

经连通图 $G$ 的每条边一一次而且仅仅一次的回路（通路）称为**欧拉回路**（欧拉通路），具有欧拉回路的图称为**欧拉图**。

图论中，欧拉最早给出关于图的奇次顶点的个数问题的定理：对任意的图 $G$ ，奇次顶点的个数一定是偶数。解决七桥问题就是要判别它是否存在欧拉图．有如下的判别定理：一个连通图 $G$ 是欧拉图当且仅当 $G$ 的每个顶点次数是偶数。

我们把七桥问题这样画成图：把两岸和小岛缩成点，桥化成边，就得到了下图
 ![图片](/uploads/2025-04/588bee.jpg){width=300px}

它的四个顶点都是奇顶点．即它不能一笔画成，故经过桥一次且仅一次而回到原地是不可能的．

在我国民间也早就流传＂一笔画＂的游戏．长期实践经验使人们知道，如果图中所有点是偶次顶点，可以任意取一点做起始点，一笔画完，回到始点．如果图中只有两个奇次顶点，那么选择一个奇次顶点做起始点，一笔画完，终点为另一个奇次结点

## 图论的发展

图论的发展大致可以分三个阶段：从 1736 年到 19 世纪中叶是图论的萌芽阶段，在这一阶段，围绕着游戏提出了许多图论的问题。从 19 世纪中叶到 1936 年，
图论作为一个数学分支开始形成。在这一阶段，一方面，诸如四色问题、哈密顿图等的图论问题大量出现；另一方面，也出现了以图为工具解决问题的成果。1936
年，Konig 总结了图论 200 年来的研究成果，出版了系统论述图论的第一部专著《有限图与无限图理论》。在 1936 年以后则是图论的全面发展阶段。一方面，计算
机科学的发展为图论的发展提供了计算工具；另一方面，现代科学技术的发展需要借助图论来描述和解决各类课题中的各种关系，因为图论提供了一个自然的结
构，由此产生的数学模型几乎适合于所有科学（自然科学和社会科学）领域，只要这个领域研究的主题是“对象”与“对象”之间的关系。

## 图论的作用
图论的本质是将**复杂关系抽象为节点与边**，图论在公交线路规划、地铁网络设计、实时交通拥堵分析中占据重要作用。 比如在地图导航里，从A点到B点，有很多路径可以行走，通过图论，**可以在“距离最近、耗时最短、费用最低”等多个维度要求下，找到最优解**。

![图片](/uploads/2025-04/dfee49.jpg)

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：没有了

下一篇：有向图无向图

本文对您是否有用？有用 (0) 无用 (0)