圖論及其應用范更華福州大學離散數學研究中心離散數學及其應用教育部重點實驗室

現實世界中許多問題的數學抽象形式可以用圖來描述。如互聯網、交通網、通訊網、大規模集成電路、分子結構等都可以用圖來描述。對圖的研究形成了一個專門的數學分支：圖論（GraphTheory)。圖論(GraphTheory)圖的直觀定義：點與邊圖的抽象定義：一個集合上的二元關系圖的定義兩個長度為5的圈通過5條邊相連，也可如下構造：5個元素集合的所有2-子集作為點，兩點有邊相連當且僅當對應的2-子集不交。◆沒有長度小于5的圈◆沒有長度為10的圈(哈密頓圈)◆邊傳遞、點傳遞◆不是平面圖Petersen圖圖論結構圖論隨機圖論代數圖論拓撲圖論圖論分支離散數學

圖論是離散數學的一個主要分支廣泛應用背景的基礎研究與計算機科學密切相關離散數學

以蒸汽機的出現為標志的工業革命促進了以微積分為基礎的連續數學的發展。

以計算機的出現為標志的信息革命將促進離散數學的發展。計算機光纖網波長分配問題

在一個計算機光纖網絡中，給傳輸信道分配波長，兩信道若有公共部分，必須得到不同的波長。要求使用盡可能少的波長。波長分配問題轉化為圖論問題每條信道看作圖的一個點。兩點間有邊相連當且僅當它們對應的信道有公共部分。波長問題等價于所構造圖的點著色問題：

給圖的每個點著色，有邊相連的點須著不同的顏色。所用顏色盡可能少。圖的例子

交通網

互聯網

計算機處理器連接方式

集成電路板

分子結構圖

分子間相互作用及信息傳遞具體應用

大型高速計算機：處理器的連接方式互聯網：信息傳輸及控制管理大規模集成電路：布局、布線數據庫技術：數據的存儲、檢索理論計算機科學：

子圖理論對計算機算法研究的應用

DNA序列分析：圖的歐拉回路問題機器智能與模式識別：圖的同構通訊網絡：連通性，可靠性印刷電路板檢測:12萬5千次降為4次(《美國科學》ScientificAmerican,9(1997),92-94)具體應用

旅行推銷員問題問題提出:一個推銷員從公司出發,訪問若干指定城市,最后返回公司,要求設計最優旅行路線。(費用最小)

數學抽象:城市作為點,兩點間有邊相連,如果對應的城市間有直飛航班。機票價作為每條邊的權。求解:在圖中求一個圈過每點恰好一次,且邊的權之和最小。(最優哈密頓問題；比較：最優歐拉回路問題—中國郵遞員問題)難度:NP--完全問題應用:投幣電話、自動取鈔機、機器人行走路線設計旅行推銷員問題簡單情形:任意六個人中,必有3個互相認識,或三個互相不認識。

數學抽象:點代表人,兩點相連當且僅當對應的兩人認識。該圖要么有三角形,要么有三個點兩兩不連。Ramsey數問題證明：令G是6個點的圖，x為G中一個點。與x相鄰的點集記為N,與x不相鄰的點集記為R.情形I.|N|>2.若N中有兩點相連，則這兩點連同x構成一個三角形；若N中任意兩點均不相連，則N含三個兩兩不連的點。情形II.|N|<2.那么|R|>2.若R中有兩點不相連，則這兩點連同x是三個兩兩不連的點；若R中任意兩點均相連，則R含一個三角形。Ramsey數問題一般化:定義R(s,t)為最小整數使得任意R(s,t)個人中,要么有s個人兩兩認識,要么有t個人兩兩不認識。

R(3,3)=6R(4,4)=18R(5,5)=?Ramsey問題

應用廣、影響大。微軟研究中心的Kim因求解R(3,t)的工作而獲1997年Fulkerson獎。Ramsey數問題一般敘述:

圖的邊數大于某個數時,該圖具有某種性質,此數的最小值稱為該性質的極值.Mantel

定理(1907年):n點圖的邊數大于n2/4時,該圖含三角形,且n2/4是具有該性質的最小數.上述定理是Turan定理(1941年)的特殊情形.極值圖論Mantel定理的證明:

設G是不含三角形的n點圖,其最大點度數為t.不難證明G的邊數至多是f(t)=t(n-t).該二次函數在t=n/2處取得極大值:f(n/2)=n2/4.當n為偶數時,n個點的平衡完全二部圖不含三角形,且邊數恰為n2/4.因此,n2/4是具有該性質的最小數.極值圖論1852年,Morgan教授的一位學生問他:能否給出一個理由,為什么只需4

