魅力無限的圖論(Ⅰ)

許 進

(北京大學 信息科學技術學院， 北京 100871)

1 圖論過去、現(xiàn)在和未來

圖的概念引入主要來自兩個方面：①1736年大數(shù)學家Euler[1]解決格尼斯堡七橋問題而提出圖的概念；②1840年電路專家Kirchhoff[2]研究電路時，為了研究電路中電流和電壓的特性,獨創(chuàng)性地引入圖的概念，揭示了電路中的一些基本性質，提出了著名的基爾霍夫第一定律和基爾霍夫第二定律.

從1736年到1936年，整整兩個世紀，圖論的發(fā)展是非常緩慢的.1936年，法國數(shù)學家Berge才寫出第一本圖論的專著.就在1936年，年僅24歲的超天才圖靈創(chuàng)立了圖靈機[3].1945年，馮·諾依曼根據(jù)圖靈機原理建立了可編程的計算機結構體系.1946年，在美國賓夕法尼亞大學誕生了人類第一臺電子計算機.由于馮·諾依曼電子計算機模型是基于0-1二進制的，它的理論體系是離散數(shù)學，而圖論在離散數(shù)學中的地位幾乎是主導性的，這就極大地激發(fā)了人們對圖論研究的興趣.于是，伴隨著電子計算機的發(fā)展，圖論這門古老而年輕的學科得到了飛速的發(fā)展.從1945年至今，僅僅七十余年，無論從理論研究，還是在現(xiàn)實生活中的應用，都得到了驚人的發(fā)展.現(xiàn)在，可以毫不夸張地講，圖論幾乎已經(jīng)應用于人類目前創(chuàng)造的所有領域.2016年，一種從底層全并行的計算機模型，稱為“探針機”被提出來[4].該模型發(fā)現(xiàn)了圖靈機的局限性，即本質上與中國珠算等價.探針機的框架充分利用圖論理論構建.相信未來，人類的計算機體系結構將會以探針機模型構建.

2 圖論魅力無限

首先，圖論在理論方面存在層出不窮又難的出奇的難題需要去解決，其中有些問題的難度可能不亞于諸如哥德巴赫猜想、孿生數(shù)猜想、費馬爾猜想及P≠NP猜想等.

其次，圖論自身優(yōu)勢特點與時代發(fā)展相契合.圖論自身直觀、簡單、明了的優(yōu)勢特點，在解決問題時能給人以獨特、奇妙的魅力感受.由于四色猜想的促進和電子計算機科學快速發(fā)展的強烈激發(fā)，圖論在當今離散數(shù)學與組合數(shù)學中占據(jù)了主導地位，現(xiàn)已在理論上形成了含蓋樹論、圖的度序列理論、連通圖論、代數(shù)圖論、圖的計數(shù)理論、著色理論、平面圖理論及其應用、Ramsey數(shù)理論、圖的可遍歷性理論、算法圖論及應用圖論的強大理論體系[5-7].加之互聯(lián)網(wǎng)的促進，人類發(fā)展到了產(chǎn)生大量形形色色數(shù)據(jù)的“大數(shù)據(jù)時代”和“社交網(wǎng)絡時代”，而要處理這些海量數(shù)據(jù)，圖論因其在模型構建和算法設計上的獨特優(yōu)勢勢必擔當主角.

最后，圖論具有許多數(shù)學分支無法比擬的、廣闊無垠的應用天地.可以毫不夸張地講，圖論幾乎可以應用于人類目前創(chuàng)造的所有領域.經(jīng)過近幾十年的發(fā)展，圖論業(yè)已廣泛應用于諸如生命科學、計算機科學、電子線路、信息科學、模式識別、網(wǎng)絡安全、心理學、社會科學，甚至中文等領域.

圖論的魅力在于它本身的結構之美，解決問題的速度之快，以及應用的范圍之廣.在可預見的將來，圖論將在下述八個領域大放異彩.

2.1 生命科學領域

