一部圖論發(fā)展史：從柯尼斯堡七橋到改變世界的現(xiàn)代數(shù)學(xué)語言

1736年的普魯士柯尼斯堡城中，一個(gè)有趣的消遣游戲在當(dāng)?shù)鼐用裰辛餍校涸谶@座被普列戈利亞河分割的城市里，能否找到一條路線，一次性走遍連接兩座小島與兩岸的七座橋，且每座橋只走一次？

圖源：維基

很多人嘗試過，但沒有一人能走通，也沒人知道為什么。當(dāng)這個(gè)問題傳到大數(shù)學(xué)家歐拉耳朵里后，他完成了一次漂亮的思想飛躍，徹底解決了這個(gè)問題。

歐拉拋棄了所有無用的物理表象——島嶼的面積、橋梁的長度，所有與連接關(guān)系無關(guān)的屬性，通通不重要。他剝離了度量信息，直擊問題的拓?fù)浜诵模?strong>連通關(guān)系，將陸地簡化為點(diǎn)，橋梁簡化為線。

憑借這一思維跨越，歐拉發(fā)表了論文《與位置幾何有關(guān)的一個(gè)問題的解》(Solutio Problematis ad Geometriam Situs Pertinentis)。他不僅通過嚴(yán)格的邏輯證明了七橋路線的不存在，更由此奠定了數(shù)學(xué)中一個(gè)全新分支——圖論(Graph Theory)的基礎(chǔ)。

歐拉的這篇論文，連同范德蒙在1771年發(fā)表的關(guān)于騎士巡邏(Knight's tour)問題的研究，共同推進(jìn)了由萊布尼茨開啟的位置分析(Analysis situs)探索。

歐拉這種只看連通關(guān)系、不看幾何形狀的抽象思考方式，對(duì)后世數(shù)學(xué)產(chǎn)生了深遠(yuǎn)影響。

unset unset剝離表象的位置分析unset unset

幾十年后，柯西與西蒙·安托萬·讓·呂利耶等數(shù)學(xué)家繼續(xù)沿著這一方向探索。歐拉本人發(fā)現(xiàn)了凸多面體的一個(gè)基本性質(zhì)，后來被稱為歐拉示性數(shù)(Euler's characteristic)公式：對(duì)于任何凸多面體，頂點(diǎn)數(shù) 、邊數(shù) 與面數(shù) 永遠(yuǎn)滿足恒等式： 。柯西等人將其推廣到了更一般的情況。

這種研究物體在連續(xù)變形下保持不變的性質(zhì)的學(xué)問，最終演化成了今天大名鼎鼎的拓?fù)鋵W(xué)(Topology)。圖論與拓?fù)鋵W(xué)的發(fā)展始終緊密交織，相互滋養(yǎng)。在1860年至1930年間，拓?fù)鋵W(xué)的獨(dú)立發(fā)展通過若爾當(dāng)、庫拉托夫斯基以及惠特尼的工作，反向滋養(yǎng)了圖論。

19世紀(jì)中葉，推動(dòng)兩門學(xué)科共同演進(jìn)的另一股力量來自現(xiàn)代代數(shù)工具的引入。物理學(xué)家基爾霍夫在研究電路時(shí)，獨(dú)立發(fā)展了用圖表示電路結(jié)構(gòu)的方法，并由此提出了現(xiàn)代電子工程領(lǐng)域的基礎(chǔ)法則——基爾霍夫電路定律(Kirchhoff's circuit laws)。

而在同一時(shí)期，當(dāng)約翰·本尼迪克特·李斯廷剛剛將拓?fù)鋵W(xué)這一概念引入學(xué)術(shù)界時(shí)，凱萊在研究微分算子的代數(shù)結(jié)構(gòu)時(shí)，開始關(guān)注一類特殊的圖——樹(Trees)。凱萊敏銳地發(fā)現(xiàn)，這些沒有回路的樹，與化學(xué)分子中原子的內(nèi)在連接網(wǎng)絡(luò)存在著高度的結(jié)構(gòu)同構(gòu)性。他將關(guān)于樹的成果與當(dāng)時(shí)的化學(xué)成分研究結(jié)合起來，這種數(shù)學(xué)與化學(xué)的跨界結(jié)合，為枚舉圖論(Enumerative graph theory)的誕生奠定了重要基礎(chǔ)。

這一領(lǐng)域隨后在波利亞于1935至1937年間發(fā)表的奠基性成果中得到確立，并于1959年被德布魯因推廣，同時(shí)也為圖論留下了許多源自化學(xué)的專有名詞。

隨著理論的不斷成熟，圖論的系統(tǒng)化構(gòu)建也被提上日程。1936年，柯尼格出版了世界上第一本系統(tǒng)的圖論教材。

1969年，哈拉里出版了該領(lǐng)域的權(quán)威教科書。特別是哈拉里的著作，打破了學(xué)科間的專業(yè)壁壘，使得數(shù)學(xué)家、化學(xué)家、電氣工程師以及社會(huì)科學(xué)家得以在統(tǒng)一的理論框架下探討網(wǎng)絡(luò)結(jié)構(gòu)問題。哈拉里更將該書的全部版稅捐出，資助設(shè)立了波利亞獎(jiǎng)(Pólya Prize)。

unset unset四色問題驅(qū)動(dòng)的理論突破unset unset

如果說七橋問題是圖論的起點(diǎn)，那么四色問題就是推動(dòng)這門學(xué)科發(fā)生質(zhì)變的催化劑。

