圖論中的計數(shù)理論及其應用

錢建國，金賢安，楊維玲

(廈門大學數(shù)學科學學院，福建 廈門 361005)

圖論中的計數(shù)問題可追溯到1857年Cayley第一次用樹表示烷烴研究同分異構體的計數(shù)問題時所建立的遞歸公式[1].隨后，對圖結(jié)構計數(shù)問題的研究始終伴隨著分析化學的應用，并由此催生了基于對稱原理的離散結(jié)構計數(shù)理論，即：Redfield-Pólya計數(shù)理論[2].100多年來，包括圖結(jié)構計數(shù)在內(nèi)的各種圖論計數(shù)問題得到了很好的發(fā)展并各自形成了較完整的理論體系，如匹配計數(shù)[3-5]、著色計數(shù)(色多項式)[6]及圖計數(shù)[7]等理論，在統(tǒng)計物理、分析化學及信息生物學等領域得到了很好的應用.

本文主要對以張?；淌跒榇淼膹B門大學組合圖論研究團隊20多年來在圖論中的計數(shù)問題，以及在統(tǒng)計物理和分析化學中的應用方面的研究成果進行回顧.限于篇幅，在此僅包括部分具有代表性的工作，主要包括匹配計數(shù)、組合計數(shù)、拓撲圖論、組合紐結(jié)理論、隨機圖理論、網(wǎng)絡優(yōu)化以及相關應用等方面的研究成果，并提出未來研究的展望.

1 匹配理論及應用

圖的匹配理論是圖論中非?；钴S的研究領域.著名圖論專家Lovsz(Wolf獎及Abel獎得主，國際數(shù)學家大會ICM邀請報告人，曾任國際數(shù)學聯(lián)盟主席)的專著《匹配理論》對匹配理論進行了系統(tǒng)的論述[8].2006年Fields獎獲得者Okounkov的獲獎工作之一也與匹配計數(shù)理論有著密切的關系[4].在應用方面，匹配理論中的匹配計數(shù)問題等價于統(tǒng)計物理中的二聚體(Dimer)問題，是統(tǒng)計物理計算可解模型的熱門研究對象[9-11].此外，匹配理論也是量子化學家研究芳香碳氫化合物的重要工具之一[12-13]，如Kekule結(jié)構及Clar 覆蓋[14].

本團隊運用組合學、代數(shù)、概率及Pfaffian定向等理論方法，在匹配計數(shù)問題的理論研究及應用取得了許多突破性的成果，豐富了匹配理論.

1.1 匹配計數(shù)

匹配計數(shù)是匹配理論中的一個核心問題，也是一個非常難的問題.Robertson等[3]和Kenyon等[4]先后發(fā)表文章對此進行論述.在匹配計數(shù)理論的研究中，來源于積和式計算問題的Pfaffian定向是完美匹配計數(shù)的一個強有力工具：若一個圖有Pfaffian定向，那么就可以在多項式時間內(nèi)計算其完美匹配數(shù).然而，確定一個圖是否有Pfaffian定向也是非確定性多項式(NP)-困難的.2006年Thomas[5]提出了值得進一步研究的若干重要問題(猜想7.5，9.5).該問題被列入在教育部、科學技術部、中國科學院和國家自然科學基金委聯(lián)合編撰的《10 000個科學難題(數(shù)學卷)》中，相當程度上代表了我國相關學科研究的前沿問題，不僅具有深刻的理論意義，而且在統(tǒng)計物理、量子化學中也將具有很好的應用價值.

