讓你不迷路的萬能地圖

撰文|賴加翌

我想大家都有這樣的經驗:和朋友約在一個地點見面,但他卻在附近迷了路,最後只好打電話給你,告訴你當下的位置請你指路。但是如果人在國外就比較麻煩了,他可能看不懂路標和店名。

這時候,如果當地的街道都被染成特定的顏色,他只要按著固定的模式走就能到目的地,那不是方便嗎?你可以在電話裡跟他說:「沿著藍色那條路走到交叉口之後,換走紅色那條,再走到下一個交叉口時,繼續走紅色那條。紅色走完接藍色,藍色一直走到交叉口換紅色,紅色走到一個交叉口繼續走紅色,這樣就可以到了。」講白一點就是說,他只要不斷照著「藍—紅—紅」的模式走下去,就算他不清楚自己現在哪裏,最後還是能到指定地點。

或許單純用說的很難想像,不如直接看下圖。按照「藍—紅—紅」的模式重複三次,不管你人在哪裏,都能到黃色的點;而按照「藍—藍—紅」,的模式重複三次,則一定會到綠點。

圖片出處: wikipedia

道路著色的問題,是圖論中非常有名的問題之一。由節點和連接節點的邊所構成的圖形,可以衍伸成現實世界中遇到的系統。比如街道的交叉口可以看做是節點,而街道看成是邊。網際網路的世界裡,節點就是路由器,邊是路由器之間的連結。以航空網路來說,節點就是機場,而邊是機場到機場之間的航程。

令人好奇的是,每個點和邊構成的圖形都存在像這樣理想的「萬能地圖」嗎?只要將邊上色,就可以照著簡單重複的指令到達目的地?1970年班傑明.懷斯和羅伊.阿德勒最早提出這個問題,本來只是要找地圖,順便想到要設計一個電腦的自動除錯程式。想不到自己提出的問題,花了好幾年還沒辦法證明。因為這個想法相當有趣,引起一些數學家的關注,前前後後出了幾篇相關論文。

雖然問題的敘述看似單純,卻在數學界懸而不解將近40年,直到阿夫拉罕.塔克特曼出現,他證明任一個點和編構成的圖形只要完成某些特定條件,都能以「萬能地圖」般的方式著色。這個證明不只是數學上的成就,在計算機領域也有特別意義。等於是說明了某些情況下,錯誤數據和干擾不影響結果,就像迷路的朋友就算不知道自己位置,只要依據重複指令,都能到達目的地。

 

參考資料: 

  1. Vojtěch Vorel, &Adam Roman. Complexity of road coloring with prescribed reset words. Journal of Computer and System Sciences. 2016
  2. A.Roman, &M. Drewienkowski. A complete solution to the complexity of Synchronizing Road Coloring for non-binary alphabets. Information and Computation. 242, 383-393. 2015

加入好友

1,179 人瀏覽過