圖論學家一直無法證明某個半個世紀前提出的數(shù)學難題,,現(xiàn)在俄羅斯的數(shù)學家用三頁論文終結了該猜想,。 圖論,研究對象是所謂圖的理論,。一般來說,,簡單的圖,包含兩個部分:點和線,。點,,就是抽象的點,可以指代各種對象,,比如說某個人,,某個地點,某個性質(zhì)……如果上述對象之間存在聯(lián)系,,比如說兩個人相互認識,,則可以在對應的點之間連上線。因為線本身也是指代抽象的屬性,,所以它不具備幾何特征,,如長度,平直性等,。 由于圖只包括最純粹的對象(點)和關系(線),,所以從研究對象的抽象層次上來說,圖論本身是最基本的數(shù)學領域之一。而圖的染色理論,,則是圖論中最富有活力的領域之一,。 把一群人看作是點,把每個人按性別加以區(qū)分,,就可以看做是對點的染色,。具體的染色,只不過是某個符號(如用紅色指代♀),,所以數(shù)學家真正關心的是相關結構,,而不是顏色本身(所以也可以用數(shù)字0和1來染色)。 一般來說,,數(shù)學家還喜歡給問題加上某些限制——如要求互相有線連接的點,,具有不同的顏色。一個圖滿足此類要求,,所用到的最少的顏色數(shù)目,,被稱為染色數(shù)。最有名的染色問題,,就是所謂的四色猜想:任何一張(簡單)地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色,。在這里,可以把每個國家都看做是一個點,,兩個領土接壤的國家,,則對應點之間連上一條線。這樣就把實際問題,,轉(zhuǎn)化為了抽象的圖論染色問題——地圖的染色數(shù)不會大于4,。好吧,如果你想知道的話,,我們已經(jīng)利用計算機證明了四色猜想,。 或許是發(fā)現(xiàn)不夠虐心,數(shù)學家又在不同的圖之間建立了諸如笛卡爾積一類的運算,。1966年,,現(xiàn)任南卡羅來納州克萊姆森大學教授的Stephen Hedetniemi在他的博士論文中猜測:為兩個圖的笛卡爾積圖進行染色,其染色數(shù)小于等于兩個圖的染色數(shù)中最小者,。 數(shù)十年來,,數(shù)學家構造了不少支持猜想的證據(jù),,因為普遍認為猜想應該是真的,。隨著時間流逝,苦于無法徹底證明,,該猜想已然成為了領域里知名的重要猜想,。很多數(shù)學家推測,需要發(fā)明出更高級的理論工具,,才能解決這一難題,。 普林斯頓大學的Noga Alon說:“人們普遍認為它是真的,,但證明非常困難?!?/p> 但現(xiàn)在,,俄羅斯數(shù)學家Yaroslav Shitov通過三頁的論文表明,有些猜想之所以十分困難,,主要是因為它們本來就是錯的,! Shitov現(xiàn)在已通過一個清晰、簡單的反例證明,,Hedetniemi的推斷是錯誤的,。 如果你對此問題,以及Shitov的精巧構造十分感興趣的話,,可以在此下載論文的PDF文件,。 |
|
來自: 挑燈看劍r7wtm5 > 《數(shù)理化》