楔子:一筆畫問題

by MRPC

在影片的最開始,數學老師(周曉涵飾)對同學解說了七橋問題,也就是大家熟知的一筆畫問題。這其實牽涉到一個近代蓬勃發展且應用廣泛,只要有在使用網路便一定身受其惠,但大眾卻很少聽過的數學領域:圖論

題目內容

左圖是否能一筆畫完?

數學原理

關於一筆畫問題,最早是由大數學家歐拉在面對七橋問題時所解決。其給出的結論如下:

一個連通的圖要能夠一筆畫畫完,
當且僅當其由奇數條路交會而成的交叉點個數
是零個或兩個。

證明其實並不困難,大家可以參照此連結

解題過程

透過上述歐拉的定理,要判斷一個圖能不能一筆畫非常容易:數一數每個交叉點有幾條路就可以了!在這個圖中,每個交叉點的路數如下:

注意到這裡是奇數的點有四個,不是兩個也不是零個,因此由前面的定理得知,這個圖必不能一筆畫。

延伸應用

一筆畫問題是圖論能處理的問題之一,但圖論可不是只能處理一筆畫這樣的益智問題而已唷!

由於圖是不同的點與之間的連線,類似於不同地點與之間的道路,因此自然而然可以拿來處理像是交通等網絡問題。例如像Uber、DHL之類的物流業,基本上都需要面對像是旅行推銷員問題這種「尋找最佳路徑」的問題。

而除此之外,還有一些比較難以想像到的應用,例如: