圖論中若干經(jīng)典問(wèn)題

武育杰　王浩　王宏立　王曉

關(guān)鍵詞：圖論；四色問(wèn)題；中國(guó)郵遞員問(wèn)題；哈密爾頓圖

中圖分類(lèi)號(hào)：O157.5 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2023）14-0106-03

1 引言

圖是一個(gè)具有二元代數(shù)結(jié)構(gòu)特征的數(shù)學(xué)模型，由頂點(diǎn)集和邊集構(gòu)成，頂點(diǎn)表示研究對(duì)象，邊表示研究對(duì)象之間的關(guān)系。凡是涉及研究對(duì)象及其關(guān)系的問(wèn)題都可以用“圖”來(lái)建立其拓?fù)鋽?shù)學(xué)結(jié)構(gòu)。圖論作為理論工具，在復(fù)雜網(wǎng)絡(luò)系統(tǒng)、多智能體、分子結(jié)構(gòu)和能量、生物基因譜分析、大數(shù)據(jù)分析以及社交網(wǎng)絡(luò)等諸多領(lǐng)域中都有著廣泛的應(yīng)用。

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

現(xiàn)實(shí)世界中許多問(wèn)題都可以用圖來(lái)描述其數(shù)學(xué)拓?fù)浣Y(jié)構(gòu)，通訊網(wǎng)、交通網(wǎng)、社團(tuán)網(wǎng)、化學(xué)分子結(jié)構(gòu)、生物基因圖譜、大規(guī)模集成電路都可以用圖來(lái)建立其數(shù)學(xué)模型框架。在理論研究上，圖論主要分為結(jié)構(gòu)圖論、極值圖論、代數(shù)圖論、隨機(jī)圖論、拓?fù)鋱D論等幾個(gè)主要模塊，這幾個(gè)方面相互促進(jìn)相互影響，共同促進(jìn)圖論的發(fā)展。

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

2 圖論的起源——哥尼斯堡七橋問(wèn)題

十八世紀(jì)的哥尼斯堡（現(xiàn)為俄羅斯的加里寧格勒），普列戈利亞河橫穿其中，河上有七座橋，連接著A、B、C、D四塊陸地，如圖1所示。當(dāng)?shù)亓鱾髦粋€(gè)著名的游戲謎題：能否從某塊陸地出發(fā)，恰好把每座橋走一次，最后又回到原地？1735年幾名大學(xué)生給當(dāng)時(shí)的數(shù)學(xué)家歐拉寫(xiě)信，請(qǐng)教這個(gè)問(wèn)題。一年之后，歐拉證明了哥尼斯堡七橋問(wèn)題是無(wú)解的，并引入了圖的概念，由此開(kāi)創(chuàng)了圖論這一新的數(shù)學(xué)分支。

歐拉將A、B、C、D四塊陸地看作頂點(diǎn)，連接它們的橋看作邊，七橋問(wèn)題就轉(zhuǎn)化為圖1中右邊的圖是否有經(jīng)過(guò)每一條邊恰好一次的回路的問(wèn)題。這樣的回路稱(chēng)為歐拉回路，歐拉證明了圖論中最古老的定理（歐拉定理）：無(wú)奇度頂點(diǎn)的連通圖存在歐拉回路且可分解成邊不交的圈。同時(shí)，歐拉處理七橋問(wèn)題的方法也蘊(yùn)含著拓?fù)鋵W(xué)的思想，拓?fù)鋵W(xué)只關(guān)注圖形形狀的連接性，而并不關(guān)注自身的具體的大小和距離。交通網(wǎng)絡(luò)圖、通信網(wǎng)絡(luò)圖、社交網(wǎng)絡(luò)圖等都是以圖為基本結(jié)構(gòu)來(lái)建立現(xiàn)實(shí)問(wèn)題的數(shù)學(xué)拓?fù)淠Ｐ汀?/p>

山東師范大學(xué)的管梅谷教授在20世紀(jì)60年代提出一個(gè)運(yùn)籌學(xué)問(wèn)題：郵遞員每天從郵局出發(fā)，走遍該地區(qū)所有的街道再返回郵局，他如何安排送信路線可以使所走的總路程最短？這個(gè)問(wèn)題被稱(chēng)為中國(guó)郵遞員問(wèn)題，其數(shù)學(xué)描述為：在賦權(quán)圖中找一條回路，使得過(guò)每條邊至少一次，且邊的權(quán)之和最小，即為帶權(quán)最優(yōu)歐拉回路問(wèn)題。管梅谷給出了奇偶點(diǎn)圖上作業(yè)法，求解中國(guó)郵遞員問(wèn)題。1985年Edmonds給出了中國(guó)郵遞員問(wèn)題的多項(xiàng)式算法[6]。

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

認(rèn)哥尼斯堡七橋問(wèn)題為起源，歐拉引出了“圖”這一數(shù)學(xué)模型結(jié)構(gòu)，構(gòu)建了圖論的雛形。隨著中國(guó)郵遞員問(wèn)題、歐拉圖的圈分解問(wèn)題等的出現(xiàn)，進(jìn)一步促進(jìn)了圖論的發(fā)展。

3 圖論發(fā)展的動(dòng)力——四色問(wèn)題

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