在生命科學領域，很多重要問題的研究都涉及到生物復雜網(wǎng)絡，如生物神經(jīng)網(wǎng)絡[8]、控制生物性狀的基因網(wǎng)絡[9]、植物次生代謝網(wǎng)絡[10]、蛋白質相互作用網(wǎng)絡[11]、蛋白質結構預測問題[12]等.生物神經(jīng)網(wǎng)絡通常指生物的大腦神經(jīng)元、細胞、觸點等組成的網(wǎng)絡；在基因網(wǎng)絡中，結點是轉錄因子或基因，邊表示轉錄因子和基因之間的調(diào)控關系；代謝網(wǎng)絡中結點代表的是代謝底物或者產(chǎn)物，而邊代表底物或產(chǎn)物之間的代謝反映；蛋白質相互作用網(wǎng)絡中，結點代表蛋白質個體，邊代表兩個蛋白質之間的相互作用關系.因此，這些問題可利用圖論的方法進行研究.Koessler等[13]利用圖論方法，對從主結構確定RNA二級結構的問題進行研究，提出了RNA二級結構的預測模型.Bermúdez等[14]利用圖論方法刻畫大腸桿菌的tRNA結構，將tRNA表示為圖，其中頂點對應核苷酸，邊對應磷酸二酯和氫鍵之間的鍵.Ren等[15]利用圖論方法，建立腦功能的網(wǎng)絡結構模型，研究了針灸調(diào)節(jié)腦網(wǎng)絡重組的效果. Stavrakas等[16]利用圖論方法建立蛋白質結構網(wǎng)絡，通過寬度優(yōu)先遍歷算法識別最短路徑，分析了蛋白質相互作用網(wǎng)絡，給出了生物學解釋.

2.2 社交網(wǎng)絡領域

社交網(wǎng)絡又稱為社會網(wǎng)絡，是一種基于網(wǎng)絡的社交組織形式，指社會行動者及他們之間關系的集合.若將社交網(wǎng)絡中的基本要素，也就是每個人看成一個節(jié)點，節(jié)點之間的連線看成是人與人之間的聯(lián)系，那么用一個復雜的圖就可以對社交網(wǎng)絡進行描述，G=(V,E)，其中V表示節(jié)點的集合，E表示節(jié)點關聯(lián)(邊)的集合.因此，社交網(wǎng)絡中的一些重要問題，如結構特征[17-18]、社區(qū)發(fā)現(xiàn)[19-20]、影響力最大化[21-22]等問題，都可以利用圖論的方法進行研究.

1998年，Watts等[17]發(fā)現(xiàn)許多網(wǎng)絡中都存在小世界現(xiàn)象.網(wǎng)絡的小世界特性包含兩個重要的屬性，即網(wǎng)絡平均路徑長度和平均聚集系數(shù).Mislove等[23]對YouTube、Flickr、Live Journal等知名在線社交網(wǎng)絡進行了小世界現(xiàn)象的驗證，得到這些不同種類的在線社交網(wǎng)絡均有小世界現(xiàn)象.

Barabasi等[18]于1999 年首先發(fā)現(xiàn)了復雜網(wǎng)絡的無標度特性，并揭示出無標度性是許多復雜網(wǎng)絡具有的性質.社區(qū)發(fā)現(xiàn)問題都是NP-難問題[19]，Palla等[20]提出了團滲透的方法解決社區(qū)發(fā)現(xiàn)問題，并定義在k團特征圖中有k-1個節(jié)點相同的k團具有連接關系.特征圖中的每個連通分支就被定義為一個社區(qū).由于k團之間會有重疊節(jié)點，因此，這種方法可以自然地發(fā)現(xiàn)重疊社區(qū).

影響最大化問題最早是由Domingos等[21]引入到社交網(wǎng)絡中的.他們將影響最大化問題抽象成一個算法問題.Kempe 等[22]針對所提出的級聯(lián)模型和閾值模型，給出了一種貪心近似算法，并證明了該算法的貪心近似比至少為1-1/e. Estevez等[24]提出了集合覆蓋貪心算法.Chen等[25]從兩個方面提高了影響力最大化的效率問題，即首先提出一種改進的貪心算法，該算法將圖中沒有傳播成功的邊去掉，得到新的圖，然后在新圖上依照貪心策略依次選擇初始節(jié)點.

2.3 網(wǎng)絡安全領域

社會信息化程度的加深使人們對網(wǎng)絡的依賴程度加強，網(wǎng)絡安全日益受到重視并得到廣泛的研究.其中，圖論作為研究網(wǎng)絡安全的重要工具，被用于研究各種可行的方法以對網(wǎng)絡系統(tǒng)安全進行建模、分析和評估，并取得了許多的研究成果.

2.3.1 攻擊樹

Schneier[26]提出的攻擊樹是一種描述滲透式攻擊對系統(tǒng)安全造成威脅的模型，能比較直觀地反映攻擊者實施攻擊的步驟.在攻擊樹模型中，用樹型結構來表示系統(tǒng)面臨的攻擊，其中根節(jié)點代表被攻擊的目標，葉子節(jié)點表示達成攻擊目標的方法，可以在很大程度上幫助我們判斷系統(tǒng)存在的威脅和決定應對攻擊的方法.

2.3.2 攻擊圖

網(wǎng)絡中總是存在一定的安全漏洞，同時這些漏洞之間可能存在一定的關聯(lián)關系，即當一個漏洞被成功利用后，可能為另一漏洞的利用創(chuàng)造有利條件.結合網(wǎng)絡拓撲、目標漏洞、主機弱點等信息，找到所有能夠到達目標的攻擊路徑，并以圖的形式表現(xiàn)，即攻擊圖[27].