本團隊多年來一直致力于圖的Pfaffian定向及其應用問題的探索，解決了一系列經(jīng)典圖類的Pfaffian定向問題[15-17].確定一個圖的Pfaffian定向的本質(zhì)是要研究對應的匹配覆蓋的brick結(jié)構.Norine 和Thomas猜想每個極小brick的三度點至少有4個，我們證明了該猜想[18].進一步地，Lucchesi等猜想：三正則solid brick中的任意兩個奇圈必相交.我們證明了一類三正則solid brick存在兩個點不交的奇圈，從而否定了該猜想[19].此外，我們刻畫了邊等價類階數(shù)可以任意大的匹配覆蓋圖，推廣了Lovsz關于brick中的邊等價類中最多含2條邊的結(jié)果，回答了Lu等[20-21]提出的問題.這些猜想和問題的解決，有助于更好地認識brick結(jié)構，推動圖的Pfaffian定向問題的進展.

美國數(shù)學家Ciucu利用純組合方法研究了具有反射對稱的平面二部圖的完美匹配的計數(shù)問題，得到了匹配因子定理，但該結(jié)果要求對稱軸不能與圖的邊相交.我們運用組合與Pfaffian定向相結(jié)合的方法，結(jié)合代數(shù)理論，對多種具有反射對稱圖的完美匹配的計數(shù)問題進行了全面而又系統(tǒng)的研究，給出了這些對稱圖的完美匹配的計數(shù)公式[22-23].進一步，運用這一方法以及對稱圖的匹配計數(shù)理論也得到了反射對稱圖的生成樹數(shù)目的一個因子分解定理，并首次建立了樹的匹配數(shù)與Wiener數(shù)這兩個看似無關的拓撲指標之間的關系[24-25].Pfaffian定向不僅在匹配計數(shù)理論中扮演著重要角色，也反過來促進了積和式問題的研究.Borowiecki和Jozwiak于1981年提出了刻畫匹配計數(shù)理論積和式多項式只有純虛數(shù)根的所有圖的公開問題，但直到現(xiàn)在此問題還沒有完全解決；本團隊運用Pfaffian定向的方法部分地解決了此問題，是迄今為止此問題的最好結(jié)果[26].

1.2 應 用

匹配及其計數(shù)是圖論最具應用背景的理論之一，在優(yōu)化理論、統(tǒng)計物理及分析化學中扮演著重要的角色.

在統(tǒng)計物理中單體-二聚體(Monomer-Dimer)問題等價于匹配理論中的匹配多項式問題.然而，二維以上(含二維)的大規(guī)模圖的Monomer-Dimer問題之前從未得到過精確計算公式，已有結(jié)果都是通過數(shù)字模擬的方法得到近似解.我們運用Pfaffian定向與組合計數(shù)相結(jié)合的方法給出了一類任意維數(shù)的大規(guī)模圖的Monomer-Dimer構型的精確解，這是迄今為止有關此問題的第一個非平凡的精確解[27].此外，我們得到了克萊因瓶上網(wǎng)格圖Dimer構型的數(shù)目[28]; 計算了幾類化學圖的Kekule結(jié)構數(shù)[29]；得到了一些平面網(wǎng)格圖、若干環(huán)面上圖的完美匹配數(shù)[20]；推廣了著名物理學家Kasteleyn的一個被引用880多次的經(jīng)典結(jié)果，該結(jié)果被收錄于HandbookofProductGraphs一書中；給出了多米諾圖完美匹配數(shù)的線性算法及不存在線性算法的刻畫[30].

自C60被人工合成以來，石墨烯成為了現(xiàn)代材料科學的一個熱點.本團隊運用轉(zhuǎn)移矩陣、積和式及隨機過程等理論方法給出了納米管、隨機石墨烯的Dimer與Monomer-Dimer的計數(shù)公式[31-35].特別是在文獻[31-32]中，運用統(tǒng)計的方法解決了隨機生長石墨烯Monomer-Dimer的計數(shù)問題，從而建立了石墨烯繩隨機生長過程的數(shù)學模型.

