圖論中的計(jì)數(shù)理論及其應(yīng)用

錢建國，金賢安，楊維玲

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

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

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

1 匹配理論及應(yīng)用

圖的匹配理論是圖論中非?；钴S的研究領(lǐng)域.著名圖論專家Lovsz(Wolf獎(jiǎng)及Abel獎(jiǎng)得主，國際數(shù)學(xué)家大會(huì)ICM邀請(qǐng)報(bào)告人，曾任國際數(shù)學(xué)聯(lián)盟主席)的專著《匹配理論》對(duì)匹配理論進(jìn)行了系統(tǒng)的論述[8].2006年Fields獎(jiǎng)獲得者Okounkov的獲獎(jiǎng)工作之一也與匹配計(jì)數(shù)理論有著密切的關(guān)系[4].在應(yīng)用方面，匹配理論中的匹配計(jì)數(shù)問題等價(jià)于統(tǒng)計(jì)物理中的二聚體(Dimer)問題，是統(tǒng)計(jì)物理計(jì)算可解模型的熱門研究對(duì)象[9-11].此外，匹配理論也是量子化學(xué)家研究芳香碳?xì)浠衔锏闹匾ぞ咧籟12-13]，如Kekule結(jié)構(gòu)及Clar 覆蓋[14].

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

1.1 匹配計(jì)數(shù)

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

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

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

1.2 應(yīng) 用

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

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

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

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

2 組合計(jì)數(shù)

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

2.1 容斥理論及應(yīng)用

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

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

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

2.2 Pólya計(jì)數(shù)理論在圖論中的應(yīng)用

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

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

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

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

3.1 組合紐結(jié)理論

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

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

3.2 帶子圖理論

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

4 圖網(wǎng)絡(luò)及應(yīng)用

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

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

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

在網(wǎng)絡(luò)優(yōu)化理論中，高效、大容量、高可靠性、經(jīng)濟(jì)性的網(wǎng)絡(luò)設(shè)計(jì)具有重要的理論意義和應(yīng)用價(jià)值，其中高效和高可靠性與圖的連通性密切相關(guān)，大量有實(shí)際應(yīng)用背景的理論課題需要深入研究.在張福基和郭曉峰早期得到的幾類2-連通圖的可約鏈和臨界k-邊連通圖的構(gòu)造方法[92-93]基礎(chǔ)上，本團(tuán)隊(duì)進(jìn)一步在臨界2-連通圖的構(gòu)造方法、5-連通圖的可去邊和構(gòu)造方法、k-連通圖的可去邊和k-連通圖的構(gòu)造方法、各種有應(yīng)用背景的特殊圖類的多種限制性連通度、超連通度等一系列課題研究中取得豐富的成果[94-104].

5 展 望

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