第一章 柯尼斯堡七橋問題
幾何學中,處理距離的領域一直都很受人矚目。
然而除此之外,還有個領域幾乎從來沒人提到。
首先談及這個領域的萊布尼茲,
將其稱作「位置的幾何學」。
——李昂哈德‧歐拉(Leonhard Euler)
1.1 由梨
「最近哥哥給人的感覺好像不太一樣耶。」由梨說著。
今天是星期六的下午,這裡是我的房間。
就讀國中三年級的表妹,由梨來找我玩。
小時候就常和我一起玩的她,總是叫我《哥哥》。
綁著栗色馬尾,穿著牛仔褲的她,從我的書架上抽起了幾本書,慵懶地翻著閱讀。
「給人的感覺不一樣?」我反問她。
「嗯——總覺得有點過度冷靜,感覺很無聊喵。」
由梨一邊翻著書頁,一邊用著她獨特的貓語這麼說。
「是嗎?畢竟我也是高三生,也得有些考生的樣子啊。」
「不對喔。」她馬上否定了我的辯解。「哥哥以前不是都會和我玩很多不同的遊戲嗎?但是最近——應該說暑假結束後,就都沒怎麼理我了,明明都已經秋天了耶!」
說完後,由梨把手上的書啪一聲闔起。那是一本給高中生讀的數學書籍。雖然裡面有寫到一些比較難的內容,但由梨的話應該也讀得懂吧。
「明明都已經秋天了……不不不,就是因為已經是秋天了,身為考生,得開始認真讀書啊。再說,由梨也是考生不是嗎?」
「你是想說,國中三年級也該有點考生的樣子嗎喵?」
像這樣刁蠻的由梨,明年也要考高中了。她的成績並不差,所以應該能考進她想讀的學校——也就是我的高中吧。
「可是學校好無聊喔。」由梨邊嘆氣邊說。
啊……因為《那傢伙》已經轉學了是嗎?
1.2 一筆劃問題
「對了,由梨知道柯尼斯堡七橋問題嗎?」
「柯尼……什麼啊?」由梨回道。
「柯尼斯堡。這是一個城市的名字。這個城市內有七座橋。」
「這什麼啊,聽起來好像奇幻小說喔。『這個城市有七座神聖的橋,勇者們需通過這些橋,才能打敗龍——』」
「不是啦,不是那種故事。柯尼斯堡七橋問題是歷史上很有名的數學問題喔。」
「是這樣嗎?」
「也就是所謂的一筆劃問題喔!」
「是只能用一筆劃通過所有邊的那個嗎?」
「是啊。說得更仔細一點,就像這樣。柯尼斯堡這個城市內有河流通過,市內有七座橋,如圖所示。」
1 柯尼斯堡七橋問題
「橋不是只有六座而已嗎?a、b、c、d、e、f。」
「右下方還有第七座橋g不是嗎?陸地可分為A、B、C、D四塊,橋則有a、b、c、d、e、f、g七座。」
「嗯嗯,然後要用一筆劃走過所有的橋嗎?」
「沒錯。不管從A、B、C、D哪一塊陸地開始都行。在不重複經過同一條橋的條件下,能不能走過每一條橋呢?」
問題1-1(柯尼斯堡七橋問題)
在不重複經過同一條橋的條件下,能不能走過柯尼斯堡的七座橋呢?
「嗯——要走過所有的橋,但不能重複經過同一條橋。也就是說,每一條橋都要剛好走過一次對吧。」
「沒錯,條件就只有這些。」
「不對唷。」由梨裝模作樣地說著。「還得加上『不可以游過河』之類的條件不是嗎?『勇者啊,絕對不可以用游的過河喔!』」
「這當然囉。既然是和橋有關的問題,就不能作弊用游的過河嘛。」
「而且還要加上『只有一個人過橋』的條件才行啊!要是沒有這個條件的話,只要七個人分工,就可以馬上走完七座橋了!」
「好啦好啦。過橋的只有一個人,而且不能用直升機、火箭、挖地道之類的方法過河,當然也不能瞬間移動。」我邊搖頭邊說著,由梨總是追究這些詳細的條件。
「還有啊,一定要回到一開始出發的陸地嗎?」
「不,最後不一定要回到一開始出發的陸地喔。當然,回到一開始出發的陸地也沒關係。柯尼斯堡的七橋問題中,只要沒重複走過同一條橋,且每條橋都有走過就行了。」
「有辦法一筆劃走完這些橋嗎喵……嗯喵,我覺得應該可以耶。」
「那就試試看吧。」
由梨拿著自動鉛筆,花了好一段時間嘗試一筆劃走完這些橋。
「……」
「怎麼樣?完成了嗎?」
「不行!一定辦不到啦!你看,假設我們從A開始走,沿著a→e→f→b→c→d的順序過橋,最後就沒有路可以走了啊!這樣走不到g啦!」
1 沿著a→e→f→b→c→d的順序過橋(走不到g橋)
「是啊。走過橋d來到陸地B時,會發現連接陸地B的五座橋都已經走過了,沒辦法再從B走到其它陸地。然而,卻還沒走過橋g。」
「沒錯沒錯。」
「可是說不定還有其它走法啊。要不要試著從其它陸地開始走走看呢?」
「我試很多種走法了啦,就是不行!」
「即使你說試了很多種走法,卻不代表你試過所有的走法不是嗎?」
「是這樣沒錯啦……」由梨說著。「但一定不行啦!」
「那這就是由梨的猜想囉?」
「咦?」
「由梨為了解開柯尼斯堡七橋問題,用嘗試錯誤法試了許多次,認為不可能一筆劃走完所有的橋。但因為由梨沒有辦法以數學方法證明這真的不可能,故這只是《由梨的猜想》。」
「以數學方法證明……這有可能做到嗎?這是一筆劃問題喔?哥哥再怎麼擅於算式推導也派不上用場吧?」
「我們可以用圖來證明能不能用一筆劃走完所有橋喔,這還不需要用到算式。」
「圖?」
「沒錯。這裡說的圖並不是折線圖或圓餅圖那種統計用的圖表,而是《由邊連接起許多頂點的圖》。討論那些可以一筆劃走完的圖擁有哪些性質,也是一種數學喔。」
「由邊連接起許多頂點的圖……那是什麼啊,聽不懂耶。」
「拿柯尼斯堡的七橋問題當例子,陸地就相當於頂點,橋就相當於邊,故可得到下面這個圖。圖裡面,頂點之間《連接的方式》非常重要。你看,這張圖與橋的地圖是用同樣的方式連接起來的不是嗎?」
1 柯尼斯堡七橋問題的圖
「這完全不一樣吧。」
「沒這回事喔。仔細看,地圖上的A、B、C、D陸地分別對應到以圓表示的頂點。也就是將大片土地縮小變形,以一個頂點來表示。而a、b、c、d、e、f、g等橋則可以邊來表示。」
1 將地圖縮小變形成『圖』的樣子
「縮小變形……原來是這樣啊——」
「一筆劃問題中,不需要考慮《陸地面積多大》或《橋有多長》之類的問題。《各個陸地分別有哪些橋》才是重點。」
「原來如此啊。」由梨點了點頭。「那那那,邊可以彎曲嗎?」
「『圖』的邊可以彎曲喔。只要連接方式相同,邊有多長、有沒有彎曲都可以。地圖上的橋g雖然離得很遠,但只要注意不要改變與陸地的連接方式,就可以把g橋往中間拉。將『圖』的形狀整理好後,證明起來也比較容易喔。」
「我知道『圖』是什麼了。但是——該怎麼證明呢?」
「那,我們就一起來想想看這個一筆劃問題吧!」
「嗯!」
1.3 從簡單的圖開始
「從簡單的圖開始思考吧。假設圖1是由兩個頂點和一個邊組成的圖,這很明顯可以用一筆劃完成對吧。」
1 圖1
「當然囉。從A畫到B就畫完啦。」
「讓我們用一個箭頭來表示一筆劃的路徑吧。這條路徑是由A畫到B,A是開始的點,也稱作起點;B是結束的點,也稱作終點。」
2 圖1可一筆劃完成
「嗯嗯。」
「接著來考慮一個稍微複雜的圖吧。就是這個三角形的圖2。」
「這一點都不複雜啊!只要繞一圈就可以一筆劃畫完了嘛!」
1 圖2可一筆劃完成
「是啊。這樣畫的話,起點和終點都是A。」
「嗯,就是繞一圈嘛。」
「那,這個圖3可以一筆劃完成嗎?」
2 圖3可一筆劃完成嗎?
「不行!」
「為什麼呢?」
「因為,不管從哪個點開始,都不可能走過所有邊嘛!」
「沒錯。舉例來說,如果起點是A,接著會走到頂點B,再來可以走到頂點C。這樣就剩B和D間的這條邊還沒走過了,然而我們卻沒辦法走到這條邊上,這是為什麼呢?」
1 圖3沒辦法一筆劃完成(起點為A)
「因為到頂點C以後就沒辦法再移動了嘛。」
「是啊,沒辦法再移動了。因為頂點C只有一個邊,當我們從別的頂點走到頂點C時,就把這條邊用掉了,所以之後便沒辦法再度移動。A→B→D和A→B→C的情況相同,而且不管起點是頂點C還是頂點D都一樣。」
「嗯。」
「另外,將頂點B當作起點也沒辦法完成一筆劃。譬如說B→A,之後就沒辦法再移動了。」
2 圖4沒辦法一筆劃完成(起點為A)
「原來如此,如果頂點只有一個邊就不行!因為,如果從這個邊連到這個頂點,就沒辦法再走出來了嘛!」
「不不,這話說得太早囉。圖3確實如此,但某些情況下只有一個邊也是能一筆劃完成的喔。一開始我們提到的圖1,就是由頂點A與頂點B以一個邊連起來的不是嗎?這個圖可以用一筆劃完成。」
1 圖1僅由一個邊連起頂點A與頂點B,卻可以用一筆劃完成
「咦——那是因為這兩個點就是起點和終點嘛!只要用一個邊就可以連起來了啊!」
「沒錯!由梨發現了一個很大的重點囉!」
「發現?」
1.4 圖與次數
「剛才由梨說的話,就是一筆劃問題中很重要的發現喔!」
●考慮所有頂點的《連接邊數》
●將《起點與終點》及《中途點》分開考慮
「嗯……?」
「假設有一個可以一筆劃完成的圖。那麼,起點附近看起來應該會像這個樣子。假設我們只看與起點連接的邊,省略其它頂點的話,看起來就像這樣。」
2 可一筆劃完成的圖的起點
「這是……什麼意思啊?」
「注意看圖中與起點相連的邊。假設有七個邊與這個點相連,由於這個點是起點,故有一個邊會被當作《一筆劃的第一個邊》,其它邊則一定會以《進入邊》與《離開邊》的形式兩兩成對出現。這個頂點有三對這樣的邊。當然,圖不一樣的話,成對的連接邊數亦會不同,也有可能出現零個成對邊的情形。」
「這樣啊……」
「可一筆劃完成的圖中,起點有一條《一筆劃的第一個邊》,以及數條兩兩成對出現的邊。這表示與起點相連的邊有奇數個,也就是1、3、5、7……等。」
「哥哥啊,你好聰明喔!」
●可一筆劃完成的圖中,起點與終點相同時:
○起點:連接邊數為偶數
○終點:連接邊數為偶數
○中途點:連接邊數為偶數
●可一筆劃完成的圖中,起點與終點不同時:
○起點:連接邊數為奇數
○終點:連接邊數為奇數
○中途點:連接邊數為偶數
「原來如此……」由梨說。
「由此可發現一個很重要的問題。」
如果一個圖可以用一筆劃完成,
那麼圖中連接邊數為奇數的頂點會有幾個?
「有幾個……連接邊數為奇數的頂點,不就是零個或兩個嗎?如果起點和終點相同的話就是零個,不同的話就是兩個——啊!」
「想到了吧?」
「柯尼斯堡的七橋問題!奇數邊的頂點有四個!」
「沒錯,A有三個邊、B有五個邊、C有三個邊、D有三個邊,所以連接邊數為奇數的頂點有四個。」
1 連接邊數為3 2 連接邊數為5 3 連接邊數為3 4 連接邊數為3
5 連接邊數為奇數的頂點有四個
「有四個就不行了啊!」
「沒錯。如果一個圖可以用一筆劃完成的話,連接邊數為奇數的頂點只可能是零個或兩個。可是柯尼斯堡的七橋圖中有四個奇數點,所以——」
「沒辦法一筆劃完成!」
「是啊。我們絕對沒辦法用一筆劃走完由柯尼斯堡七橋簡化而成的圖。或者也可以說,柯尼斯堡的七橋問題無解。這樣就證明結束了!」
解答1-1(柯尼斯堡七橋問題)
如果可以用一筆劃走完由柯尼斯堡七橋簡化而成的圖,那麼這個圖中,連接邊數為奇數的頂點必須是零個或兩個。然而柯尼斯堡七橋的圖中,連接邊數為奇數的點卻有四個。因此,柯尼斯堡七橋問題無解。
「原來如此——!就算沒有每種情況都試過也可以證明耶!」由梨的眼睛閃閃發光。
「某個頂點的《連接邊數》又稱為該頂點的次數。所以,如果改用《次數》來描述我們對於一筆劃問題的已知性質的話,就像這樣。」
一筆劃問題的已知性質
如果一個圖可以用一筆劃完成,
那麼次數為奇數的頂點就是零個或兩個。
「孩子們!茶泡好囉!」媽媽的聲音傳進我的房間。
這也是數學嗎?
「小由梨啊,你又長高囉!」媽媽說。
「是這樣嗎?」由梨邊回答邊把手放在頭上。
「正處於成長期呢。」我附和著。
這裡是客廳。我和由梨正在享用媽媽端出來的藥草茶,至少由梨確實有在喝。
「怎麼樣?好喝嗎?」媽媽問。
「這是德國洋甘菊吧,覺得心情平靜多了——」由梨回答。
「由梨懂得真多耶。」
「你呢?覺得好喝嗎?」媽媽轉頭問我。
「等我喝了再說感想吧。對了由梨,剛才說的柯尼斯堡的七橋問題都懂了嗎?」
「嗯,都懂囉。」由梨回答。
「唉呀呀,又要開始講數學了嗎?」媽媽走回了廚房。
「第一個證明了柯尼斯堡七橋問題的是數學家歐拉。不過歐拉剛證明出這個問題時,似乎認為這個問題和數學沒什麼關係。」
「嗯嗯,歐拉的意見和由梨一樣呢。」
「在得意什麼啊……不過,後來歐拉在這個問題中發現了新的數學喔,還寫了一篇論文說明七橋問題的解法。」
「發現新的數學——是什麼意思啊?」
「柯尼斯堡七橋問題不只是單純的益智遊戲,還有著深入研究的價值。這個問題與幾何學很像,是處理圖形的數學。」
「像是正方形或圓形嗎?」
「沒錯,不過和一般的幾何學不太一樣。這是一種只要不改變連接方式,就算任意改變邊的長度也沒關係的幾何學。」
「啊,說的也是。畢竟剛才也把地圖整個縮小變形了。」
「沒錯沒錯。只要連接方式相同——或者說只要保留連接方式,就算將廣大陸地縮小成一個點也沒關係;把橋視為邊的話,也可以任意伸長或縮短。柯尼斯堡的七橋問題,就是這個《新幾何學的領域之一》的誕生契機喔。」
「新幾何學……」
「不過,歐拉的論文中,並沒有像剛才一樣用圖來表示。歐拉在十八世紀時寫下這篇論文,不過剛才的圖卻是十九世紀才出現喔。」
「就算不計算也能證明出答案的方法……」
「並不是完全沒有計算喔。我們不是有一一檢查次數是奇數還是偶數嗎?歐拉有在論文中引用了萊布尼茲的《位置幾何學》概念。歐拉是開創了這個數學領域的學者,不過確立這門學問在數學領域中地位的人,則是一位叫做龐加萊的數學家。龐加萊在論文中用《位置解析》的方法來探討這個領域的問題,最後將這個領域稱作位相幾何學,也可以稱作拓樸學。」
「拓樸學的話我有聽過。」
「拓樸學關注的就是《連接的方式》。」我說。
拓樸學關注的就是《連接的方式》。
幾何學中,處理距離的領域一直都很受人矚目。
然而除此之外,還有個領域幾乎從來沒人提到。
首先談及這個領域的萊布尼茲,
將其稱作「位置的幾何學」。
——李昂哈德‧歐拉(Leonhard Euler)
1.1 由梨
「最近哥哥給人的感覺好像不太一樣耶。」由梨說著。
今天是星期六的下午,這裡是我的房間。
就讀國中三年級的表妹,由梨來找我玩。
小時候就常和我一起玩的她,總是叫我《哥哥》。
綁著栗色馬尾,穿著牛仔褲的她,從我的書架上抽起了幾本書,慵懶地翻著閱讀。
「給人的感覺不一樣?」我反問她。
「嗯——總覺得有點過度冷靜,感覺很無聊喵。」
由梨一邊翻著書頁,一邊用著她獨特的貓語這麼說。
「是嗎?畢竟我也是高三生,也得有些考生的樣子啊。」
「不對喔。」她馬上否定了我的辯解。「哥哥以前不是都會和我玩很多不同的遊戲嗎?但是最近——應該說暑假結束後,就都沒怎麼理我了,明明都已經秋天了耶!」
說完後,由梨把手上的書啪一聲闔起。那是一本給高中生讀的數學書籍。雖然裡面有寫到一些比較難的內容,但由梨的話應該也讀得懂吧。
「明明都已經秋天了……不不不,就是因為已經是秋天了,身為考生,得開始認真讀書啊。再說,由梨也是考生不是嗎?」
「你是想說,國中三年級也該有點考生的樣子嗎喵?」
像這樣刁蠻的由梨,明年也要考高中了。她的成績並不差,所以應該能考進她想讀的學校——也就是我的高中吧。
「可是學校好無聊喔。」由梨邊嘆氣邊說。
啊……因為《那傢伙》已經轉學了是嗎?
1.2 一筆劃問題
「對了,由梨知道柯尼斯堡七橋問題嗎?」
「柯尼……什麼啊?」由梨回道。
「柯尼斯堡。這是一個城市的名字。這個城市內有七座橋。」
「這什麼啊,聽起來好像奇幻小說喔。『這個城市有七座神聖的橋,勇者們需通過這些橋,才能打敗龍——』」
「不是啦,不是那種故事。柯尼斯堡七橋問題是歷史上很有名的數學問題喔。」
「是這樣嗎?」
「也就是所謂的一筆劃問題喔!」
「是只能用一筆劃通過所有邊的那個嗎?」
「是啊。說得更仔細一點,就像這樣。柯尼斯堡這個城市內有河流通過,市內有七座橋,如圖所示。」
1 柯尼斯堡七橋問題
「橋不是只有六座而已嗎?a、b、c、d、e、f。」
「右下方還有第七座橋g不是嗎?陸地可分為A、B、C、D四塊,橋則有a、b、c、d、e、f、g七座。」
「嗯嗯,然後要用一筆劃走過所有的橋嗎?」
「沒錯。不管從A、B、C、D哪一塊陸地開始都行。在不重複經過同一條橋的條件下,能不能走過每一條橋呢?」
問題1-1(柯尼斯堡七橋問題)
在不重複經過同一條橋的條件下,能不能走過柯尼斯堡的七座橋呢?
「嗯——要走過所有的橋,但不能重複經過同一條橋。也就是說,每一條橋都要剛好走過一次對吧。」
「沒錯,條件就只有這些。」
「不對唷。」由梨裝模作樣地說著。「還得加上『不可以游過河』之類的條件不是嗎?『勇者啊,絕對不可以用游的過河喔!』」
「這當然囉。既然是和橋有關的問題,就不能作弊用游的過河嘛。」
「而且還要加上『只有一個人過橋』的條件才行啊!要是沒有這個條件的話,只要七個人分工,就可以馬上走完七座橋了!」
「好啦好啦。過橋的只有一個人,而且不能用直升機、火箭、挖地道之類的方法過河,當然也不能瞬間移動。」我邊搖頭邊說著,由梨總是追究這些詳細的條件。
「還有啊,一定要回到一開始出發的陸地嗎?」
「不,最後不一定要回到一開始出發的陸地喔。當然,回到一開始出發的陸地也沒關係。柯尼斯堡的七橋問題中,只要沒重複走過同一條橋,且每條橋都有走過就行了。」
「有辦法一筆劃走完這些橋嗎喵……嗯喵,我覺得應該可以耶。」
「那就試試看吧。」
由梨拿著自動鉛筆,花了好一段時間嘗試一筆劃走完這些橋。
「……」
「怎麼樣?完成了嗎?」
「不行!一定辦不到啦!你看,假設我們從A開始走,沿著a→e→f→b→c→d的順序過橋,最後就沒有路可以走了啊!這樣走不到g啦!」
1 沿著a→e→f→b→c→d的順序過橋(走不到g橋)
「是啊。走過橋d來到陸地B時,會發現連接陸地B的五座橋都已經走過了,沒辦法再從B走到其它陸地。然而,卻還沒走過橋g。」
「沒錯沒錯。」
「可是說不定還有其它走法啊。要不要試著從其它陸地開始走走看呢?」
「我試很多種走法了啦,就是不行!」
「即使你說試了很多種走法,卻不代表你試過所有的走法不是嗎?」
「是這樣沒錯啦……」由梨說著。「但一定不行啦!」
「那這就是由梨的猜想囉?」
「咦?」
「由梨為了解開柯尼斯堡七橋問題,用嘗試錯誤法試了許多次,認為不可能一筆劃走完所有的橋。但因為由梨沒有辦法以數學方法證明這真的不可能,故這只是《由梨的猜想》。」
「以數學方法證明……這有可能做到嗎?這是一筆劃問題喔?哥哥再怎麼擅於算式推導也派不上用場吧?」
「我們可以用圖來證明能不能用一筆劃走完所有橋喔,這還不需要用到算式。」
「圖?」
「沒錯。這裡說的圖並不是折線圖或圓餅圖那種統計用的圖表,而是《由邊連接起許多頂點的圖》。討論那些可以一筆劃走完的圖擁有哪些性質,也是一種數學喔。」
「由邊連接起許多頂點的圖……那是什麼啊,聽不懂耶。」
「拿柯尼斯堡的七橋問題當例子,陸地就相當於頂點,橋就相當於邊,故可得到下面這個圖。圖裡面,頂點之間《連接的方式》非常重要。你看,這張圖與橋的地圖是用同樣的方式連接起來的不是嗎?」
1 柯尼斯堡七橋問題的圖
「這完全不一樣吧。」
「沒這回事喔。仔細看,地圖上的A、B、C、D陸地分別對應到以圓表示的頂點。也就是將大片土地縮小變形,以一個頂點來表示。而a、b、c、d、e、f、g等橋則可以邊來表示。」
1 將地圖縮小變形成『圖』的樣子
「縮小變形……原來是這樣啊——」
「一筆劃問題中,不需要考慮《陸地面積多大》或《橋有多長》之類的問題。《各個陸地分別有哪些橋》才是重點。」
「原來如此啊。」由梨點了點頭。「那那那,邊可以彎曲嗎?」
「『圖』的邊可以彎曲喔。只要連接方式相同,邊有多長、有沒有彎曲都可以。地圖上的橋g雖然離得很遠,但只要注意不要改變與陸地的連接方式,就可以把g橋往中間拉。將『圖』的形狀整理好後,證明起來也比較容易喔。」
「我知道『圖』是什麼了。但是——該怎麼證明呢?」
「那,我們就一起來想想看這個一筆劃問題吧!」
「嗯!」
1.3 從簡單的圖開始
「從簡單的圖開始思考吧。假設圖1是由兩個頂點和一個邊組成的圖,這很明顯可以用一筆劃完成對吧。」
1 圖1
「當然囉。從A畫到B就畫完啦。」
「讓我們用一個箭頭來表示一筆劃的路徑吧。這條路徑是由A畫到B,A是開始的點,也稱作起點;B是結束的點,也稱作終點。」
2 圖1可一筆劃完成
「嗯嗯。」
「接著來考慮一個稍微複雜的圖吧。就是這個三角形的圖2。」
「這一點都不複雜啊!只要繞一圈就可以一筆劃畫完了嘛!」
1 圖2可一筆劃完成
「是啊。這樣畫的話,起點和終點都是A。」
「嗯,就是繞一圈嘛。」
「那,這個圖3可以一筆劃完成嗎?」
2 圖3可一筆劃完成嗎?
「不行!」
「為什麼呢?」
「因為,不管從哪個點開始,都不可能走過所有邊嘛!」
「沒錯。舉例來說,如果起點是A,接著會走到頂點B,再來可以走到頂點C。這樣就剩B和D間的這條邊還沒走過了,然而我們卻沒辦法走到這條邊上,這是為什麼呢?」
1 圖3沒辦法一筆劃完成(起點為A)
「因為到頂點C以後就沒辦法再移動了嘛。」
「是啊,沒辦法再移動了。因為頂點C只有一個邊,當我們從別的頂點走到頂點C時,就把這條邊用掉了,所以之後便沒辦法再度移動。A→B→D和A→B→C的情況相同,而且不管起點是頂點C還是頂點D都一樣。」
「嗯。」
「另外,將頂點B當作起點也沒辦法完成一筆劃。譬如說B→A,之後就沒辦法再移動了。」
2 圖4沒辦法一筆劃完成(起點為A)
「原來如此,如果頂點只有一個邊就不行!因為,如果從這個邊連到這個頂點,就沒辦法再走出來了嘛!」
「不不,這話說得太早囉。圖3確實如此,但某些情況下只有一個邊也是能一筆劃完成的喔。一開始我們提到的圖1,就是由頂點A與頂點B以一個邊連起來的不是嗎?這個圖可以用一筆劃完成。」
1 圖1僅由一個邊連起頂點A與頂點B,卻可以用一筆劃完成
「咦——那是因為這兩個點就是起點和終點嘛!只要用一個邊就可以連起來了啊!」
「沒錯!由梨發現了一個很大的重點囉!」
「發現?」
1.4 圖與次數
「剛才由梨說的話,就是一筆劃問題中很重要的發現喔!」
●考慮所有頂點的《連接邊數》
●將《起點與終點》及《中途點》分開考慮
「嗯……?」
「假設有一個可以一筆劃完成的圖。那麼,起點附近看起來應該會像這個樣子。假設我們只看與起點連接的邊,省略其它頂點的話,看起來就像這樣。」
2 可一筆劃完成的圖的起點
「這是……什麼意思啊?」
「注意看圖中與起點相連的邊。假設有七個邊與這個點相連,由於這個點是起點,故有一個邊會被當作《一筆劃的第一個邊》,其它邊則一定會以《進入邊》與《離開邊》的形式兩兩成對出現。這個頂點有三對這樣的邊。當然,圖不一樣的話,成對的連接邊數亦會不同,也有可能出現零個成對邊的情形。」
「這樣啊……」
「可一筆劃完成的圖中,起點有一條《一筆劃的第一個邊》,以及數條兩兩成對出現的邊。這表示與起點相連的邊有奇數個,也就是1、3、5、7……等。」
「哥哥啊,你好聰明喔!」
●可一筆劃完成的圖中,起點與終點相同時:
○起點:連接邊數為偶數
○終點:連接邊數為偶數
○中途點:連接邊數為偶數
●可一筆劃完成的圖中,起點與終點不同時:
○起點:連接邊數為奇數
○終點:連接邊數為奇數
○中途點:連接邊數為偶數
「原來如此……」由梨說。
「由此可發現一個很重要的問題。」
如果一個圖可以用一筆劃完成,
那麼圖中連接邊數為奇數的頂點會有幾個?
「有幾個……連接邊數為奇數的頂點,不就是零個或兩個嗎?如果起點和終點相同的話就是零個,不同的話就是兩個——啊!」
「想到了吧?」
「柯尼斯堡的七橋問題!奇數邊的頂點有四個!」
「沒錯,A有三個邊、B有五個邊、C有三個邊、D有三個邊,所以連接邊數為奇數的頂點有四個。」
1 連接邊數為3 2 連接邊數為5 3 連接邊數為3 4 連接邊數為3
5 連接邊數為奇數的頂點有四個
「有四個就不行了啊!」
「沒錯。如果一個圖可以用一筆劃完成的話,連接邊數為奇數的頂點只可能是零個或兩個。可是柯尼斯堡的七橋圖中有四個奇數點,所以——」
「沒辦法一筆劃完成!」
「是啊。我們絕對沒辦法用一筆劃走完由柯尼斯堡七橋簡化而成的圖。或者也可以說,柯尼斯堡的七橋問題無解。這樣就證明結束了!」
解答1-1(柯尼斯堡七橋問題)
如果可以用一筆劃走完由柯尼斯堡七橋簡化而成的圖,那麼這個圖中,連接邊數為奇數的頂點必須是零個或兩個。然而柯尼斯堡七橋的圖中,連接邊數為奇數的點卻有四個。因此,柯尼斯堡七橋問題無解。
「原來如此——!就算沒有每種情況都試過也可以證明耶!」由梨的眼睛閃閃發光。
「某個頂點的《連接邊數》又稱為該頂點的次數。所以,如果改用《次數》來描述我們對於一筆劃問題的已知性質的話,就像這樣。」
一筆劃問題的已知性質
如果一個圖可以用一筆劃完成,
那麼次數為奇數的頂點就是零個或兩個。
「孩子們!茶泡好囉!」媽媽的聲音傳進我的房間。
這也是數學嗎?
「小由梨啊,你又長高囉!」媽媽說。
「是這樣嗎?」由梨邊回答邊把手放在頭上。
「正處於成長期呢。」我附和著。
這裡是客廳。我和由梨正在享用媽媽端出來的藥草茶,至少由梨確實有在喝。
「怎麼樣?好喝嗎?」媽媽問。
「這是德國洋甘菊吧,覺得心情平靜多了——」由梨回答。
「由梨懂得真多耶。」
「你呢?覺得好喝嗎?」媽媽轉頭問我。
「等我喝了再說感想吧。對了由梨,剛才說的柯尼斯堡的七橋問題都懂了嗎?」
「嗯,都懂囉。」由梨回答。
「唉呀呀,又要開始講數學了嗎?」媽媽走回了廚房。
「第一個證明了柯尼斯堡七橋問題的是數學家歐拉。不過歐拉剛證明出這個問題時,似乎認為這個問題和數學沒什麼關係。」
「嗯嗯,歐拉的意見和由梨一樣呢。」
「在得意什麼啊……不過,後來歐拉在這個問題中發現了新的數學喔,還寫了一篇論文說明七橋問題的解法。」
「發現新的數學——是什麼意思啊?」
「柯尼斯堡七橋問題不只是單純的益智遊戲,還有著深入研究的價值。這個問題與幾何學很像,是處理圖形的數學。」
「像是正方形或圓形嗎?」
「沒錯,不過和一般的幾何學不太一樣。這是一種只要不改變連接方式,就算任意改變邊的長度也沒關係的幾何學。」
「啊,說的也是。畢竟剛才也把地圖整個縮小變形了。」
「沒錯沒錯。只要連接方式相同——或者說只要保留連接方式,就算將廣大陸地縮小成一個點也沒關係;把橋視為邊的話,也可以任意伸長或縮短。柯尼斯堡的七橋問題,就是這個《新幾何學的領域之一》的誕生契機喔。」
「新幾何學……」
「不過,歐拉的論文中,並沒有像剛才一樣用圖來表示。歐拉在十八世紀時寫下這篇論文,不過剛才的圖卻是十九世紀才出現喔。」
「就算不計算也能證明出答案的方法……」
「並不是完全沒有計算喔。我們不是有一一檢查次數是奇數還是偶數嗎?歐拉有在論文中引用了萊布尼茲的《位置幾何學》概念。歐拉是開創了這個數學領域的學者,不過確立這門學問在數學領域中地位的人,則是一位叫做龐加萊的數學家。龐加萊在論文中用《位置解析》的方法來探討這個領域的問題,最後將這個領域稱作位相幾何學,也可以稱作拓樸學。」
「拓樸學的話我有聽過。」
「拓樸學關注的就是《連接的方式》。」我說。
拓樸學關注的就是《連接的方式》。