Clar芳香六隅體理論是著名化學家Clar[14]于1972年提出的理論模型.基于分子軌道的性質(zhì)，芳香性反映一定類型的共軛系統(tǒng)的特定穩(wěn)定性.從多種實驗測量計算所得到的共振能表示在不同的Kekule(完美匹配)結(jié)構之間互相轉(zhuǎn)換所得到或失去的能量，也表示共軛系統(tǒng)的特定穩(wěn)定性.在半經(jīng)驗的分子價-鍵視角中，處理這個問題的不同價-鍵模型相繼建立[38].在這些模型中，Clar 芳香六隅體理論描述了苯類碳氫化合物的芳香性.在估算分子共振能的多種方法中，化學家Randic在1976年建立的共軛圈模型是基于共軛圈的組合計數(shù)[39]，它能用于多環(huán)共軛系統(tǒng)的芳香性和共軛的研究.從Clar芳香六隅體理論和Randic共軛圈模型，能夠發(fā)展出一系列有化學背景的數(shù)學模型和數(shù)學計算方法.六隅體多項式、Clar多項式、Clar覆蓋多項式和線性獨立極小共軛圈多項式等被相繼引入[40-42].六隅體結(jié)構，Kekule結(jié)構以及線性獨立極小共軛圈結(jié)構的性質(zhì)被深入研究.這些多項式的計算和多種結(jié)構的性質(zhì)研究提出了非常有趣并具有挑戰(zhàn)性的研究課題.本團隊在上述課題的研究中取得豐富的開創(chuàng)性研究成果[41-45]，其中張和平和張?；淌谑状我氲腃lar覆蓋多項式[41]被國際數(shù)學化學界稱為Zhang-Zhang多項式[46].郭曉峰等首次引入了線性獨立極小共軛圈多項式，并對此多項式的遞歸計算方法和解析計算方法進行了較深入的探索，進而在k-共振苯系統(tǒng)，k-共振冠狀苯系統(tǒng)和k-圈共振圖的研究中得到一系列新成果[46-50].

2 組合計數(shù)

組合計數(shù)是古老且有廣泛應用背景的理論.本團隊在組合計數(shù)理論，特別是容斥理論、Pólya計數(shù)理論及應用方面取得了豐碩的成果，部分成果具有較好的創(chuàng)新性.

2.1 容斥理論及應用

容斥原理是組合計數(shù)最經(jīng)典和最基本的方法之一，是組合數(shù)學教科書中的基本內(nèi)容.在容斥表達式中，基于容斥原理的“項”多達指數(shù)量級，其中大多數(shù)是重復計算的.由此產(chǎn)生了一個自然而深刻的問題：是否有可能使一些項事先相互對消而使最終的計算簡化？1932 年著名數(shù)學家 Whitney 建立了計算圖的色多項式的破圈定理[6]，對這個問題給予了一個肯定的回答，由此開創(chuàng)了容斥對消(inclusion-exclusion cancellation)理論.特別對色多項式而言，破圈結(jié)構實現(xiàn)了“完全對消”并據(jù)此獲得了色多項式系數(shù)的組合解釋.Whitney的破圈定理對圖多項式理論無疑產(chǎn)生了深刻的影響，不僅在圖的色多項式理論中扮演著重要角色，也被推廣到超圖、符號圖、擬陣的多項式理論以及格論的研究中[51-52].

本團隊首次將容斥對消理論用于圖的列表著色計數(shù)問題[52]，大幅改進了 Donner 和 Thomassen 的重要結(jié)果.這一方法也為研究更一般圖類(如超圖、符號圖等)的(列表)著色計數(shù)問題提供了很好的借鑒.在文獻[53]中本團隊將上述成果推廣到超圖上，其技術難點是如何對消超圖結(jié)構中的邊子集.為此，我們對超圖的圈結(jié)構進行了合理的刻畫，對超圖“圈”的概念給予了新的詮釋.文獻[54]運用容斥對消理論研究符號圖著色的對偶問題，首次給出了符號圖處處非零流計數(shù)的容斥對消表達式，并就奇數(shù)的情形給出了符號圖流多項式系數(shù)的一個組合解釋.