攻擊圖能夠挖掘出潛在的攻擊序列，可對網(wǎng)絡系統(tǒng)的安全性做出更為全面的分析，及時發(fā)現(xiàn)和消除計算機網(wǎng)絡系統(tǒng)中存在的安全隱患，減少惡意攻擊.與攻擊樹相比，攻擊圖對網(wǎng)絡攻擊過程的描述能力更強，但該方法因其高復雜度，存在組合爆炸問題，無法直接對大規(guī)模網(wǎng)絡使用.

2.3.3 脆弱性分析

對一個網(wǎng)絡的拓撲結構而言，總有一個或多個節(jié)點占有極為重要的位置，如果破壞掉它們，這個網(wǎng)絡在諸如結構、穩(wěn)定性上將受到很大的影響.因此，分析關鍵節(jié)點或脆弱點有著重要的現(xiàn)實意義.

最為簡單直接的做法就是使用節(jié)點的度指標，來衡量關鍵節(jié)點的重要程度.筆者提出了核與核度理論[28]，用于刻畫網(wǎng)絡中一組節(jié)點的重要性, 通過刪除一些節(jié)點及其相連的邊后, 以網(wǎng)絡中出現(xiàn)的連通分支個數(shù)來衡量核度.王建偉等[29]認為連接節(jié)點的邊越重要, 則節(jié)點越重要，并將其視為分析網(wǎng)絡中節(jié)點與連邊重要性的一個基本公理.同時，還有基于隨機游走思想設計的算法，如PageRank和LeaderRank，也可以用于網(wǎng)絡脆弱性分析.

此外，還有一些基于圖論的網(wǎng)絡安全分析方法，如類似于攻擊樹的故障樹[30]具有可靠性分析的功能，被大量應用在航空航天和核工業(yè)等產(chǎn)業(yè)領域.總之，圖論因其具有高效性和較好的可讀性，被廣泛應用于網(wǎng)絡安全領域當中.

2.4 社會科學領域

人類社會有種種現(xiàn)象，涉及經(jīng)濟、政治、心理、歷史等很多學科，社會科學便是用科學的方法來研究人類社會這些現(xiàn)象.在科學研究的發(fā)展進程中，圖論為社會科學的研究提供了新的方法和手段.例如在經(jīng)濟金融領域，Tabak等[31]研究了巴西股票市場網(wǎng)絡的拓撲結構，使用關聯(lián)矩陣為不同板塊的股票構建了最小生成樹，采用復雜網(wǎng)絡的動態(tài)方法度量了不同板塊的相對重要指數(shù)，并給出了股票市場網(wǎng)絡中最重要的板塊.如何分析越來越龐大的金融數(shù)據(jù)集是現(xiàn)在眾多應用需要面對的挑戰(zhàn).2012年，Lautier等[32]針對金融市場的高維數(shù)據(jù)提出了一種可以應用于多種領域的圖論分析方法，同時闡述了該方法應用于金融衍生市場系統(tǒng)風險分析情景的優(yōu)勢.針對金融領域的犯罪場景，Jedrzejek 等[33]使用圖挖掘方法進行檢測，對犯罪行為人的行為及逆行有效推理.在心理學領域，Crosier等[34]回顧了社交網(wǎng)絡的演化基礎和網(wǎng)絡構成中的心理因素.在考古學領域，Brughmans[35]追溯了考古學家中最有影響力的學術傳統(tǒng)以及網(wǎng)絡模型和技術的起源，揭示了圖論方法在考古學中的潛力.

2.5 系統(tǒng)科學領域

圖論在系統(tǒng)科學領域也有諸多應用.在研究系統(tǒng)中非常重要的要素，即系統(tǒng)的核和核度理論時，用圖作為系統(tǒng)中要素和關系的映射以及應用圖論進行分析與研究是一種相當重要的方法[28].譬如控制系統(tǒng)等很多復雜的系統(tǒng)都可以簡化地表示為一個圖.作為分析大型工程問題的有力工具，圖論可以幫助我們簡化復雜系統(tǒng)的拓撲連接關系.圖論中的許多研究成果也可以作為分析系統(tǒng)結構、尋求系統(tǒng)優(yōu)化算法的重要理論依據(jù)和研究方法[36]，圖論在復雜系統(tǒng)中的系統(tǒng)設計、故障診斷恢復、狀態(tài)分析、損費分攤等方面均有廣泛而重要的應用[37].Prabhakaran等[38]利用圖論的方法，通過建立復合材料性能與結構之間的聯(lián)系，給出了一種對復合產(chǎn)品系統(tǒng)進行完整分析的自上而下的方法.Schné等[39]利用圖論方法，對分散化控制器結構進行優(yōu)化設計，提出一種基于最接近加權最大匹配的圖論算法，改進了分散化控制器的效率.Hamzeh等[40]利用圖論方法，對電力系統(tǒng)網(wǎng)絡的優(yōu)化配置問題進行了研究.

