路線著色問題是圖論中最著名的猜想之一。
這個猜想認為,可以繪製一張“萬能地圖”,指導人們到達某一目的地,不管他們原來在什麼位置。而這一似乎違反邏輯的命題可以運用於製圖、計算機科學、電網路分析等諸多領域。
路線著色問題是猶太裔美國數學家和計算機專家班傑明·韋斯和他在IBM工作的同事羅伊·艾德勒於1970年首先提出來的。他們認為,如果路線的數量有限,人們應該能畫出一張地圖,標上不同的顏色,把人引導到某一目的地。路線著色問題可以通俗解釋為,“一個人來到他從未造訪過的小鎮上,駕著車到處尋找他朋友的家,即使連路名都沒有。朋友說,別擔心,他會指示他如何到達,先向左,再向右,接著向左……”
38年來,許多傑出的數學家都致力於解決這一路線著色問題,而解決這一難題要涉及到圖論、群論、矩陣論、機率論、代數學、拓撲學、數值分析等多個數學分支。然而,數學奇才特雷特曼只花了一年時間就解決了這道難題。以色列著名數學家斯圖爾特·馬戈利斯對美聯社說,“在數學界,我們都在談論這一美好的結果,多么美好啊,而且是那么出乎意料。用外行話來說,這是完全反直覺的,但它確實管用。”
為了與同行交流,特雷特曼於去年底在網上的一個數學文獻庫里貼出他的解題方法。在對特雷特曼的方法深入研究後,數學界為之震驚了,並公認他已經掌握了破解路線著色謎題的要領和訣竅。今年2月,他進一步完善了自己的解題方法。最近,世界上眾多著名學術刊物編輯部得知此事後,紛紛向他約稿,但他最終決定把論文發表在即將出版的《以色列數學雜誌》上。
今年63歲的特雷特曼出生在俄羅斯葉卡捷琳堡,1972年在烏拉爾州立大學獲得數學博士學位,之後在烏拉爾科技大學任教。但是猶太人身份使他在工作中受到歧視和排擠。儘管特雷特曼在1992年移居以色列之前就是一位頗有造詣的數學家,但他剛到以色列時身無分文,為養家餬口他經常去教會領救濟品,後來在好心人的介紹下,他成了一名值夜班的保全員,但生活仍然十分艱苦。1995年,特雷特曼被聘為巴爾伊蘭大學的教員。當年把他招進巴爾伊蘭大學的馬戈利斯回憶說,“我第一次見到他時,他穿著守夜人的制服,不修邊幅,衣服很髒。”
特雷特曼在數學上的這一成果極為令人矚目,英國《獨立報》為此事專門發表了一篇題為“身無分文的移民成了數學超級明星”的文章,給予了高度的評價。
以色列人也為特雷特曼取得的成就感到無比的驕傲。特拉維夫電視台中斷了正常的節目播放,以第一時間發布了這一重大訊息,連中東其他國家的主流媒體也就此事作了大篇幅的報導。
得知特雷特曼解決這一難題的訊息後,多年從事路線著色問題研究的加拿大數學家喬爾·弗里德曼說,“路線著色問題的解決令數學共同體非常興奮。”讀過特雷特曼論文的中國數學家和語言學家周海中教授認為,特雷特曼的數學知識非常淵博,解題方法十分巧妙,這一謎題得到破解,無疑是數學史上的一個華彩樂章。
相關詞條
-
圖著色問題
圖著色問題(Graph Coloring Problem, GCP) 又稱著色問題,是最著名的NP-完全問題之一。道路著色問題(Road Colorin...
簡介 路線著色問題 算法 -
思維盛宴:拓展思維的益智遊戲
絕頂聰明了!目錄第一輯 觀察思考謎題 觀察思考能力是一種依靠直覺來... 12.鋸木板 13.給圓圈著色 14.骰子構圖 15.失蹤... 71.九點連線 72.陳景潤的難題 73.巧畫路線 74.九道門...
圖書信息 內容簡介 目錄 前言 -
思維的瑜伽:牛津劍橋學生最愛玩的益智遊戲
,將引領你一步步探索思維的樂趣。目錄第一輯 觀察思考謎題 1.迷... 12.鋸木板 13.給圓圈著色 14.骰子構圖 15.失蹤... 72.陳景潤的難題 73.巧畫路線 74.九道門 75....
圖書信息 內容簡介 目錄 -
CTR
3ds資料這款全新的掌機將具有裸視觀察立體畫面的功能,並能兼容目前DSi和DS系列的所有遊戲軟體功能。任天堂3DS預定2010年...
3ds資料 詳細資訊 N3DS特性 -
殺手7
全方位隨意變向。這樣特別的操作,加上極其另類的畫面和著色,可能會讓很多... 路線選擇右搖桿 換鏜R1 進入第一人稱主視角R2 切換鏡頭第一人稱主視角...謎題,紅色點狀物代表該處有關鍵道具,S代表可存檔的Harman’s...
商品信息 故事背景 人物介紹 遊戲介紹 遊戲攻略 -
《殺手7》
轉身□鍵 發動特殊技能△鍵 地圖左搖桿 路線選擇右搖桿 換鏜R1 進入...公用謎題,紅色點狀物代表該處有關鍵道具,S代表可存檔的Harman’s...
遊戲簡介 系統介紹 畫面音樂 系統設定 -
ctr[3DS生產批號]
3ds資料這款全新的掌機將具有裸視觀察立體畫面的功能,並能兼容目前DSi和DS系列的所有遊戲軟體功能。任天堂3DS預定2010年...
3ds資料 詳細資訊 N3DS特性