七橋問題

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

先來說一個歷史問題：

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

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

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

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

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

瑞士鼎鼎有名的數學家

李昂哈德·尤拉(Leonhard Euler)

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

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

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

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

參考文獻：