主題
Search

哥尼斯堡橋問題


Koenigsberg bridges
KoenigsbergBridges

哥尼斯堡橋問題提出,位於普雷格爾河上的哥尼斯堡市(左圖;Kraitchik 1942),該城市曾是德國的一部分,現在被稱為加里寧格勒,是俄羅斯的一部分,其七座橋樑是否可以在一次旅行中全部遍歷,且不重複走,並附加要求旅行在開始的地方結束。這等同於詢問具有四個節點和七條邊的多重圖(右圖)是否具有歐拉回路。尤拉(1736)對這個問題給出了否定回答,這代表了圖論的開端。

KoenigsbergBridgesNew
KoenigsbergBridgesNewCircuit

從實際角度來看,J. Kåhre 觀察到橋樑 bbdd 不再存在,並且橋樑 aacc 現在是一座橋樑,它從 A 上方透過,中間有一個樓梯通往 A。即便如此,使用現代哥尼斯堡橋樑,在節點 A, B, C, 和 D 上仍然沒有歐拉回路,但存在尤拉路徑(右圖)。右圖說明了一個尤拉路徑的例子,其中,作為最後一步,可以攀登從 Aaacc 的樓梯,不僅覆蓋所有橋樑,還覆蓋所有臺階。


另請參閱

歐拉回路, 圖環, 多重圖, 可追蹤圖, 單筆畫迴路

使用 探索

參考文獻

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. "哥尼斯堡橋問題。" 來自 -- Wolfram 網路資源。 https://mathworld.tw/KoenigsbergBridgeProblem.html

主題分類