圖論中若干經典問題

武育杰　王浩　王宏立　王曉

關鍵詞：圖論；四色問題；中國郵遞員問題；哈密爾頓圖

中圖分類號：O157.5 文獻標識碼：A

文章編號：1009-3044（2023）14-0106-03

1 引言

圖是一個具有二元代數結構特征的數學模型，由頂點集和邊集構成，頂點表示研究對象，邊表示研究對象之間的關系。凡是涉及研究對象及其關系的問題都可以用“圖”來建立其拓撲數學結構。圖論作為理論工具，在復雜網絡系統、多智能體、分子結構和能量、生物基因譜分析、大數據分析以及社交網絡等諸多領域中都有著廣泛的應用。

圖論作為數學學科的一個分支，已經有200余年的歷史。公認的圖論第一篇論文是由瑞士數學家歐拉在1736 發表的關于哥尼斯堡七橋問題的論文[1]。在哥尼斯堡七橋問題中，將各個獨立的陸地區域視為頂點，每一座橋視為連接兩個頂點的邊，便構造了一個既簡潔又直觀的圖。1847年Kirchhoff運用圖論作為工具，成功地解決了電路理論中求解聯立方程的問題，引進了“樹”的概念，樹是圖論也是計算機理論中最基本并且是應用最多的概念之一[1]。1857年Cayley 在有機化學領域利用圖論中的樹為工具，解決了計算飽和氫化物同分異構體的數目的問題，這使得圖論在化學領域也發揮了重要作用。1936年，匈牙利數學家Konig出版了圖論的第一部專著《有限圖與無限圖理論》，這是圖論發展史上最重要的里程碑，它標志著圖論已成為一個具有完整體系的數學分支[2]。

現實世界中許多問題都可以用圖來描述其數學拓撲結構，通訊網、交通網、社團網、化學分子結構、生物基因圖譜、大規模集成電路都可以用圖來建立其數學模型框架。在理論研究上，圖論主要分為結構圖論、極值圖論、代數圖論、隨機圖論、拓撲圖論等幾個主要模塊，這幾個方面相互促進相互影響，共同促進圖論的發展。

一個好的數學問題應該具有描述的簡潔性、結論的出乎意料性、應用上的一般性。圖論中的四色問題、歐拉圖問題和哈密爾頓問題就完整地具備這些特征。由四色問題衍生出圖的著色理論，已成為結構圖論中最經典的部分[3]；中國郵遞員問題來源于歐拉圖問題，是中國學者研究圖論的典型結果之一[4]；哈密爾頓圖問題也稱為周游世界問題，是一個經典的NP-困難問題，對NP問題的研究起到了重要的促進作用[5]。通過對圖論中一些經典問題的起源、發展及影響的概述，可以促進圖論知識的普及，吸引更多研究者深入研究圖論理論及其應用。

2 圖論的起源——哥尼斯堡七橋問題

十八世紀的哥尼斯堡（現為俄羅斯的加里寧格勒），普列戈利亞河橫穿其中，河上有七座橋，連接著A、B、C、D四塊陸地，如圖1所示。當地流傳著一個著名的游戲謎題：能否從某塊陸地出發，恰好把每座橋走一次，最后又回到原地？1735年幾名大學生給當時的數學家歐拉寫信，請教這個問題。一年之后，歐拉證明了哥尼斯堡七橋問題是無解的，并引入了圖的概念，由此開創了圖論這一新的數學分支。

歐拉將A、B、C、D四塊陸地看作頂點，連接它們的橋看作邊，七橋問題就轉化為圖1中右邊的圖是否有經過每一條邊恰好一次的回路的問題。這樣的回路稱為歐拉回路，歐拉證明了圖論中最古老的定理（歐拉定理）：無奇度頂點的連通圖存在歐拉回路且可分解成邊不交的圈。同時，歐拉處理七橋問題的方法也蘊含著拓撲學的思想，拓撲學只關注圖形形狀的連接性，而并不關注自身的具體的大小和距離。交通網絡圖、通信網絡圖、社交網絡圖等都是以圖為基本結構來建立現實問題的數學拓撲模型。

山東師范大學的管梅谷教授在20世紀60年代提出一個運籌學問題：郵遞員每天從郵局出發，走遍該地區所有的街道再返回郵局，他如何安排送信路線可以使所走的總路程最短？這個問題被稱為中國郵遞員問題，其數學描述為：在賦權圖中找一條回路，使得過每條邊至少一次，且邊的權之和最小，即為帶權最優歐拉回路問題。管梅谷給出了奇偶點圖上作業法，求解中國郵遞員問題。1985年Edmonds給出了中國郵遞員問題的多項式算法[6]。

由歐拉定理可知歐拉圖的邊可以分解為邊不交的圈，但是最少可以分解成多少個邊不交的圈呢？Hajos曾給出猜想（被稱為Hajos猜想）：n個頂點的歐拉圖至多可以分解為n/2個邊不交的圈[7]。1966年，Erd?s、Goodman和Posa將此猜想弱化，猜想存在常數c使得n個頂點的歐拉圖可分解成cn個邊不交的圈。這兩個猜想被Pyber認為是“out of reach at present”。

認哥尼斯堡七橋問題為起源，歐拉引出了“圖”這一數學模型結構，構建了圖論的雛形。隨著中國郵遞員問題、歐拉圖的圈分解問題等的出現，進一步促進了圖論的發展。

3 圖論發展的動力——四色問題