種顏色，就可給任意地圖的每個國家著色，使得有共同邊界的國家著不同的顏色。教授無語,該問題成為數學史上最著名問題之一,對它的研究推動了圖論,拓撲,代數的發展.歷史上許多著名數學家研究過四色問題并給出錯誤證明.四色問題當年,這位學生告訴Morgan教授:下面的例子說明3種顏色不夠,至少需4種顏色.四色問題轉化為圖論問題:點代表國家,兩點相連當且僅當對應的兩個國家有共同邊界。由此得到的圖是平面圖.四色問題:

每個平面圖可用4種顏色對其點著色,使得任何兩個有邊相連的點得到不同顏色.1976年,兩位計算機專家借助計算機驗證,解決了四色問題.未被數學界普遍接受.四色問題子圖覆蓋問題定義：若一個圖的某些子圖共同包含了該圖的所有邊，則稱該圖被這些子圖覆蓋。

子圖覆蓋問題：用具有某種特性的子圖來覆蓋一個圖。子圖覆蓋四色問題的一個等價形式:每個2-邊連通平面圖可被兩個偶圖覆蓋（偶圖：每個點與偶數條邊關聯;圈是連通極小偶圖）

哥德巴赫猜想:每個大于2的偶數是兩個素數之和。子圖覆蓋圖論:每個2-邊連通圖可被3個偶圖覆蓋。數論:每個充分大的奇數是3個素數之和。陳景潤定理:每個充分大的偶數是一個素數與不超過兩個素數的乘積之和。Seymour定理:每個2-邊連通圖可被一個偶圖及不超過兩個偶圖的并所覆蓋。子圖覆蓋哥尼斯堡七橋問題哥尼斯堡七橋問題1735年,歐拉(Euler)證明哥尼斯堡七橋問題無解,由此開創了數學的一個新分支---圖論.歐拉將哥尼斯堡七橋問題轉化為圖論問題:求圖中一條跡(walk),過每條邊一次且僅一次.后人將具有這種性質的跡稱為歐拉跡,閉的歐拉跡也稱為歐拉回路.歐拉定理:

連通圖存在歐拉跡當且僅當圖中奇度數的點的個數至多為2(若為0,則存在歐拉回路,這種圖稱為歐拉圖,也稱為偶圖)哥尼斯堡七橋問題歐拉定理

(圖論最古老的定理,1735年)：無奇度數點的連通圖(歐拉圖)存在歐拉回路（一筆劃）,且可被邊不交的圈覆蓋。次此定理未能回答需要多少個圈。二百多年來，人們一直試圖回答這個問題。

子圖覆蓋Hajos

猜想：n個點的歐拉圖可被[n/2]個邊不交的圈覆蓋。Erdos-Goodman-Posa

猜想(1966):存在常數c,n個點的歐拉圖可被cn

個邊不交的圈覆蓋。定理

(范更華，2003年)：n個點的歐拉圖可被[n/2]個圈覆蓋，且每條邊恰好被覆蓋奇數次。子圖覆蓋圈k-覆蓋:給定一個圖，對哪些正整數k，存在一組圈，使得圖中的每條邊恰好在k個圈上?這樣一組圈稱為該圖的一個圈k-覆蓋。 當k為奇數時，這個問題已解決；

然而當k為偶數時，至今仍未完全解決。60年代中，Edmonds（JohnvonNeumann獎得主）的匹配多面體理論為人們提供了有力工具，得以證明圈k-覆蓋對某個偶數k存在，但無法確定這個偶數的值。子圖覆蓋定理(BJJ1983)：當k是4的倍數，圈k-覆蓋存在。定理(Fan1992)：當k是6的倍數，圈k-覆蓋存在。推論：當k是大于2的偶數時，圈k-覆蓋存在。

唯獨k=2未能解決。圈2-覆蓋也被稱為圈雙覆蓋，至今仍是圖論界的一個著名難題。它是曲面拓撲中的強嵌入猜想的一個弱形式。子圖覆蓋圈雙覆蓋猜想（CycleDoubleCoverConjecture）每個2-邊連通圖存在圈2-覆蓋。

強嵌入猜想（StrongEmbeddingConjecture）每個2-連通圖可嵌入到某個曲面上，使得每個面的周界是一個圈（2-cell-embedding:eachfaceishomeomorphictoanopendisk）。子圖覆蓋