破圈定理所蘊含的容斥對消思想也發(fā)展了組合學中經(jīng)典的容斥原理，并進一步獲得了各種形式的推廣.最具代表的是Narushima[55]、Dohmen等[56]、Brylawski[57]以及Naiman等[58]分別從組合學和代數(shù)拓撲的角度所建立的定義在一般度量空間上的容斥對消理論，其主要思想是對指標集進行排序(index ordering，全序或偏序或格系統(tǒng))，進而運用單純復形的計數(shù)理論對重復計算做對消分析.最近，在文獻[59]中本團隊首次創(chuàng)立了不依賴指標序(ordering-free)的容斥對消方法，并進一步證明不依賴指標序的容斥對消集優(yōu)于所有依賴指標序的對消集.這一結(jié)果實質(zhì)性地改進了容斥對消理論，進一步發(fā)展了經(jīng)典的容斥原理，在圖的各種計數(shù)多項式以及更一般的基于容斥原理的計數(shù)問題上具有廣闊的應用前景.

2.2 Pólya計數(shù)理論在圖論中的應用

1857年，著名數(shù)學家 Cayley[1]首次用樹表示烷烴來研究同分異構體的計數(shù)問題，由此開啟了圖的計數(shù)問題的研究.100多年來，對圖的計數(shù)問題的研究始終伴隨著化學及生物學的應用，并由此催生了許多經(jīng)典的計數(shù)理論和方法[60].最具代表性的是 Redfield 和 Pólya 的工作：他們把代數(shù)學家 Burnside 揭示的群與不變元之間關系的理論進一步完善，并成功應用到同分異構體的計數(shù)中，其核心是將置換與結(jié)構等價類之間的內(nèi)在聯(lián)系用輪換示式(cycle index)給出了一個清晰的刻畫.Pólya 計數(shù)理論不僅在化學中的應用意義重大，也極大地豐富和發(fā)展了組合計數(shù)理論.1987 年，Read 將 Pólya 計數(shù)理論的原始著作翻譯成英文并對這一理論的發(fā)展給予了精彩的回顧[2].

本團隊應用 Pólya 計數(shù)理論在分子結(jié)構的計數(shù)問題取得了豐富的研究成果：運用 Pólya 計數(shù)理論給出了富勒烯的計數(shù)公式[61]；運用顏色集上的置換給出了苯環(huán)及其手性結(jié)構數(shù)目的解析表達式，其中苯環(huán)抽象為具有兩種互為手性對映的顏色和一種非手性顏色的著色平凡紐結(jié)[62].文獻[62]中方法的另一個意義是通過顏色集上的置換簡化了目標集置換群的作用，通過引入多面體全著色的概念以及簡化手性顏色軌道的計算，給出了該類多面體鏈環(huán)的計數(shù)公式，為研究更一般的多面體鏈環(huán)打下了很好的理論基礎[63-64].Harary 等[7]將生成函數(shù)處理樹的計數(shù)問題總結(jié)概括為“二十步”法，其核心是用分析的手段對生成函數(shù)的收斂域及臨界點(critical point)進行估計.本團隊運用這一方法給出了兩類樹狀分子結(jié)構的遞歸計數(shù)公式及漸近值[65].此外，在運用 Pólya 理論處理等價類的研究中，本團隊也提出了一個新的思想方法，其核心是將邊置換的每一個循環(huán)轉(zhuǎn)化為邊集在該置換所生成的群的作用下的等價類[66-67]，對處理圖的計數(shù)問題有很好的效果.

3 紐結(jié)理論及帶子圖

紐結(jié)的分類是紐結(jié)理論研究的基本問題，其基本思想是通過引入合適的不變量(多項式)來區(qū)分不同的紐結(jié).因此，對不變量的研究是紐結(jié)理論的重要課題.本團隊以組合數(shù)學和圖論為工具研究紐結(jié)不變量，在組合紐結(jié)理論及帶子圖理論這兩個拓撲學與圖論交叉領域取得了較好的研究成果，是國內(nèi)少有的涉足這一領域的研究團隊.