四色問題曾和費馬猜想（1994年已由英國數學家證明，被稱為費馬大定理）、哥德巴赫猜想被稱為世界三大數學猜想。1852 年Morgan 教授的一位學生問他，能否證明：只需四種顏色就可以給任意地圖的每個國家著色，使得任意有共同邊界的國家所著的顏色不同。把地圖看作一個平面圖，國界看作是邊，不同國界的相交處看作是頂點，每個國家的區域就是面，則上述問題就是：任意一個平面圖最多用四種顏色給每個面著色，就可以使得有任何有公共邊的面所著的顏色都不同。如圖2，用4種顏色就可以把中國地圖各個相鄰的省份區分開。

1872年，英國數學家Cayley正式向倫敦數學學會提出了四色問題。自此以后，四色問題逐漸成為世界數學界關注的研究對象，吸引了一批優秀的數學家不斷地進行探索。一百多年來，這個看似簡單的問題，卻讓許多一流的數學家“折戟沉沙”。后人評價德國著名數學家Minkowski（曾是愛因斯坦的老師），最讓他尷尬的不是他曾罵愛因斯坦是“懶蟲”，而是他被四色問題掛在了黑板上。

1878年到1880年之間，數學家Kempe和Tait先后發表了關于四色問題的論文，宣布四色問題已獲得證明。大家都認為四色問題從此也就解決了，然而十年后，人們卻發現這兩人的證明都是錯誤的。1890年Heawood給出了Kempe證明中的一個反例（即為著名的Heawood 圖），從而推翻他的證明，并且利用Heawood的方法卻可以很容易就得到平面圖的5-色定理。Tait證明的錯誤之處是他認為3-正則且3-連通的平面是哈密爾頓圖（有一個圈包含圖中所有的頂點）。1946年，數學家Tutte給出了一個3-正則且3- 連通的平面圖不是哈密爾頓圖，從而徹底宣告了Tait 證明中的錯誤是無法修補的。雖然Kempe和Tait關于四色問題的證明是錯誤的，但是他們二人均為之后四色問題的證明奠定了基礎，并為之后圖論的發展做出了不可磨滅的貢獻。

20世紀以后，數學家關于四色問題的探索基本上是沿著Kempe 的思路進行。1936 年，美國數學家Franklin證明了22個面以內的平面圖都是4-可面著色的。沿用此思路，四色問題在1950年被改進到了35個面，隨后又被改進到了50個面。1976年，美國數學家Appel和Haken與計算機專家Kock三人合作完成了四色問題的證明[8-9]，這也開創了利用計算機來證明數學重大問題的先河。1994年，Seymour在第22屆國際數學家大會上做了1小時報告，報告的主題就是關于四色問題的證明。

給出Tait證明四色問題反例的數學家Tutte，一直致力于研究從純粹數學的角度來證明四色問題，希望找到純推理的方法來證明。為此，Tutte創立了整數流理論[10]，從更大的框架內來研究四色問題。Tutte提出了三個整數流猜想，形成了整數流研究的核心問題。目前，整數流理論已成為圖論研究的前沿問題之一。

4 圖論的NP-困難問題——哈密爾頓圖

1856年愛爾蘭數學家哈密爾頓（他也是第一個給出復數的代數表示的數學家）設計了一個游戲：給定一個十二面體（如圖3所示），每個點代表一個城市，每條棱代表兩個城市之間的一條路，是否存在從某一城市出發，經過每座城市恰好一次，最后又回到出發點？此問題也稱為周游世界問題。十二面體的20個點的拓撲結構可以用圖3中右圖的平面圖來表示，周游世界問題是有滿足條件的走法的，即圖中存在一個圈恰好包含每個頂點一次，這樣的圈稱為哈密爾頓圈，含有哈密爾頓圈的圖稱為哈密爾頓圖。

更一般化的周游世界問題，或者稱為旅行商問題，即一個旅行商從公司出發，訪問若干指定城市，最后返回公司，要求設計最優旅行路線（行程最短或費用最小）。數學抽象描述為：在賦權圖中找一條回路使得過每個點恰好一次且邊的權之和最小，即尋找賦權最優哈密頓圈[5]。

不同于歐拉圖，目前還沒有一個判定圖是哈密爾頓圖的非平凡的等價條件，這也是圖論中最重要的未解決問題之一。1952年，Dirac給出了判定哈密爾頓圖的度型條件；1960年，Ore給出了改進的度型條件；1972年，Chvátal給出了判定哈密爾頓圖的度序列條件；1976年Bondy和Chvátal給出了判定哈密爾頓圖的閉包條件[1]。

從算法角度看，判定圖的哈密爾頓性是NP-困難的。研究世紀猜想——NP問題，哈密爾頓圖即為一個很好的突破口。通常判定一個圖是否含有哈密頓圈都是用窮舉的方法。Rubin利用推演的方法給出了一個可優化的搜索步驟尋找圖中的哈密爾頓圈，An?gluin和Valiant利用概率方法設計了一種尋找哈密爾頓圈的非常有用的方法。

從應用的角度看，從工業鋪路到農業灌溉，從航空路線到海底偵察，從國家的發展到公司的運輸都要用到哈密頓圖的基礎數學模型結構。對哈密爾頓圖的研究已經顯得越來越重要，利用哈密爾頓圖的研究結果，可以大大提高工作的效率和節約發展成本，為可持續發展提供重要支持。

5 結束語

國內著名圖論學者范更華教授曾講過，以蒸汽機為標志的工業革命促進了以微積分為基礎的連續數學的發展，以計算機為標志的信息革命將極大地促進離散數學的發展，而圖論則是離散數學最主要的分支之一。現實世界中許多問題都可以用圖來描述其數學拓撲結構，四色問題、中國郵遞員問題和周游世界問題都是圖論中的經典問題，在圖論學科的發展過程中起著至關重要的作用。綜述圖論中經典問題的發展歷史，可促進圖論知識的普及，吸引更多研究者深入研究圖論理論知識及其在現實中的應用。