若我們不要求每條邊恰好在k個圈上，而只要求每條邊至少在一個圈上，這樣一組圈稱為該圖的一個圈覆蓋。所有這些圈的邊數之和稱為該圈覆蓋的長度。短圈覆蓋問題：尋找長度最短的圈覆蓋。Itai-Rodeh猜想（1978）：若圖的邊數為m，點數為n，則一定有長度不超過m+n-1的圈覆蓋。子圖覆蓋l

1985年，Alon（2002年世界數學家大會作１小時報告）證明存在長度不超過m+7(n-1)/3的圈覆蓋。l

1994年，Thomassen（丹麥科學院院士）證實了計算機算法專家Papadimitriou的猜測：短圈覆蓋問題是NP-完全。l

1998年，范更華徹底解決了Itai-Rodeh猜想，證明存在長度不超過m+n-1的圈覆蓋。子圖覆蓋未解決問題

(Itai-Rodeh，1978)：是否存在長度不超過7m/5

的圈覆蓋？若答案是肯定的，則推出圈2-覆蓋猜想成立。已知最好結果(BJJ，1983；Alon-Tarsi，1985)：存在長度不超過5m/3的圈覆蓋。子圖覆蓋整數流問題 給圖的每條邊一個定向及一個整數值,使得在圖的每個點,進入該點的所有邊的整數值之和等于離開該點的所有邊的整數值之和。整數流的一個例子

整數流的抽象定義

給定圖G和k階可換群A。若對G的某個定向,存在一個函數f

:從G的邊集到A的非零元素,使得在圖的每個一點,進入該點的邊的函數值之和等于離開該點的邊函數值之和,則稱f為G的一個k-流。

Tutte定理(1954年):平面圖可k著色當且僅當該圖存在k-流。

◆四色問題等價于平面圖的4-流存在性整數流與平面圖著色

5-流猜想：每個2-邊連通圖有5-流。4-流猜想：每個不含廣義Petersen子圖的2-邊連通圖有4-流。3-流猜想：每個4-邊連通圖有3-流。整數流三大猜想

弱3-流猜想：存在常數t，使得每個t-邊連通圖有3-流。此猜想與有限域向量空間堆壘基（AdditiveBasis）猜想有關聯，吸引了眾多國際一流學者。定理(Thomassen，2012):每個8-邊連通圖有3-流。(隨后被改進到：6-邊連通圖有3-流。)弱3-流猜想

整數流與數學其他領域的一些著名問題有關聯:

組合學:LonelyRunner

數論:DiophantineApproximation

幾何學:ViewObstruction有限域線性空間:AdditiveBasis

整數流理論孤獨的跑步者

n個人繞跑道以各自固有的速度跑步。他們在同一時間、同一起點起跑。是否存在某一時刻，某個跑步者“遠離”其余跑步者？數學定量描述

設跑道一圈的長度為1個單位。是否存在某個時刻、某跑步者與所有其余跑步者的距離至少是1/n單位。等價描述

n-1個人繞單位長度跑道以各自固有的速度從同一起點起跑。是否存在某個時刻，所有跑步者與起點的距離至少是1/n

？數學描述

n-1

個跑步者的速度分別為a1,a2,…,an-1

。

1

圈跑道相當于數軸上的一個單位，2

圈2

個單位，…,k圈k

個單位…。這樣，每個正整數均相當于跑道起點。是否存在時間t

,對每個

i,tai

與最近整數的距離至少是1/n?

數論難題（丟番圖逼近）

給定n-1個正整數

a1,a2,…,an-1,

是否存在實數t,使得對每個i,tai與最近整數的距離至少為1/n?

對n﹥5,

未解決世界難題。觀察者問題(ViewObstruction)大規模集成電路（VLSI）VeryLargeScaleIntegration

用半導體工藝技術將電子電路的電子元器件（電阻、電容、電感、晶體管、二極管、傳感器等）在一塊半導體材料（硅、砷化鎵）芯片上“一氣呵成”，互連成有獨立功能的電路和系統。亦稱為“芯片”（Chip）。

集成電路產業包括設計、芯片制造、封裝檢測三大部分。可形象地比喻為寫書、印刷、裝訂。顯然，設計最具原創性。“863”、“973”，及國家重大專項都把集成電路設計列入其中。集成電路設計所依賴的關鍵軟件EDA(ElectronicDesignAutomation),基本上全是進口。