3.1 組合紐結(jié)理論

本團隊建立了更廣泛的基于圖的鏈環(huán)類的Homfly多項式與該圖的Tutte多項式的聯(lián)系[68].該工作大大拓展了著名組合紐結(jié)領域?qū)＜襃aeger F和Traldi L教授的工作，即從用個別整tangle覆蓋圖的邊推廣到用無窮類具有交錯定向的tangle覆蓋圖的邊，證明了排叉紐結(jié)Jones多項式零點在整個復平面上分布是稠密的[69]，該工作與統(tǒng)計物理密切關聯(lián).著名的紐結(jié)不變量專家Lin X S生前曾從事紐結(jié)Jones多項式的零點的研究，做了大量的數(shù)值試驗，數(shù)值結(jié)果顯示零點在復平面上有些空洞.本團隊的理論結(jié)果與Lin X S數(shù)值計算結(jié)果比較頗為意外，這可能是由于數(shù)值計算結(jié)果只考慮有限個(盡管很多)小的紐結(jié)，而本團隊考慮的是一類無限個紐結(jié)所造成的.

此外，本團隊還證明：除(2,n)環(huán)面結(jié)和(p,q,r)排叉結(jié)外，所有的素鏈環(huán)都對應一個cubic 3-polytope的符號平圖[70]，由此可以得到所有鏈環(huán)的Kauffman bracket多項式.最小stick數(shù)是紐結(jié)理論中的一個基本參數(shù).數(shù)學家很早就知道至少6個stick才能構成一個非平凡的紐結(jié)，即三葉結(jié).20世紀90年代，化學家在生物聚合物中發(fā)現(xiàn)了許多DNA紐結(jié)和蛋白質(zhì)紐結(jié)，可抽象為立方體格子中的紐結(jié).由此，人們開始關注立方晶格中紐結(jié)的最小長度.1992年，Diao[71]證明立方體格子中三葉結(jié)的最短長度是24.2005年，Huh[72]得到立方體格子中八字結(jié)的最少stick數(shù).本團隊證明：除了三葉結(jié)和八字結(jié)外，其他紐結(jié)的SL(K)均不小于 16，且交叉點指標為 5的兩個紐結(jié)SL(K)均為 16，并具體給出了 16 個線段拼成的 5 個交叉點的立方體紐結(jié)[73].

3.2 帶子圖理論

本團隊在扭曲對偶以及相關領域取得了系列成果：給出了平圖部分對偶中的歐拉圖的一個刻畫[76]，解決了Huggett[77]提出的一個問題；對任意帶子圖部分對偶圖中的二部圖和歐拉圖進行了刻畫；研究了極值帶子圖刻畫問題[78]，解決了文中提出的兩個關于環(huán)面嵌入圖的問題，并將相關結(jié)果推廣到更高虧格的曲面；證明了一個虛紐結(jié)是可圖的當且僅當它是棋盤可著色的[79]；將空間圖的Yamada多項式[80]推廣到虛空間圖；針對Gross等[81]引入的部分對偶定向虧格多項式和部分對偶歐拉虧格多項式，猜測不存在定向帶子圖且它的部分對偶虧格多項式只有一項且該項不是常數(shù)項的結(jié)論，本團隊分別給出了一類反例，并進一步猜測該反例在某種程度上是僅有的一類反例[82].

4 圖網(wǎng)絡及應用

圖網(wǎng)絡是現(xiàn)實各種網(wǎng)絡的統(tǒng)一抽象，在計算機科學、理論物理及信息生物學等領域扮演著重要的角色.本團隊在圖上隨機游動、電網(wǎng)絡及網(wǎng)絡優(yōu)化方面取得了較好的研究成果.