1872年，英國(guó)數(shù)學(xué)家Cayley正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了四色問(wèn)題。自此以后，四色問(wèn)題逐漸成為世界數(shù)學(xué)界關(guān)注的研究對(duì)象，吸引了一批優(yōu)秀的數(shù)學(xué)家不斷地進(jìn)行探索。一百多年來(lái)，這個(gè)看似簡(jiǎn)單的問(wèn)題，卻讓許多一流的數(shù)學(xué)家“折戟沉沙”。后人評(píng)價(jià)德國(guó)著名數(shù)學(xué)家Minkowski（曾是愛(ài)因斯坦的老師），最讓他尷尬的不是他曾罵愛(ài)因斯坦是“懶蟲(chóng)”，而是他被四色問(wèn)題掛在了黑板上。

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

20世紀(jì)以后，數(shù)學(xué)家關(guān)于四色問(wèn)題的探索基本上是沿著Kempe 的思路進(jìn)行。1936 年，美國(guó)數(shù)學(xué)家Franklin證明了22個(gè)面以?xún)?nèi)的平面圖都是4-可面著色的。沿用此思路，四色問(wèn)題在1950年被改進(jìn)到了35個(gè)面，隨后又被改進(jìn)到了50個(gè)面。1976年，美國(guó)數(shù)學(xué)家Appel和Haken與計(jì)算機(jī)專(zhuān)家Kock三人合作完成了四色問(wèn)題的證明[8-9]，這也開(kāi)創(chuàng)了利用計(jì)算機(jī)來(lái)證明數(shù)學(xué)重大問(wèn)題的先河。1994年，Seymour在第22屆國(guó)際數(shù)學(xué)家大會(huì)上做了1小時(shí)報(bào)告，報(bào)告的主題就是關(guān)于四色問(wèn)題的證明。

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

4 圖論的NP-困難問(wèn)題——哈密爾頓圖

1856年愛(ài)爾蘭數(shù)學(xué)家哈密爾頓（他也是第一個(gè)給出復(fù)數(shù)的代數(shù)表示的數(shù)學(xué)家）設(shè)計(jì)了一個(gè)游戲：給定一個(gè)十二面體（如圖3所示），每個(gè)點(diǎn)代表一個(gè)城市，每條棱代表兩個(gè)城市之間的一條路，是否存在從某一城市出發(fā)，經(jīng)過(guò)每座城市恰好一次，最后又回到出發(fā)點(diǎn)？此問(wèn)題也稱(chēng)為周游世界問(wèn)題。十二面體的20個(gè)點(diǎn)的拓?fù)浣Y(jié)構(gòu)可以用圖3中右圖的平面圖來(lái)表示，周游世界問(wèn)題是有滿(mǎn)足條件的走法的，即圖中存在一個(gè)圈恰好包含每個(gè)頂點(diǎn)一次，這樣的圈稱(chēng)為哈密爾頓圈，含有哈密爾頓圈的圖稱(chēng)為哈密爾頓圖。

更一般化的周游世界問(wèn)題，或者稱(chēng)為旅行商問(wèn)題，即一個(gè)旅行商從公司出發(fā)，訪問(wèn)若干指定城市，最后返回公司，要求設(shè)計(jì)最優(yōu)旅行路線（行程最短或費(fèi)用最小）。數(shù)學(xué)抽象描述為：在賦權(quán)圖中找一條回路使得過(guò)每個(gè)點(diǎn)恰好一次且邊的權(quán)之和最小，即尋找賦權(quán)最優(yōu)哈密頓圈[5]。

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

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

從應(yīng)用的角度看，從工業(yè)鋪路到農(nóng)業(yè)灌溉，從航空路線到海底偵察，從國(guó)家的發(fā)展到公司的運(yùn)輸都要用到哈密頓圖的基礎(chǔ)數(shù)學(xué)模型結(jié)構(gòu)。對(duì)哈密爾頓圖的研究已經(jīng)顯得越來(lái)越重要，利用哈密爾頓圖的研究結(jié)果，可以大大提高工作的效率和節(jié)約發(fā)展成本，為可持續(xù)發(fā)展提供重要支持。

5 結(jié)束語(yǔ)

國(guó)內(nèi)著名圖論學(xué)者范更華教授曾講過(guò)，以蒸汽機(jī)為標(biāo)志的工業(yè)革命促進(jìn)了以微積分為基礎(chǔ)的連續(xù)數(shù)學(xué)的發(fā)展，以計(jì)算機(jī)為標(biāo)志的信息革命將極大地促進(jìn)離散數(shù)學(xué)的發(fā)展，而圖論則是離散數(shù)學(xué)最主要的分支之一?，F(xiàn)實(shí)世界中許多問(wèn)題都可以用圖來(lái)描述其數(shù)學(xué)拓?fù)浣Y(jié)構(gòu)，四色問(wèn)題、中國(guó)郵遞員問(wèn)題和周游世界問(wèn)題都是圖論中的經(jīng)典問(wèn)題，在圖論學(xué)科的發(fā)展過(guò)程中起著至關(guān)重要的作用。綜述圖論中經(jīng)典問(wèn)題的發(fā)展歷史，可促進(jìn)圖論知識(shí)的普及，吸引更多研究者深入研究圖論理論知識(shí)及其在現(xiàn)實(shí)中的應(yīng)用。