(EDA軟件的研制涉及大量的圖論和組合優化問題.)集成電路產業

《國家中長期科學和技術發展規劃綱要》確定了16個重大專項作為我國科技發展的重中之重（總投資超過1萬億）。其中與集成電路有關的占了兩項:◆核心電子器件、高端通用芯片及基礎軟件◆極大規模集成電路制造技術及成套工藝我國集成電路產業發展前景硅園片上的芯片硅襯底drain硅襯底頂部保護層金屬層絕緣層凹進導電層導電層1961年早期芯片

4個晶體管和若干電阻

1990年Intel奔騰處理器芯片1.5cm2310萬晶體管奔Ⅳ芯片結構圖

2000年，0.18μm工藝，4千2百萬個晶體管頭發對最小特征尺寸為0.18μm的比較ContactholeLinewidth

Space~90mmMinimumICfeaturesize=0.18mm90mm0.18mm=500Crosssectionofhumanhair芯片中金屬層（介質腐蝕后呈立交橋狀）MetalLayersinaChip973項目：數學與其它領域交叉的若干專題（2006.6-2010.12)課題

：大規模集成電路設計中的圖論與代數方法負責人：范更華承擔單位：福州大學參加單位：北京大學、南開大學、山東大學

國家重點基礎研究發展計劃新一輪973項目：信息及相關領域若干重大需求的應用數學研究（2011.1-2015.12)課題

：大規模集成電路物理設計中關鍵應用數學理論和方法負責人：范更華承擔單位：福州大學參加單位：北大、南開、山東大學、四川大學

國家重點基礎研究發展計劃

研究大規模集成電路設計中的電路劃分、布圖、布線等問題。以圖論、組合優化、算法設計為主，為研制具有自主知識產權的大規模集成電路設計應用軟件提供理論支持，提高我國在EDA（ElectronicDesignAutomation）工具研制這一領域的基礎理論研究水平。973課題概述電路劃分布局布線原理圖輸入芯片制造版圖驗證數據導出芯片版圖設計三個主要部分：電路劃分、布圖、布線涉及大量圖論問題芯片版圖設計大規模集成電路設計的關鍵一步，其結果會影響后續的布局、布線等過程。由于需要布局的電路太大，且輸入輸出引腳數目受到芯片封裝工藝的限制，需要將整個電路劃分成若干模塊，要考慮模塊的大小、模塊間的連線等。電路劃分

是一個多約束、多目標的優化問題。它的理論抽象是圖論中的點集劃分（VertexPartition）問題:

給定一個圖G及邊集E(G)上的一個權函數w.對正整數k≤t，求點集V(G)的一個劃分(A1,A2,...,Am)使得k≤|Ai|≤t，1≤i≤m，且∑i<jw(Ai,Aj)盡可能小。電路劃分

最簡單情形：二部劃分且對每部分的點數不加限制，則等價于在給定賦權圖（允許負權）中找最大生成二部子圖。就一般圖而言，這是NP-困難。平面圖有多項式算法。其主要思想是：將所有奇圈（長度為奇數的圈）破壞，剩下的圖就是一個二部子圖。電路劃分求平面圖G的最大二部子圖求G中最小權和的邊集E使得G\E不含奇圈在對偶圖G*中求奇度點間的一組權和最小的路P使得G*\P不含奇度點在以奇度點為點集的賦權完全圖中求最小完美匹配（Edmonds多項式算法）電路劃分

若對每部分的點數加以限制，則有下述至今未解決的難題：平面圖二部劃分問題：對任何n頂點平面圖，是否存在一個頂點集的二部劃分(X,Y)使得：||X|-|Y||≤1且X與Y之間的邊的數目至多為n.電路劃分在完成電路劃分之后，通過布局規劃（floorplanning）把模塊安置在芯片的適當位置上，并滿足一定的要求，如面積最小、模塊間的連線最短且容易布通等。由于模塊間連線要占用芯片面積，布局時要為后一步的布線留下必要的布線通道。布局

若只考慮模塊間的互連關系，則問題成為典型的“二次分配”問題（QuadraticAssignmentProblem）：給定兩個n階矩陣A=(aij)n×n，B=(bij)n×n，求映射π:{1,2,…,n}→{1,2,…,n}使得

aij

bπ(i)π(j)

盡可能小。布局