2.6 交通信號研究

近年來隨著城市人口密度的增長，車流量的增加，交通擁堵成為各大城市需要重點解決的難題.解決交通擁堵一方面在于合理的城市道路規(guī)劃，另一方面則在于優(yōu)化交通信號從而發(fā)揮其合理的交通指揮和疏導作用[41].因為交通信號在處理過程中存在著錯綜復雜的連接關系，因而圖論知識在其中起到了不可或缺的作用.

在處理交通信號燈問題時，可以引入圖論中“圖染色”的概念[42].將城市路口交通信號燈最優(yōu)相位個數(shù)歸結為其交通流模型圖的圓色數(shù).在計算過程中，根據(jù)特殊n岔路口交通流狀況，由車流的沖突關系給出交通流模型圖并求出它們的圓色數(shù)，即為給出對應交通信號燈的最優(yōu)相位個數(shù)，從而確定不同狀態(tài)下的交通信號.

此外，城市軌道交通線路之間的連接關系同樣可以利用圖論的形式來展現(xiàn).在設計城市軌道交通信號設備布置模型時，可采用圖論拓撲結構策略[43].用圖的形式描述信號設備，為城市軌道交通信號設備布置設計合理的矢量圖形數(shù)據(jù)拓撲結構，從而實現(xiàn)信息數(shù)據(jù)的組織.在解決地鐵信號設備布置問題的算法中，需要從某個信號設備出發(fā)，系統(tǒng)遍歷所有的信號設備，在這個過程中，需要用到圖論知識中圖的遍歷. Yang等[44]利用圖論方法，提出一種基于點對點網(wǎng)絡的車輛網(wǎng)絡模型，提高了網(wǎng)絡通信能力以及網(wǎng)絡系統(tǒng)的穩(wěn)定性.

2.7 中文研究

圖論在中文研究領域，諸如在文本研究、古漢語音韻學研究等領域，都有著極為廣泛的應用，對探索語言網(wǎng)絡的結構特征規(guī)律和功能演化規(guī)律有著十分重要的意義.

2006年，通過應用基于模糊圖論的最大樹法，提出了一種中文文本模糊聚類算法ATCMT[45].ATCMT首先對文本建立模糊相似矩陣，然后構造模糊圖及其最大模糊支撐樹，最后進行模糊聚類分析.2009年，一種基于圖結構的中文文本表示模型被提出[46].它將文本特征項表示成圖結構節(jié)點，將特征項之間的共現(xiàn)關系表示為圖結構的邊，從而將文本映射為圖結構，有效地解決了文本表示中詞語間語義信息缺失問題.2012年，結合圖論中的理論，一種基于語義圖結構的中文文本分類方法RCSGC被提出[47].除了對文本研究有著極為重要的作用，圖論在古漢語音韻學研究中也有一定的實用價值.2011年，一種基于圖論方法的度量古漢語詞音相似度方法被提出[48]，為傳統(tǒng)音韻學長期以來建立的定性研究提供了一些定量的參考和檢驗.

2.8 模式識別研究

模式識別指對表征事物或現(xiàn)象各種形式的信息進行處理和分析，從而達到對事物或現(xiàn)象進行描述、辨認、分類和解釋的目的.在自然界中，大量模式都可以用圖的形式進行表示.隨著數(shù)據(jù)存儲、傳輸、計算能力的增強，人們開始有能力從圖結構數(shù)據(jù)中提取有用的信息.以圖理論對問題和數(shù)據(jù)進行建模，利用經(jīng)典圖論算法求解或與其他新興技術相融合正越來越成為模式識別研究中的熱門領域.比如在計算機視覺方向，利用圖論建模圖像中的拓撲關系，提高圖像識別和分割的準確率及可信度[49-50]；在計算化學方向，以圖結構對化合物分子結構進行建模，以尋找特定的分子亞結構和模式，為新型化合物制備及藥物研發(fā)提供理論指導[51]；在腦科學方向，利用圖論方法，對功能核磁共振成像數(shù)據(jù)進行建模，在分析各神經(jīng)單元的依賴關系和因果性相互作用，建立大腦連接模式，理解大腦架構等方面發(fā)揮了重要作用[52].此外，圖論與其他理論和工具的融合也催生了一系列富有前景的新方法，如概率圖模型[53]、圖神經(jīng)網(wǎng)絡[54]等.