網(wǎng)絡上的隨機游動是一個隨機過程，與物理中的電網(wǎng)絡[83]、布朗運動、沙堆模型等各種擴散過程都有緊密的聯(lián)系[84].近年來，它更是被廣泛應用于各種復雜網(wǎng)絡的研究中，如社會網(wǎng)絡的關系預測、社團識別、萬維網(wǎng)的規(guī)模估計、網(wǎng)頁的排序等.此外，設計圖上的隨機游動來近似地處理一些經(jīng)典的特別是組合數(shù)學中的NP-困難問題，已成為當今的一個熱門研究課題.2002年，Kannan[85]在北京世界數(shù)學家大會45 min大會報告中對此做了較詳細的介紹；2006年Fields獎獲得者俄羅斯數(shù)學家Okounkov獲獎的工作也和隨機游動有關；Wolf獎獲得者Lovsz[84]在這方面也做了很多工作.

本團隊運用圖上的隨機游動和電網(wǎng)絡之間的緊密聯(lián)系，發(fā)現(xiàn)了隨機游動轉(zhuǎn)移矩陣的譜和電阻距離之間的一個優(yōu)美關系式.在此基礎上，提出了一個全新的拓撲指標：度乘Kirchhoff指標.該指標與Kirchhoff指標(由國際著名數(shù)學化學家Klein和Randic于1993年提出)以及度和Kirchhoff指標(由國際著名的數(shù)學化學家、塞爾維亞科學院及俄羅斯非線性科學院院士Gutman 于2012年提出)一起被稱為電阻距離的三大重要指標[86-87].進一步，本團隊給出了計算圖上電阻距離的兩種新方法：一是關于電阻距離的一個完備的局部和法則，從這個局部和法則不僅可以推得幾乎所有已知的和公式(如著名的Foster公式)，而且把任意兩圖之間電阻距離的計算問題轉(zhuǎn)化成解線性方程組問題；二是得到了電阻距離關于轉(zhuǎn)移矩陣及其最小多項式的一個全新表達式，利用此表達式得到了幾類圖任意兩點間電阻距離的具體表達式[88].在文獻[89]中首次運用圖上沙堆模型的常返構型和生成樹之間的一一對應關系，得到了一類廣義Bethe 格上沙堆模型的高度分布函數(shù)精確表達式，從而不僅理論上證明了物理學家Grassberger和Manna由數(shù)據(jù)模擬發(fā)現(xiàn)的結(jié)果，并且推廣了印度著名統(tǒng)計物理學家Dhar和Majumdar關于無限Bethe格高度分布函數(shù)的結(jié)果.在文獻[90]中運用圖的臨界群和圖的圈空間及割空間之間的關系，建立了一類變換圖-團插入圖的臨界群與其原圖臨界群之間的同態(tài).此外，本團隊運用代數(shù)和組合相結(jié)合的方法，證明了標準遺傳算法中變異算子的快速收斂性[91].

在網(wǎng)絡優(yōu)化理論中，高效、大容量、高可靠性、經(jīng)濟性的網(wǎng)絡設計具有重要的理論意義和應用價值，其中高效和高可靠性與圖的連通性密切相關，大量有實際應用背景的理論課題需要深入研究.在張?；凸鶗苑逶缙诘玫降膸最?-連通圖的可約鏈和臨界k-邊連通圖的構造方法[92-93]基礎上，本團隊進一步在臨界2-連通圖的構造方法、5-連通圖的可去邊和構造方法、k-連通圖的可去邊和k-連通圖的構造方法、各種有應用背景的特殊圖類的多種限制性連通度、超連通度等一系列課題研究中取得豐富的成果[94-104].

5 展 望

上述成果的取得為團隊今后的可持續(xù)發(fā)展打下了良好的基礎，特別是在匹配計數(shù)、組合計數(shù)及拓撲圖論等方面的部分成果具有很好的開創(chuàng)性，為進一步研究圖的各種計數(shù)多項式及紐結(jié)不變量提供了良好的思想方法.