不妨想象一張空白的世界地圖。如果要給不同的國家上色，并且保證任何兩個(gè)相鄰（有共同邊界而非僅一個(gè)公共點(diǎn)）的國家顏色都不一樣，你最少需要幾支彩筆？

德摩根寫給哈密頓的信件，首次提到四色猜想。現(xiàn)存于都柏林三一學(xué)院。DeMorganFourColour

1852年，弗加斯·格思里在給英國地圖上色時(shí)，經(jīng)過觀察發(fā)現(xiàn)，四種顏色就足夠了，并提出了這個(gè)著名的猜想。這就是后來困擾數(shù)學(xué)界一個(gè)多世紀(jì)的四色問題(Four color problem)。同年，德·摩根在寫給哈密頓的一封信中，留下了關(guān)于該問題的最早書面記錄。

這個(gè)猜想看似簡單，證明過程卻異常艱難。一個(gè)多世紀(jì)以來，無數(shù)頂尖數(shù)學(xué)家都曾嘗試證明這個(gè)猜想，卻都未能成功，期間誕生了諸如凱萊、肯普等人的錯(cuò)誤證明。肯普曾發(fā)表過一份仗著直覺而學(xué)術(shù)上看似優(yōu)雅的證明，在被數(shù)學(xué)界普遍接受十余年后，才被希伍德指出存在致命的邏輯漏洞。

然而，這些艱難的嘗試并非徒勞。為了解決四色問題，數(shù)學(xué)家們發(fā)展出了許多新方法。泰特將四色問題轉(zhuǎn)化為圖的因子分解問題(Factorization problems)，這一重新表述衍生出了一類新問題，并由彼得森與柯尼格進(jìn)行了重點(diǎn)研究；希伍德、拉姆齊與雨果·哈德維格則將問題推廣到了嵌入在任意虧格(Genus)曲面上的圖著色問題。

與此同時(shí)，拉姆齊在著色理論上的工作，特別是圖蘭于1941年發(fā)表的關(guān)于圖的邊數(shù)與特定子圖存在性關(guān)系的研究，共同開創(chuàng)了圖論的另一重要分支——極值圖論(Extremal graph theory)。

unset unset機(jī)器輔證與隨機(jī)演化：走向復(fù)雜系統(tǒng)unset unset

四色問題的最終解決，引發(fā)了長久的數(shù)學(xué)爭議。

1969年，海因里希·赫施首先發(fā)表了一種利用計(jì)算機(jī)求解該問題的方法。1976年，阿佩爾和哈肯正式宣布證明了四色定理。他們的核心策略深層依賴于海因里希·赫施提出的放電法(Discharging Method)，將無限復(fù)雜的地圖歸納為 種基本構(gòu)型，并借助當(dāng)時(shí)的大型計(jì)算機(jī)進(jìn)行了全面的窮舉驗(yàn)證。

這是人類歷史上第一個(gè)主要依靠計(jì)算機(jī)完成的重要數(shù)學(xué)定理證明。由于人類無法逐一檢查所有構(gòu)型，這個(gè)證明在當(dāng)時(shí)引發(fā)了巨大爭議，許多數(shù)學(xué)家拒絕接受這種無法被手動(dòng)驗(yàn)證的證明方式。直到二十年后，羅伯遜、西摩、桑德斯和托馬斯將構(gòu)型數(shù)量優(yōu)化至 種，提供了一個(gè)更為簡潔的證明版本，相關(guān)爭議才逐漸平息。

但這還不是故事的終點(diǎn)。

2005 年 1 月互聯(lián)網(wǎng)拓?fù)渚植繄D（數(shù)據(jù)：opte.org）

就在人們以為圖論的研究對(duì)象僅限于靜態(tài)的確定性圖(Deterministic Graphs)時(shí)，埃爾德什與雷尼將概率論的思想引入進(jìn)來了。他們改變了傳統(tǒng)的研究視角，不再局限于單一圖的靜態(tài)拓?fù)洌菍Ｗ⒂谘芯繄D連通性的漸近概率。他們思考：當(dāng)頂點(diǎn)數(shù)量趨向無窮時(shí)，在給定頂點(diǎn)之間以特定概率隨機(jī)生成連線，圖的連通性等整體性質(zhì)將呈現(xiàn)何種漸近規(guī)律？就這樣，隨機(jī)圖論(Random graph theory)作為一個(gè)全新分支破土而出。

今天圖論已經(jīng)滲透到現(xiàn)代科學(xué)的幾乎每一個(gè)角落，計(jì)算機(jī)科學(xué)家用來設(shè)計(jì)算法與數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，生物學(xué)家研究基因調(diào)控網(wǎng)絡(luò)與蛋白質(zhì)相互作用，社會(huì)學(xué)家分析人際關(guān)系與信息傳播，也被工程師用于設(shè)計(jì)通信網(wǎng)絡(luò)和交通系統(tǒng)。

就這樣，圖論從柯尼斯堡里的趣味問題出發(fā)，經(jīng)過近三百年的發(fā)展，已經(jīng)超越了傳統(tǒng)幾何學(xué)的經(jīng)典范疇，成長為我們理解這個(gè)復(fù)雜互聯(lián)世界的一種數(shù)學(xué)語言。

參考資料：維基百科(Graph theory)

來源：遇見數(shù)學(xué)

編輯：檸七

轉(zhuǎn)載內(nèi)容僅代表作者觀點(diǎn)

不代表中科院物理所立場

如需轉(zhuǎn)載請(qǐng)聯(lián)系原公眾號(hào)