1736年的普魯士柯尼斯堡城中，一個有趣的消遣游戲在當地居民中流行：在這座被普列戈利亞河分割的城市里，能否找到一條路線，一次性走遍連接兩座小島與兩岸的七座橋，且每座橋只走一次？

圖源：維基

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

歐拉拋棄了所有無用的物理表象——島嶼的面積、橋梁的長度，所有與連接關系無關的屬性，通通不重要。他剝離了度量信息，直擊問題的拓撲核心：連通關系，將陸地簡化為點，橋梁簡化為線。

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

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

歐拉這種只看連通關系、不看幾何形狀的抽象思考方式，對后世數學產生了深遠影響。

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

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

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

19世紀中葉，推動兩門學科共同演進的另一股力量來自現代代數工具的引入。物理學家基爾霍夫在研究電路時，獨立發展了用圖表示電路結構的方法，并由此提出了現代電子工程領域的基礎法則——基爾霍夫電路定律(Kirchhoff's circuit laws)。

而在同一時期，當約翰·本尼迪克特·李斯廷剛剛將拓撲學這一概念引入學術界時，凱萊在研究微分算子的代數結構時，開始關注一類特殊的圖——樹(Trees)。凱萊敏銳地發現，這些沒有回路的樹，與化學分子中原子的內在連接網絡存在著高度的結構同構性。他將關于樹的成果與當時的化學成分研究結合起來，這種數學與化學的跨界結合，為枚舉圖論(Enumerative graph theory)的誕生奠定了重要基礎。

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

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

1969年，哈拉里出版了該領域的權威教科書。特別是哈拉里的著作，打破了學科間的專業壁壘，使得數學家、化學家、電氣工程師以及社會科學家得以在統一的理論框架下探討網絡結構問題。哈拉里更將該書的全部版稅捐出，資助設立了波利亞獎(Pólya Prize)。

unset unset四色問題驅動的理論突破unset unset

如果說七橋問題是圖論的起點，那么四色問題就是推動這門學科發生質變的催化劑。

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

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

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

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

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

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

unset unset機器輔證與隨機演化：走向復雜系統unset unset

四色問題的最終解決，引發了長久的數學爭議。

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

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

但這還不是故事的終點。

2005 年 1 月互聯網拓撲局部圖（數據：opte.org）

就在人們以為圖論的研究對象僅限于靜態的確定性圖(Deterministic Graphs)時，埃爾德什與雷尼將概率論的思想引入進來了。他們改變了傳統的研究視角，不再局限于單一圖的靜態拓撲，而是專注于研究圖連通性的漸近概率。他們思考：當頂點數量趨向無窮時，在給定頂點之間以特定概率隨機生成連線，圖的連通性等整體性質將呈現何種漸近規律？就這樣，隨機圖論(Random graph theory)作為一個全新分支破土而出。

今天圖論已經滲透到現代科學的幾乎每一個角落，計算機科學家用來設計算法與數據結構的基礎，生物學家研究基因調控網絡與蛋白質相互作用，社會學家分析人際關系與信息傳播，也被工程師用于設計通信網絡和交通系統。

就這樣，圖論從柯尼斯堡里的趣味問題出發，經過近三百年的發展，已經超越了傳統幾何學的經典范疇，成長為我們理解這個復雜互聯世界的一種數學語言。

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

來源：遇見數學

編輯：檸七

轉載內容僅代表作者觀點

不代表中科院物理所立場

如需轉載請聯系原公眾號