北京时时彩平台官网下载
當前位置: 主頁 > 百科 > 數學計算 >
0 Comments

計算機程序與數字

發布于:2019-01-09  |   作者:http://www.ufkgq.com.cn  |   已聚集:人圍觀

想象有一個網絡,其中每一個節點通向其他節點的邊數相同,此外,每一個節點也可以經其他任一節點到達,路徑可能是經由許多不同節點的曲折路徑。這里的問題是,是否可以為這種網絡的邊標以不同顏色,以便根據前述那種簡單的指令組合到達目的地。

1970年,兩位數學家猜想,符合一項技術條件的網絡,確實可以用這種方式著色(這項技術條件是,圖中所有的回路——也就是會回到同一節點的環——的邊數,必須“互質”。這表示若有一個回路包含的邊數是3,該圖形中其他回路的邊數必定不能是6、9、12……)。

然而,這兩位研究者無法證明他們的猜想,這個問題幾乎被遺忘了近40年。偶爾有數學家找到了特定網絡的部分解答,直到最近,這項猜想是否正確仍然是個未知數。

2008年,這項猜想被證實的消息出人意料地傳遍網絡。入籍以色列的數學家特拉特曼(Avraham Trahtman)證明所有滿足該技術條件的圖形都能以上述方式著色。這項成果不僅僅是在純數學上取得的智識成就,或許它更大的意義是證明了計算機科學的實用重要性。它說明,在某些情況下,數據輸入的錯誤或其他干擾很可能無關緊要。就像在街道迷宮中迷路的駕駛員打電話求助時不需要知道自己的確切位置一樣,計算機程序可以借助簡單地重復指令,從不正確狀態回到正確狀態。

當然,證明存在著一種著色方式能讓駕駛員找到通過街道網絡的正確路徑只是第一步,下一步是找出需要用哪幾種顏色為哪些邊著色。最近,兩位法國數學家提出一套計算機算法,據說能在一段合理的時間內,計算出網絡的適當著色方式。


標簽:                   喜歡:收藏
北京时时彩平台官网下载