目標是完成模塊間的互連，且滿足一定的要求，如減小連線總長度，減輕走線擁擠度，減少層間通孔數等。布線分為總體布線和詳細布線。總體布線是在布局完成后，將線網分配到合適的布線區域，確保布通率而不考慮走線的具體位置。詳細布線則最終確定走線的具體位置。

布線最小斯坦納樹(MinimumSteinerTree)問題：

給定一個賦權圖G及點集V(G)的一個子集S，求G中一個連結S的所有點的最小權樹。

S中的點對應模塊，通過添加斯坦納點構造斯坦納樹，減小連線總長度。總體布線中的數學問題總體布線中的數學問題總體布線中的數學問題詳細布線中的數學問題通道布線(兩層模型)

i:表示線網Ｎi的引腳，1≤i≤5；0:空線網。目標：用最少的線槽(Track)完成線網引腳的連接。所需線槽數稱為通道寬度(ChannelWidth)。１５２０２１１０３４０３０１25340023tracktrunkbranchviadogleg詳細布線中的數學問題對應每個通道布線可構造兩個圖。水平約束圖（horizontalconstraintgraph）：

頂點集

V={vi

＝I(Ni)：線網Ni最左端與最右端引腳所包含的閉區間}

邊集

E={vivj

:I(Ni)與I(Nj)相交}這是個無向的區間圖（intervalgraph）1

5

2

021103405301253400231234HCG詳細布線中的數學問題詳細布線中的數學問題

設e=vivj

是水平約束圖（HCG)中的一條邊,那么線網Ni與Nj不能使用同一個線槽，至少需要兩個線槽來完成Ni和Nj

的引腳的連接。

HCG的團數(CliqueNumber)給出通道寬度（線槽數）的下界。詳細布線中的數學問題垂直約束圖(verticalconstraintgraph)頂點集

V={vi＝Ni}有向邊集E

={(vi,vj):Ni與Nj有引腳在通道的同一列，且Ni引腳在Nj引腳之上}1

5

2

021103403012534002323415VCG詳細布線中的數學問題詳細布線中的數學問題

在無dogleg的雙層模型，垂直約束圖(VCG)中有向路上任意兩點所代表的線網不能使用同一個線槽。如果存在有向圈則不可布。

VCG中最長有向路的長度給出通道寬度（線槽數）的下界。詳細布線中的數學問題

對HCG中所有不相鄰的點對x和y，若它們在VCG中被有向路相連，則添加無向邊xy。記所得到的無向圖為MG。

MG的團數(CliqueNumber)給出通道寬度（線槽數）的下界。詳細布線中的數學問題

因HCG是區間圖，有多項式算法求它的團數(CliqueNumber)，但一般而言，求MG的團數是NP-完全，除非MG是弦圖(chordalgraph)。Algorithm(Paletal.,

2007):求MG的弦子圖(chordal

subgraph)的團數，給出通道寬度下界。詳細布線中的數學問題定理(FanandLiu,2011):令K是MG中的一個團(Clique)。設Kp=K﹨HCG，則(1)Kp中任意兩條邊要么相鄰，要么通過另一條邊相連;(2)Kp中的任意導出圈的長度至多是4。推論：令P是MG﹨HCG的非空連通分支，則(1)若P是樹，則ω(HCG+P)≤ω(HCG)+2;(2)若P僅含一個圈，則ω(HCG+P)≤ω(HCG)+3詳細布線中的數學問題定理(FanandLiu,2011):設D是MG上的一個無圈定向。若D包含VCG的定向，則定向D中最長有向路的長度給出通道寬度（線槽數）的上界；且存在這樣一個定向D*，使得D*中最長有向路的長度給出通道寬度的精確值。比較：MG的團數只能給出通道寬度的下屆，無法給出精確值。詳細布線中的數學問題定理(Szeszler,2003):n個線網的通道布線問題，若可解，則通道寬度（線槽數）至多為7n/4，且可多項式時間完成布線。定理(FanandGeng,2011):n個線網的通道布線問題，若可解，則通道寬度（線槽數）至多為3n/2，且可多項式時間完成布線。路覆蓋(PathCovering)問題：

給定圖G及G中一組路P

={P1,P2,…，Pk}，對每條邊e∈E(G)，定義P(e)為通過e的路的個數，即P(e)=|{Pi

:

e∈Pi,1≤i≤k}|

如果e代表一個通道，則P(e)為通道寬度，也即所需線槽數。詳細布線中的數學問題P

的覆蓋數：θ(P)=max