Graph [1] 七橋問題


Posted by clins210 on 2020-11-17

七橋問題

在資料結構與演算法中皆有介紹「圖論」的章節
那麼,究竟圖論是什麼呢?

先來說一個歷史問題:

柯尼斯堡七橋問題(Seven Bridges of Königsberg)

在當時東普魯士的柯尼斯堡(今日的俄羅斯加里寧格勒)市區中,有一條河叫做普列戈利亞河,河中心有兩個小島。小島與河的兩岸一共有七條橋連接。在所有橋都只能走一遍的前提下,如何才能把這個地方所有的橋都走過一次呢?

當我們把問題先「圖像化」再「抽象化」之後,可以將問題以下圖方式呈現:

而在將問題抽象畫之後,所謂的「七橋問題」,其實就是「一筆畫」問題,那麼

我們是否能找到一個方式只使用一筆就走完所有的線,且不重複呢?

瑞士鼎鼎有名的數學家

李昂哈德·尤拉(Leonhard Euler)

在1735年提出
「這個問題無法找到好的方式解決它。」
且在隔年的論文中,順帶的解釋了「連通圖」的解法

給定一個連通圖,若有超過兩個以上有奇數通路的頂點,此圖便無法一筆走完。
若有兩個奇數通路頂點,最少走完此圖的路徑為個數的一半。

此後許多數學家開始陸陸續續研究此類問題,解析在不同狀況下、對應的解法為何。
而這些解析方法,則被綜稱為「圖論」。

關鍵字:圖論graph、拓樸topology、最佳化、演算法

參考文獻:

  1. https://zh.wikipedia.org/wiki/柯尼斯堡七桥问题
  2. http://www-users.math.umn.edu/~reiner/Classes/Konigsberg.pdf
  3. http://eulerarchive.maa.org
  4. Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40

#graph #Eluer #math #topology







Related Posts

18. Mediator

18. Mediator

如何使用 Python 程式操作 Excel 試算表

如何使用 Python 程式操作 Excel 試算表

維修 Mac 蝶式鍵盤的過程

維修 Mac 蝶式鍵盤的過程


Comments