主题
Search

哥尼斯堡桥问题


Koenigsberg bridges
KoenigsbergBridges

哥尼斯堡桥问题提出,位于普雷格尔河上的哥尼斯堡市(左图;Kraitchik 1942),该城市曾是德国的一部分,现在被称为加里宁格勒,是俄罗斯的一部分,其七座桥梁是否可以在一次旅行中全部遍历,且不重复走,并附加要求旅行在开始的地方结束。这等同于询问具有四个节点和七条边的多重图(右图)是否具有欧拉回路。欧拉(1736)对这个问题给出了否定回答,这代表了图论的开端。

KoenigsbergBridgesNew
KoenigsbergBridgesNewCircuit

从实际角度来看,J. Kåhre 观察到桥梁 bbdd 不再存在,并且桥梁 aacc 现在是一座桥梁,它从 A 上方通过,中间有一个楼梯通往 A。即便如此,使用现代哥尼斯堡桥梁,在节点 A, B, C, 和 D 上仍然没有欧拉回路,但存在欧拉路径(右图)。右图说明了一个欧拉路径的例子,其中,作为最后一步,可以攀登从 Aaacc 的楼梯,不仅覆盖所有桥梁,还覆盖所有台阶。


另请参阅

欧拉回路, 图环, 多重图, 可追踪图, 单笔画回路

使用 Wolfram|Alpha 探索

参考文献

Biggs, N. L.; Lloyd, E. K.; and Wilson, R. J. 图论 1736-1936。 牛津,英格兰:牛津大学出版社,1976年。Bogomolny, A. "图。" http://www.cut-the-knot.org/do_you_know/graphs.shtml.Chartrand, G. "哥尼斯堡桥问题:欧拉图导论。" §3.1 in 图论入门。 纽约:多佛出版社,pp. 51-66, 1985.Euler, L. "关于位置几何问题的解法。" Comment. Acad. Sci. U. Petrop. 8, 128-140, 1736. Reprinted in Opera Omnia Series Prima, Vol. 7. pp. 1-10, 1766.Harary, F. 图论。 阅读,马萨诸塞州:艾迪生-韦斯利出版社,pp. 1-2, 1994.Kåhre, J. "哥尼斯堡桥问题已解决。" http://www.matheory.info/konigsberg/.Kraitchik, M. §8.4.1 in 数学娱乐。 纽约:W. W. 诺顿出版社,pp. 209-211, 1942.Newman, J. "列昂哈德·欧拉与哥尼斯堡桥。" 科学美国人 189, 66-70, 1953.Pappas, T. "哥尼斯堡桥问题 & 拓扑学。" 数学之乐。 圣卡洛斯,加利福尼亚州:Wide World Publ./Tetra, pp. 124-125, 1989.Skiena, S. 离散数学实现:使用 Mathematica 的组合数学和图论。 阅读,马萨诸塞州:艾迪生-韦斯利出版社,p. 192, 1990.Steinhaus, H. 数学快照,第三版。 纽约:多佛出版社,pp. 256-259, 1999.Wilson, R. J. "穿过哥尼斯堡的欧拉路径。" 图论杂志 10, 265-275, 1986.

引用为

韦斯坦因,埃里克·W. "哥尼斯堡桥问题。" 来自 MathWorld-- Wolfram 网络资源。 https://mathworld.net.cn/KoenigsbergBridgeProblem.html

主题分类