離散數(shù)學(xué)課件

圖論及其應(yīng)用范更華福州大學(xué)離散數(shù)學(xué)研究中心離散數(shù)學(xué)及其應(yīng)用教育部重點(diǎn)實(shí)驗(yàn)室圖論及其應(yīng)用范更華1

現(xiàn)實(shí)世界中許多問題的數(shù)學(xué)抽象形式可以用圖來描述。如互聯(lián)網(wǎng)、交通網(wǎng)、通訊網(wǎng)、大規(guī)模集成電路、分子結(jié)構(gòu)等都可以用圖來描述。對(duì)圖的研究形成了一個(gè)專門的數(shù)學(xué)分支：圖論（GraphTheory)。圖論(GraphTheory)現(xiàn)實(shí)世界中許多問題的數(shù)學(xué)抽象形式可以用圖的直觀定義：點(diǎn)與邊圖的抽象定義：一個(gè)集合上的二元關(guān)系圖的定義圖的直觀定義：點(diǎn)與邊圖的定義兩個(gè)長(zhǎng)度為5的圈通過5條邊相連，也可如下構(gòu)造：5個(gè)元素集合的所有2-子集作為點(diǎn)，兩點(diǎn)有邊相連當(dāng)且僅當(dāng)對(duì)應(yīng)的2-子集不交?！魶]有長(zhǎng)度小于5的圈◆沒有長(zhǎng)度為10的圈(哈密頓圈)◆邊傳遞、點(diǎn)傳遞◆不是平面圖Petersen圖兩個(gè)長(zhǎng)度為5的圈通過5條邊相連，也可如Petersen圖論結(jié)構(gòu)圖論隨機(jī)圖論代數(shù)圖論拓?fù)鋱D論圖論分支圖論結(jié)構(gòu)圖論隨機(jī)圖論代數(shù)圖論拓?fù)鋱D論圖論分支5離散數(shù)學(xué)

圖論是離散數(shù)學(xué)的一個(gè)主要分支廣泛應(yīng)用背景的基礎(chǔ)研究與計(jì)算機(jī)科學(xué)密切相關(guān)離散數(shù)學(xué)圖論是離散數(shù)學(xué)的一個(gè)主要分支離散數(shù)學(xué)

以蒸汽機(jī)的出現(xiàn)為標(biāo)志的工業(yè)革命促進(jìn)了以微積分為基礎(chǔ)的連續(xù)數(shù)學(xué)的發(fā)展。

以計(jì)算機(jī)的出現(xiàn)為標(biāo)志的信息革命將促進(jìn)離散數(shù)學(xué)的發(fā)展。離散數(shù)學(xué)以蒸汽機(jī)的出現(xiàn)為標(biāo)志的工業(yè)革命促進(jìn)了計(jì)算機(jī)光纖網(wǎng)波長(zhǎng)分配問題

在一個(gè)計(jì)算機(jī)光纖網(wǎng)絡(luò)中，給傳輸信道分配波長(zhǎng)，兩信道若有公共部分，必須得到不同的波長(zhǎng)。要求使用盡可能少的波長(zhǎng)。計(jì)算機(jī)光纖網(wǎng)波長(zhǎng)分配問題 在一個(gè)計(jì)算機(jī)光纖網(wǎng)絡(luò)8離散數(shù)學(xué)課件9波長(zhǎng)分配問題轉(zhuǎn)化為圖論問題每條信道看作圖的一個(gè)點(diǎn)。兩點(diǎn)間有邊相連當(dāng)且僅當(dāng)它們對(duì)應(yīng)的信道有公共部分。波長(zhǎng)問題等價(jià)于所構(gòu)造圖的點(diǎn)著色問題：

給圖的每個(gè)點(diǎn)著色，有邊相連的點(diǎn)須著不同的顏色。所用顏色盡可能少。波長(zhǎng)分配問題轉(zhuǎn)化為圖論問題每條信道看作圖的一個(gè)點(diǎn)。兩點(diǎn)間有邊圖的例子

交通網(wǎng)

互聯(lián)網(wǎng)

計(jì)算機(jī)處理器連接方式

集成電路板

分子結(jié)構(gòu)圖

分子間相互作用及信息傳遞圖的例子交通網(wǎng)具體應(yīng)用

大型高速計(jì)算機(jī)：處理器的連接方式互聯(lián)網(wǎng)：信息傳輸及控制管理大規(guī)模集成電路：布局、布線數(shù)據(jù)庫(kù)技術(shù)：數(shù)據(jù)的存儲(chǔ)、檢索理論計(jì)算機(jī)科學(xué)：

子圖理論對(duì)計(jì)算機(jī)算法研究的應(yīng)用

具體應(yīng)用大型高速計(jì)算機(jī)：處理器的連接方式DNA序列分析：圖的歐拉回路問題機(jī)器智能與模式識(shí)別：圖的同構(gòu)通訊網(wǎng)絡(luò)：連通性，可靠性印刷電路板檢測(cè):12萬5千次降為4次(《美國(guó)科學(xué)》ScientificAmerican,9(1997),92-94)具體應(yīng)用

DNA序列分析：圖的歐拉回路問題具體應(yīng)用13

旅行推銷員問題問題提出:一個(gè)推銷員從公司出發(fā),訪問若干指定城市,最后返回公司,要求設(shè)計(jì)最優(yōu)旅行路線。(費(fèi)用最小)

數(shù)學(xué)抽象:城市作為點(diǎn),兩點(diǎn)間有邊相連,如果對(duì)應(yīng)的城市間有直飛航班。機(jī)票價(jià)作為每條邊的權(quán)。旅行推銷員問題問題提出:一個(gè)推銷員從公司出發(fā),訪求解:在圖中求一個(gè)圈過每點(diǎn)恰好一次,且邊的權(quán)之和最小。(最優(yōu)哈密頓問題；比較：最優(yōu)歐拉回路問題—中國(guó)郵遞員問題)難度:NP--完全問題應(yīng)用:投幣電話、自動(dòng)取鈔機(jī)、機(jī)器人行走路線設(shè)計(jì)旅行推銷員問題求解:在圖中求一個(gè)圈過每點(diǎn)恰好一次,且邊的權(quán)之和最小。(15簡(jiǎn)單情形:任意六個(gè)人中,必有3個(gè)互相認(rèn)識(shí),或三個(gè)互相不認(rèn)識(shí)。

數(shù)學(xué)抽象:點(diǎn)代表人,兩點(diǎn)相連當(dāng)且僅當(dāng)對(duì)應(yīng)的兩人認(rèn)識(shí)。該圖要么有三角形,要么有三個(gè)點(diǎn)兩兩不連。Ramsey數(shù)問題簡(jiǎn)單情形:任意六個(gè)人中,必有3個(gè)互相Ramsey數(shù)問題證明：令G是6個(gè)點(diǎn)的圖，x為G中一個(gè)點(diǎn)。與x相鄰的點(diǎn)集記為N,與x不相鄰的點(diǎn)集記為R.情形I.|N|>2.若N中有兩點(diǎn)相連，則這兩點(diǎn)連同x構(gòu)成一個(gè)三角形；若N中任意兩點(diǎn)均不相連，則N含三個(gè)兩兩不連的點(diǎn)。情形II.|N|<2.那么|R|>2.若R中有兩點(diǎn)不相連，則這兩點(diǎn)連同x是三個(gè)兩兩不連的點(diǎn)；若R中任意兩點(diǎn)均相連，則R含一個(gè)三角形。Ramsey數(shù)問題證明：令G是6個(gè)點(diǎn)的圖，x為G中一個(gè)點(diǎn)。與xRamsey數(shù)問一般化:定義R(s,t)為最小整數(shù)使得任意R(s,t)個(gè)人中,要么有s個(gè)人兩兩認(rèn)識(shí),要么有t個(gè)人兩兩不認(rèn)識(shí)。

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

應(yīng)用廣、影響大。微軟研究中心的Kim因求解R(3,t)的工作而獲1997年Fulkerson獎(jiǎng)。Ramsey數(shù)問題一般化:定義R(s,t)為最小整數(shù)使得任意R(s,t)個(gè)人18一般敘述:

圖的邊數(shù)大于某個(gè)數(shù)時(shí),該圖具有某種性質(zhì),此數(shù)的最小值稱為該性質(zhì)的極值.Mantel

定理(1907年):n點(diǎn)圖的邊數(shù)大于n2/4時(shí),該圖含三角形,且n2/4是具有該性質(zhì)的最小數(shù).上述定理是Turan定理(1941年)的特殊情形.極值圖論一般敘述:圖的邊數(shù)大于某個(gè)數(shù)時(shí),該圖具有某種性質(zhì),此數(shù)的最19Mantel定理的證明:

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

種顏色，就可給任意地圖的每個(gè)國(guó)家著色，使得有共同邊界的國(guó)家著不同的顏色。教授無語(yǔ),該問題成為數(shù)學(xué)史上最著名問題之一,對(duì)它的研究推動(dòng)了圖論,拓?fù)?代數(shù)的發(fā)展.歷史上許多著名數(shù)學(xué)家研究過四色問題并給出錯(cuò)誤證明.四色問題1852年,Morgan教授的一位學(xué)生問他:能否給四色問21當(dāng)年,這位學(xué)生告訴Morgan教授:下面的例子說明3種顏色不夠,至少需4種顏色.四色問題當(dāng)年,這位學(xué)生告訴Morgan教授:下面的例子說明3種顏色22轉(zhuǎn)化為圖論問題:點(diǎn)代表國(guó)家,兩點(diǎn)相連當(dāng)且僅當(dāng)對(duì)應(yīng)的兩個(gè)國(guó)家有共同邊界。由此得到的圖是平面圖.四色問題:

每個(gè)平面圖可用4種顏色對(duì)其點(diǎn)著色,使得任何兩個(gè)有邊相連的點(diǎn)得到不同顏色.1976年,兩位計(jì)算機(jī)專家借助計(jì)算機(jī)驗(yàn)證,解決了四色問題.未被數(shù)學(xué)界普遍接受.四色問題轉(zhuǎn)化為圖論問題:點(diǎn)代表國(guó)家,兩點(diǎn)相連當(dāng)且僅當(dāng)對(duì)應(yīng)的兩個(gè)國(guó)23子圖覆蓋問題定義：若一個(gè)圖的某些子圖共同包含了該圖的所有邊，則稱該圖被這些子圖覆蓋。

子圖覆蓋問題：用具有某種特性的子圖來覆蓋一個(gè)圖。子圖覆蓋問題定義：若一個(gè)圖的某些子圖共同包含了該24子圖覆蓋子圖覆蓋25四色問題的一個(gè)等價(jià)形式:每個(gè)2-邊連通平面圖可被兩個(gè)偶圖覆蓋（偶圖：每個(gè)點(diǎn)與偶數(shù)條邊關(guān)聯(lián);圈是連通極小偶圖）

哥德巴赫猜想:每個(gè)大于2的偶數(shù)是兩個(gè)素?cái)?shù)之和。子圖覆蓋四色問題的一個(gè)等價(jià)形式:每個(gè)2-邊連通平面圖可被兩個(gè)偶圖覆26圖論:每個(gè)2-邊連通圖可被3個(gè)偶圖覆蓋。數(shù)論:每個(gè)充分大的奇數(shù)是3個(gè)素?cái)?shù)之和。陳景潤(rùn)定理:每個(gè)充分大的偶數(shù)是一個(gè)素?cái)?shù)與不超過兩個(gè)素?cái)?shù)的乘積之和。Seymour定理:每個(gè)2-邊連通圖可被一個(gè)偶圖及不超過兩個(gè)偶圖的并所覆蓋。子圖覆蓋圖論:每個(gè)2-邊連通圖可被3個(gè)偶圖覆蓋。子圖覆蓋27哥尼斯堡七橋問題哥尼斯堡七橋問題28哥尼斯堡七橋問題1735年,歐拉(Euler)證明哥尼斯堡七橋問題無解,由此開創(chuàng)了數(shù)學(xué)的一個(gè)新分支---圖論.歐拉將哥尼斯堡七橋問題轉(zhuǎn)化為圖論問題:求圖中一條跡(walk),過每條邊一次且僅一次.后人將具有這種性質(zhì)的跡稱為歐拉跡,閉的歐拉跡也稱為歐拉回路.歐拉定理:

連通圖存在歐拉跡當(dāng)且僅當(dāng)圖中奇度數(shù)的點(diǎn)的個(gè)數(shù)至多為2(若為0,則存在歐拉回路,這種圖稱為歐拉圖,也稱為偶圖)哥尼斯堡七橋問題1735年,歐拉(Euler)證明哥尼斯堡29哥尼斯堡七橋問題哥尼斯堡七橋問題30歐拉定理

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

子圖覆蓋歐拉定理(圖論最古老的定理,1735年)：子圖覆蓋31Hajos猜想：n個(gè)點(diǎn)的歐拉圖可被[n/2]個(gè)邊不交的圈覆蓋。Erdos-Goodman-Posa猜想(1966):存在常數(shù)c,n個(gè)點(diǎn)的歐拉圖可被cn

個(gè)邊不交的圈覆蓋。定理

(范更華，2003年)：n個(gè)點(diǎn)的歐拉圖可被[n/2]個(gè)圈覆蓋，且每條邊恰好被覆蓋奇數(shù)次。子圖覆蓋Hajos猜想：n個(gè)點(diǎn)的歐拉圖可被[n/2]個(gè)邊不交的圈覆32圈k-覆蓋:給定一個(gè)圖，對(duì)哪些正整數(shù)k，存在一組圈，使得圖中的每條邊恰好在k個(gè)圈上?這樣一組圈稱為該圖的一個(gè)圈k-覆蓋。 當(dāng)k為奇數(shù)時(shí)，這個(gè)問題已解決；

然而當(dāng)k為偶數(shù)時(shí)，至今仍未完全解決。60年代中，Edmonds（JohnvonNeumann獎(jiǎng)得主）的匹配多面體理論為人們提供了有力工具，得以證明圈k-覆蓋對(duì)某個(gè)偶數(shù)k存在，但無法確定這個(gè)偶數(shù)的值。子圖覆蓋圈k-覆蓋:給定一個(gè)圖，對(duì)哪些正整數(shù)k，存在一組圈，使得圖33定理(BJJ1983)：當(dāng)k是4的倍數(shù)，圈k-覆蓋存在。定理(Fan1992)：當(dāng)k是6的倍數(shù)，圈k-覆蓋存在。推論：當(dāng)k是大于2的偶數(shù)時(shí)，圈k-覆蓋存在。 唯獨(dú)k=2未能解決。圈2-覆蓋也被稱為圈雙覆蓋，至今仍是圖論界的一個(gè)著名難題。它是曲面拓?fù)渲械膹?qiáng)嵌入猜想的一個(gè)弱形式。子圖覆蓋定理(BJJ1983)：當(dāng)k是4的倍數(shù)，圈k-覆蓋存在。子34圈雙覆蓋猜想（CycleDoubleCoverConjecture）每個(gè)2-邊連通圖存在圈2-覆蓋。

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

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

1985年，Alon（2002年世界數(shù)學(xué)家大會(huì)作１小時(shí)報(bào)告）證明存在長(zhǎng)度不超過m+7(n-1)/3的圈覆蓋。l

1994年，Thomassen（丹麥科學(xué)院院士）證實(shí)了計(jì)算機(jī)算法專家Papadimitriou的猜測(cè)：短圈覆蓋問題是NP-完全。l

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

1985年，Alon（2002年世界數(shù)學(xué)家大會(huì)作１小37未解決問題

(Itai-Rodeh，1978)：是否存在長(zhǎng)度不超過7m/5的圈覆蓋？若答案是肯定的，則推出圈2-覆蓋猜想成立。已知最好結(jié)果(BJJ，1983；Alon-Tarsi，1985)：存在長(zhǎng)度不超過5m/3的圈覆蓋。子圖覆蓋未解決問題(Itai-Rodeh，1978)：是否存在長(zhǎng)度38整數(shù)流問題 給圖的每條邊一個(gè)定向及一個(gè)整數(shù)值,使得在圖的每個(gè)點(diǎn),進(jìn)入該點(diǎn)的所有邊的整數(shù)值之和等于離開該點(diǎn)的所有邊的整數(shù)值之和。整數(shù)流問題 給圖的每條邊一個(gè)定向及一個(gè)整數(shù)值,使得在圖的整數(shù)流的一個(gè)例子

整數(shù)流的一個(gè)例子40整數(shù)流的抽象定義

給定圖G和k階可換群A。若對(duì)G的某個(gè)定向,存在一個(gè)函數(shù)f

:從G的邊集到A的非零元素,使得在圖的每個(gè)一點(diǎn),進(jìn)入該點(diǎn)的邊的函數(shù)值之和等于離開該點(diǎn)的邊函數(shù)值之和,則稱f為G的一個(gè)k-流。整數(shù)流的抽象定義給定圖G和k階可換

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

◆四色問題等價(jià)于平面圖的4-流存在性整數(shù)流與平面圖著色 Tutte定理(1954年):平面圖可k著色當(dāng)且僅當(dāng)該圖

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

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

整數(shù)流與數(shù)學(xué)其他領(lǐng)域的一些著名問題有關(guān)聯(lián):

組合學(xué):LonelyRunner

數(shù)論:DiophantineApproximation

幾何學(xué):ViewObstruction有限域線性空間:AdditiveBasis

整數(shù)流理論整數(shù)流與數(shù)學(xué)其他領(lǐng)域的一些著名問題有關(guān)聯(lián):整數(shù)流理論45離散數(shù)學(xué)課件46孤獨(dú)的跑步者

n個(gè)人繞跑道以各自固有的速度跑步。他們?cè)谕粫r(shí)間、同一起點(diǎn)起跑。是否存在某一時(shí)刻，某個(gè)跑步者“遠(yuǎn)離”其余跑步者？孤獨(dú)的跑步者n個(gè)人繞跑道以各自固有的速度跑步。他們數(shù)學(xué)定量描述

設(shè)跑道一圈的長(zhǎng)度為1個(gè)單位。是否存在某個(gè)時(shí)刻、某跑步者與所有其余跑步者的距離至少是1/n單位。數(shù)學(xué)定量描述設(shè)跑道一圈的長(zhǎng)度為1個(gè)單位。是等價(jià)描述

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

？等價(jià)描述n-1個(gè)人繞單位長(zhǎng)度跑道以各自固數(shù)學(xué)描述

n-1

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

。

1

圈跑道相當(dāng)于數(shù)軸上的一個(gè)單位，2

圈2

個(gè)單位，…,k圈k

個(gè)單位…。這樣，每個(gè)正整數(shù)均相當(dāng)于跑道起點(diǎn)。是否存在時(shí)間t

,對(duì)每個(gè)i,tai

與最近整數(shù)的距離至少是1/n?數(shù)學(xué)描述n-1個(gè)跑步者的速度分別

數(shù)論難題（丟番圖逼近）

給定n-1個(gè)正整數(shù)a1,a2,…,an-1,

是否存在實(shí)數(shù)t,使得對(duì)每個(gè)i,tai與最近整數(shù)的距離至少為1/n?

對(duì)n﹥5,

未解決世界難題。數(shù)論難題（丟番圖逼近）觀察者問題(ViewObstruction)觀察者問題(ViewObstruction)52大規(guī)模集成電路（VLSI）VeryLargeScaleIntegration

用半導(dǎo)體工藝技術(shù)將電子電路的電子元器件（電阻、電容、電感、晶體管、二極管、傳感器等）在一塊半導(dǎo)體材料（硅、砷化鎵）芯片上“一氣呵成”，互連成有獨(dú)立功能的電路和系統(tǒng)。亦稱為“芯片”（Chip）。大規(guī)模集成電路（VLSI）

集成電路產(chǎn)業(yè)包括設(shè)計(jì)、芯片制造、封裝檢測(cè)三大部分?？尚蜗蟮乇扔鳛閷憰?、印刷、裝訂。顯然，設(shè)計(jì)最具原創(chuàng)性?！?63”、“973”，及國(guó)家重大專項(xiàng)都把集成電路設(shè)計(jì)列入其中。集成電路設(shè)計(jì)所依賴的關(guān)鍵軟件EDA(ElectronicDesignAutomation),基本上全是進(jìn)口。

(EDA軟件的研制涉及大量的圖論和組合優(yōu)化問題.)集成電路產(chǎn)業(yè)集成電路產(chǎn)業(yè)包括設(shè)計(jì)、芯片制造、封裝檢測(cè)三大部分?？尚蜗?4

《國(guó)家中長(zhǎng)期科學(xué)和技術(shù)發(fā)展規(guī)劃綱要》確定了16個(gè)重大專項(xiàng)作為我國(guó)科技發(fā)展的重中之重（總投資超過1萬億）。其中與集成電路有關(guān)的占了兩項(xiàng):◆核心電子器件、高端通用芯片及基礎(chǔ)軟件◆極大規(guī)模集成電路制造技術(shù)及成套工藝我國(guó)集成電路產(chǎn)業(yè)發(fā)展前景《國(guó)家中長(zhǎng)期科學(xué)和技術(shù)發(fā)展規(guī)劃綱要》確定了16個(gè)重大專項(xiàng)55硅園片上的芯片硅襯底drain硅襯底頂部保護(hù)層金屬層絕緣層凹進(jìn)導(dǎo)電層導(dǎo)電層硅園片上的芯片硅襯底drain硅襯底頂部保護(hù)層金屬層絕緣層凹561961年早期芯片

4個(gè)晶體管和若干電阻1961年早期芯片457

1990年Intel奔騰處理器芯片1.5cm2310萬晶體管1990年Intel奔騰處理器芯片58奔Ⅳ芯片結(jié)構(gòu)圖

2000年，0.18μm工藝，4千2百萬個(gè)晶體管奔Ⅳ芯片結(jié)構(gòu)圖2000年，0.18μm工藝，4千2頭發(fā)對(duì)最小特征尺寸為0.18μm的比較ContactholeLinewidth

Space~90mmMinimumICfeaturesize=0.18mm90mm0.18mm=500Crosssectionofhumanhair頭發(fā)對(duì)最小特征尺寸為0.18μm的比較Contacthol芯片中金屬層（介質(zhì)腐蝕后呈立交橋狀）MetalLayersinaChip芯片中金屬層（介質(zhì)腐蝕后呈立交橋狀）MetalLayers973項(xiàng)目：數(shù)學(xué)與其它領(lǐng)域交叉的若干專題（2006.6-2010.12)課題

：大規(guī)模集成電路設(shè)計(jì)中的圖論與代數(shù)方法負(fù)責(zé)人：范更華承擔(dān)單位：福州大學(xué)參加單位：北京大學(xué)、南開大學(xué)、山東大學(xué)

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃973項(xiàng)目：數(shù)學(xué)與其它領(lǐng)域交叉的若干專題國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展62新一輪973項(xiàng)目：信息及相關(guān)領(lǐng)域若干重大需求的應(yīng)用數(shù)學(xué)研究（2011.1-2015.12)課題

：大規(guī)模集成電路物理設(shè)計(jì)中關(guān)鍵應(yīng)用數(shù)學(xué)理論和方法負(fù)責(zé)人：范更華承擔(dān)單位：福州大學(xué)參加單位：北大、南開、山東大學(xué)、四川大學(xué)

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃新一輪973項(xiàng)目：信息及相關(guān)領(lǐng)域若干重大需求的應(yīng)用數(shù)學(xué)研究（63

研究大規(guī)模集成電路設(shè)計(jì)中的電路劃分、布圖、布線等問題。以圖論、組合優(yōu)化、算法設(shè)計(jì)為主，為研制具有自主知識(shí)產(chǎn)權(quán)的大規(guī)模集成電路設(shè)計(jì)應(yīng)用軟件提供理論支持，提高我國(guó)在EDA（ElectronicDesignAutomation）工具研制這一領(lǐng)域的基礎(chǔ)理論研究水平。973課題概述研究大規(guī)模集成電路設(shè)計(jì)中的電路劃分、布圖、布線等電路劃分布局布線原理圖輸入芯片制造版圖驗(yàn)證數(shù)據(jù)導(dǎo)出芯片版圖設(shè)計(jì)電路劃分布局布線原芯片制造版圖驗(yàn)證數(shù)據(jù)導(dǎo)出芯片版圖設(shè)計(jì)三個(gè)主要部分：電路劃分、布圖、布線涉及大量圖論問題芯片版圖設(shè)計(jì)三個(gè)主要部分：芯片版圖設(shè)計(jì)66大規(guī)模集成電路設(shè)計(jì)的關(guān)鍵一步，其結(jié)果會(huì)影響后續(xù)的布局、布線等過程。由于需要布局的電路太大，且輸入輸出引腳數(shù)目受到芯片封裝工藝的限制，需要將整個(gè)電路劃分成若干模塊，要考慮模塊的大小、模塊間的連線等。電路劃分大規(guī)模集成電路設(shè)計(jì)的關(guān)鍵一步，其結(jié)果會(huì)影響后續(xù)的布

是一個(gè)多約束、多目標(biāo)的優(yōu)化問題。它的理論抽象是圖論中的點(diǎn)集劃分（VertexPartition）問題:

給定一個(gè)圖G及邊集E(G)上的一個(gè)權(quán)函數(shù)w.對(duì)正整數(shù)k≤t，求點(diǎn)集V(G)的一個(gè)劃分(A1,A2,...,Am)使得k≤|Ai|≤t，1≤i≤m，且∑i<jw(Ai,Aj)盡可能小。電路劃分是一個(gè)多約束、多目標(biāo)的優(yōu)化問題。它的理論抽

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

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

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

aijbπ(i)π(j)

盡可能小。布局若只考慮模塊間的互連關(guān)系，則問題成為典型的“二次分配”問

目標(biāo)是完成模塊間的互連，且滿足一定的要求，如減小連線總長(zhǎng)度，減輕走線擁擠度，減少層間通孔數(shù)等。布線分為總體布線和詳細(xì)布線?？傮w布線是在布局完成后，將線網(wǎng)分配到合適的布線區(qū)域，確保布通率而不考慮走線的具體位置。詳細(xì)布線則最終確定走線的具體位置。

布線目標(biāo)是完成模塊間的互連，且滿足一定的要求，如減小連線74最小斯坦納樹(MinimumSteinerTree)問題：

給定一個(gè)賦權(quán)圖G及點(diǎn)集V(G)的一個(gè)子集S，求G中一個(gè)連結(jié)S的所有點(diǎn)的最小權(quán)樹。

S中的點(diǎn)對(duì)應(yīng)模塊，通過添加斯坦納點(diǎn)構(gòu)造斯坦納樹，減小連線總長(zhǎng)度?？傮w布線中的數(shù)學(xué)問題最小斯坦納樹(MinimumSteinerTree)問題75總體布線中的數(shù)學(xué)問題總體布線中的數(shù)學(xué)問題總體布線中的數(shù)學(xué)問題總體布線中的數(shù)學(xué)問題詳細(xì)布線中的數(shù)學(xué)問題通道布線(兩層模型)

i:表示線網(wǎng)Ｎi的引腳，1≤i≤5；0:空線網(wǎng)。目標(biāo)：用最少的線槽(Track)完成線網(wǎng)引腳的連接。所需線槽數(shù)稱為通道寬度(ChannelWidth)。１５２０２１１０３４０３０１25340023tracktrunkbranchviadogleg詳細(xì)布線中的數(shù)學(xué)問題通道布線(兩層模型)１５２詳細(xì)布線中的數(shù)學(xué)問題對(duì)應(yīng)每個(gè)通道布線可構(gòu)造兩個(gè)圖。水平約束圖（horizontalconstraintgraph）：

頂點(diǎn)集

V={vi

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

邊集

E={vivj:I(Ni)與I(Nj)相交}這是個(gè)無向的區(qū)間圖（intervalgraph）詳細(xì)布線中的數(shù)學(xué)問題對(duì)應(yīng)每個(gè)通道布線可構(gòu)造兩個(gè)圖。1

5

2

021103405301253400231234HCG詳細(xì)布線中的數(shù)學(xué)問題1520211詳細(xì)布線中的數(shù)學(xué)問題

設(shè)e=vivj

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

的引腳的連接。

HCG的團(tuán)數(shù)(CliqueNumber)給出通道寬度（線槽數(shù)）的下界。詳細(xì)布線中的數(shù)學(xué)問題設(shè)e=vivj是詳細(xì)布線中的數(shù)學(xué)問題垂直約束圖(verticalconstraintgraph)頂點(diǎn)集

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

={(vi,vj):Ni與Nj有引腳在通道的同一列，且Ni引腳在Nj引腳之上}詳細(xì)布線中的數(shù)學(xué)問題垂直約束圖(verticalconst1

5

2

021103403012534002323415VCG詳細(xì)布線中的數(shù)學(xué)問題1520211詳細(xì)布線中的數(shù)學(xué)問題

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

VCG中最長(zhǎng)有向路的長(zhǎng)度給出通道寬度（線槽數(shù)）的下界。詳細(xì)布線中的數(shù)學(xué)問題在無dogleg的雙層模型，垂直約束詳細(xì)布線中的數(shù)學(xué)問題

對(duì)HCG中所有不相鄰的點(diǎn)對(duì)x和y，若它們?cè)赩CG中被有向路相連，則添加無向邊xy。記所得到的無向圖為MG。

MG的團(tuán)數(shù)(CliqueNumber)給出通道寬度（線槽數(shù)）的下界。詳細(xì)布線中的數(shù)學(xué)問題對(duì)HCG中所有不相鄰的點(diǎn)對(duì)x和y，若詳細(xì)布線中的數(shù)學(xué)問題

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

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

給定圖G及G中一組路P

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

:

e∈Pi,1≤i≤k}|

如果e代表一個(gè)通道，則P(e)為通道寬度，也即所需線槽數(shù)。詳細(xì)布線中的數(shù)學(xué)問題路覆蓋(PathCovering)問題：詳細(xì)布線中的數(shù)學(xué)問90P

的覆蓋數(shù)：θ(P)=max{P(e):

e∈E(G)}

反映了布線方案的擁擠度。給定P，求圖中的一組路Q={Q1,Q2,…,Qk}，使得Qi與Pi有相同的端點(diǎn)，1≤i≤k，且θ(Q)＜θ(P).詳細(xì)布線中的數(shù)學(xué)問題P的覆蓋數(shù)：詳細(xì)布線中的數(shù)學(xué)問題91

給定n點(diǎn)圖G，是否存在一組路

P

={P1,P2,…,Pk}及常數(shù)m，使得對(duì)每條邊

e，

1≤P(e)≤m若對(duì)k

不加限制，則答案顯然。若對(duì)k

加以限制，則有下述著名猜想。Gallai猜想:k≤[(n+1)/2]

且m＝1弱Gallai猜想(Chung，1980):k≤[(n+1)/2]圖論中的路覆蓋問題給定n點(diǎn)圖G，是否存在一組路P={P1,P2,92圖論研究國(guó)際概況

David‘sReport把離散數(shù)學(xué)列在4個(gè)未來數(shù)學(xué)發(fā)展趨向的第二位，把圖論列為數(shù)學(xué)學(xué)科的核心研究領(lǐng)域。

國(guó)際大公司，如貝爾、IBM、微軟等都擁有一批一流的圖論專家。圖論研究國(guó)際概況David‘sReport把離散數(shù)

已故數(shù)學(xué)大師Erdos(Wolf獎(jiǎng)得主)為現(xiàn)代圖論的發(fā)展作出了歷史性的貢獻(xiàn)。Lovasz:1999年Wolf獎(jiǎng)得主，世界數(shù)學(xué)家大會(huì)1小時(shí)報(bào)告，上屆國(guó)際數(shù)學(xué)聯(lián)盟（IMU）主席。Seymour:普林斯頓大學(xué)數(shù)學(xué)系教授,世界數(shù)學(xué)家大會(huì)1小時(shí)報(bào)告。Alon：曾任2006年世界數(shù)學(xué)家大會(huì)程序委員會(huì)主席。國(guó)際圖論界代表人物國(guó)際圖論界代表人物德國(guó)波恩(Bonn)大學(xué)離散數(shù)學(xué)研究所ResearchInstituteforDiscreteMathematics

自主開發(fā)了一套EDA工具—BonnTools1987年開始與IBM合作，已有上千款I(lǐng)BM

芯片的設(shè)計(jì)用了BonnTools2005年開始與Magma合作，現(xiàn)今

BonnTools已成為Magma產(chǎn)品的一部分德國(guó)波恩(Bonn)大學(xué)離散數(shù)學(xué)研究所ResearchIn95國(guó)內(nèi)研究現(xiàn)狀

◆“九五”、“十五”、“十一五”圖論與組合數(shù)學(xué)均被國(guó)家基金委設(shè)為重點(diǎn)項(xiàng)目◆中科院數(shù)學(xué)與系統(tǒng)科學(xué)研究院成立了“圖論與組合開放實(shí)驗(yàn)室”◆南開大學(xué)成立了“組合數(shù)學(xué)研究中心”◆福州大學(xué)成立了“離散數(shù)學(xué)研究中心”國(guó)內(nèi)研究現(xiàn)狀◆“九五”、“十五”、“十一五”圖論在集成電路設(shè)計(jì)領(lǐng)域與北京華大電子設(shè)計(jì)有限公司（北京華大九天軟件有限公司）建立了很好的合作關(guān)系，有望將理論研究成果應(yīng)用于華大電子擁有的“九天”系列EDA工具（93年獲得國(guó)家科技進(jìn)步一等獎(jiǎng)）。中心師生已先后多次到北京華大參與他們的新產(chǎn)品研發(fā)，幫助解決新產(chǎn)品研發(fā)中的實(shí)際問題。福州大學(xué)離散數(shù)學(xué)研究中心在集成電路設(shè)計(jì)領(lǐng)域與北京華大電子設(shè)計(jì)有限公司（北京華大九97離散數(shù)學(xué)課件謝謝各位福州大學(xué)離散數(shù)學(xué)研究中心中心網(wǎng)頁(yè)：謝謝各位福州大學(xué)離散數(shù)學(xué)研究中心中心網(wǎng)頁(yè)：http99圖論及其應(yīng)用范更華福州大學(xué)離散數(shù)學(xué)研究中心離散數(shù)學(xué)及其應(yīng)用教育部重點(diǎn)實(shí)驗(yàn)室圖論及其應(yīng)用范更華100

現(xiàn)實(shí)世界中許多問題的數(shù)學(xué)抽象形式可以用圖來描述。如互聯(lián)網(wǎng)、交通網(wǎng)、通訊網(wǎng)、大規(guī)模集成電路、分子結(jié)構(gòu)等都可以用圖來描述。對(duì)圖的研究形成了一個(gè)專門的數(shù)學(xué)分支：圖論（GraphTheory)。圖論(GraphTheory)現(xiàn)實(shí)世界中許多問題的數(shù)學(xué)抽象形式可以用圖的直觀定義：點(diǎn)與邊圖的抽象定義：一個(gè)集合上的二元關(guān)系圖的定義圖的直觀定義：點(diǎn)與邊圖的定義兩個(gè)長(zhǎng)度為5的圈通過5條邊相連，也可如下構(gòu)造：5個(gè)元素集合的所有2-子集作為點(diǎn)，兩點(diǎn)有邊相連當(dāng)且僅當(dāng)對(duì)應(yīng)的2-子集不交?！魶]有長(zhǎng)度小于5的圈◆沒有長(zhǎng)度為10的圈(哈密頓圈)◆邊傳遞、點(diǎn)傳遞◆不是平面圖Petersen圖兩個(gè)長(zhǎng)度為5的圈通過5條邊相連，也可如Petersen圖論結(jié)構(gòu)圖論隨機(jī)圖論代數(shù)圖論拓?fù)鋱D論圖論分支圖論結(jié)構(gòu)圖論隨機(jī)圖論代數(shù)圖論拓?fù)鋱D論圖論分支104離散數(shù)學(xué)

圖論是離散數(shù)學(xué)的一個(gè)主要分支廣泛應(yīng)用背景的基礎(chǔ)研究與計(jì)算機(jī)科學(xué)密切相關(guān)離散數(shù)學(xué)圖論是離散數(shù)學(xué)的一個(gè)主要分支離散數(shù)學(xué)

以蒸汽機(jī)的出現(xiàn)為標(biāo)志的工業(yè)革命促進(jìn)了以微積分為基礎(chǔ)的連續(xù)數(shù)學(xué)的發(fā)展。

以計(jì)算機(jī)的出現(xiàn)為標(biāo)志的信息革命將促進(jìn)離散數(shù)學(xué)的發(fā)展。離散數(shù)學(xué)以蒸汽機(jī)的出現(xiàn)為標(biāo)志的工業(yè)革命促進(jìn)了計(jì)算機(jī)光纖網(wǎng)波長(zhǎng)分配問題

在一個(gè)計(jì)算機(jī)光纖網(wǎng)絡(luò)中，給傳輸信道分配波長(zhǎng)，兩信道若有公共部分，必須得到不同的波長(zhǎng)。要求使用盡可能少的波長(zhǎng)。計(jì)算機(jī)光纖網(wǎng)波長(zhǎng)分配問題 在一個(gè)計(jì)算機(jī)光纖網(wǎng)絡(luò)107離散數(shù)學(xué)課件108波長(zhǎng)分配問題轉(zhuǎn)化為圖論問題每條信道看作圖的一個(gè)點(diǎn)。兩點(diǎn)間有邊相連當(dāng)且僅當(dāng)它們對(duì)應(yīng)的信道有公共部分。波長(zhǎng)問題等價(jià)于所構(gòu)造圖的點(diǎn)著色問題：

給圖的每個(gè)點(diǎn)著色，有邊相連的點(diǎn)須著不同的顏色。所用顏色盡可能少。波長(zhǎng)分配問題轉(zhuǎn)化為圖論問題每條信道看作圖的一個(gè)點(diǎn)。兩點(diǎn)間有邊圖的例子

交通網(wǎng)

互聯(lián)網(wǎng)

計(jì)算機(jī)處理器連接方式

集成電路板

分子結(jié)構(gòu)圖

分子間相互作用及信息傳遞圖的例子交通網(wǎng)具體應(yīng)用

大型高速計(jì)算機(jī)：處理器的連接方式互聯(lián)網(wǎng)：信息傳輸及控制管理大規(guī)模集成電路：布局、布線數(shù)據(jù)庫(kù)技術(shù)：數(shù)據(jù)的存儲(chǔ)、檢索理論計(jì)算機(jī)科學(xué)：

子圖理論對(duì)計(jì)算機(jī)算法研究的應(yīng)用

具體應(yīng)用大型高速計(jì)算機(jī)：處理器的連接方式DNA序列分析：圖的歐拉回路問題機(jī)器智能與模式識(shí)別：圖的同構(gòu)通訊網(wǎng)絡(luò)：連通性，可靠性印刷電路板檢測(cè):12萬5千次降為4次(《美國(guó)科學(xué)》ScientificAmerican,9(1997),92-94)具體應(yīng)用

DNA序列分析：圖的歐拉回路問題具體應(yīng)用112

旅行推銷員問題問題提出:一個(gè)推銷員從公司出發(fā),訪問若干指定城市,最后返回公司,要求設(shè)計(jì)最優(yōu)旅行路線。(費(fèi)用最小)

數(shù)學(xué)抽象:城市作為點(diǎn),兩點(diǎn)間有邊相連,如果對(duì)應(yīng)的城市間有直飛航班。機(jī)票價(jià)作為每條邊的權(quán)。旅行推銷員問題問題提出:一個(gè)推銷員從公司出發(fā),訪求解:在圖中求一個(gè)圈過每點(diǎn)恰好一次,且邊的權(quán)之和最小。(最優(yōu)哈密頓問題；比較：最優(yōu)歐拉回路問題—中國(guó)郵遞員問題)難度:NP--完全問題應(yīng)用:投幣電話、自動(dòng)取鈔機(jī)、機(jī)器人行走路線設(shè)計(jì)旅行推銷員問題求解:在圖中求一個(gè)圈過每點(diǎn)恰好一次,且邊的權(quán)之和最小。(114簡(jiǎn)單情形:任意六個(gè)人中,必有3個(gè)互相認(rèn)識(shí),或三個(gè)互相不認(rèn)識(shí)。

數(shù)學(xué)抽象:點(diǎn)代表人,兩點(diǎn)相連當(dāng)且僅當(dāng)對(duì)應(yīng)的兩人認(rèn)識(shí)。該圖要么有三角形,要么有三個(gè)點(diǎn)兩兩不連。Ramsey數(shù)問題簡(jiǎn)單情形:任意六個(gè)人中,必有3個(gè)互相Ramsey數(shù)問題證明：令G是6個(gè)點(diǎn)的圖，x為G中一個(gè)點(diǎn)。與x相鄰的點(diǎn)集記為N,與x不相鄰的點(diǎn)集記為R.情形I.|N|>2.若N中有兩點(diǎn)相連，則這兩點(diǎn)連同x構(gòu)成一個(gè)三角形；若N中任意兩點(diǎn)均不相連，則N含三個(gè)兩兩不連的點(diǎn)。情形II.|N|<2.那么|R|>2.若R中有兩點(diǎn)不相連，則這兩點(diǎn)連同x是三個(gè)兩兩不連的點(diǎn)；若R中任意兩點(diǎn)均相連，則R含一個(gè)三角形。Ramsey數(shù)問題證明：令G是6個(gè)點(diǎn)的圖，x為G中一個(gè)點(diǎn)。與xRamsey數(shù)問一般化:定義R(s,t)為最小整數(shù)使得任意R(s,t)個(gè)人中,要么有s個(gè)人兩兩認(rèn)識(shí),要么有t個(gè)人兩兩不認(rèn)識(shí)。

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

應(yīng)用廣、影響大。微軟研究中心的Kim因求解R(3,t)的工作而獲1997年Fulkerson獎(jiǎng)。Ramsey數(shù)問題一般化:定義R(s,t)為最小整數(shù)使得任意R(s,t)個(gè)人117一般敘述:

圖的邊數(shù)大于某個(gè)數(shù)時(shí),該圖具有某種性質(zhì),此數(shù)的最小值稱為該性質(zhì)的極值.Mantel

定理(1907年):n點(diǎn)圖的邊數(shù)大于n2/4時(shí),該圖含三角形,且n2/4是具有該性質(zhì)的最小數(shù).上述定理是Turan定理(1941年)的特殊情形.極值圖論一般敘述:圖的邊數(shù)大于某個(gè)數(shù)時(shí),該圖具有某種性質(zhì),此數(shù)的最118Mantel定理的證明:

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

種顏色，就可給任意地圖的每個(gè)國(guó)家著色，使得有共同邊界的國(guó)家著不同的顏色。教授無語(yǔ),該問題成為數(shù)學(xué)史上最著名問題之一,對(duì)它的研究推動(dòng)了圖論,拓?fù)?代數(shù)的發(fā)展.歷史上許多著名數(shù)學(xué)家研究過四色問題并給出錯(cuò)誤證明.四色問題1852年,Morgan教授的一位學(xué)生問他:能否給四色問120當(dāng)年,這位學(xué)生告訴Morgan教授:下面的例子說明3種顏色不夠,至少需4種顏色.四色問題當(dāng)年,這位學(xué)生告訴Morgan教授:下面的例子說明3種顏色121轉(zhuǎn)化為圖論問題:點(diǎn)代表國(guó)家,兩點(diǎn)相連當(dāng)且僅當(dāng)對(duì)應(yīng)的兩個(gè)國(guó)家有共同邊界。由此得到的圖是平面圖.四色問題:

每個(gè)平面圖可用4種顏色對(duì)其點(diǎn)著色,使得任何兩個(gè)有邊相連的點(diǎn)得到不同顏色.1976年,兩位計(jì)算機(jī)專家借助計(jì)算機(jī)驗(yàn)證,解決了四色問題.未被數(shù)學(xué)界普遍接受.四色問題轉(zhuǎn)化為圖論問題:點(diǎn)代表國(guó)家,兩點(diǎn)相連當(dāng)且僅當(dāng)對(duì)應(yīng)的兩個(gè)國(guó)122子圖覆蓋問題定義：若一個(gè)圖的某些子圖共同包含了該圖的所有邊，則稱該圖被這些子圖覆蓋。

子圖覆蓋問題：用具有某種特性的子圖來覆蓋一個(gè)圖。子圖覆蓋問題定義：若一個(gè)圖的某些子圖共同包含了該123子圖覆蓋子圖覆蓋124四色問題的一個(gè)等價(jià)形式:每個(gè)2-邊連通平面圖可被兩個(gè)偶圖覆蓋（偶圖：每個(gè)點(diǎn)與偶數(shù)條邊關(guān)聯(lián);圈是連通極小偶圖）

哥德巴赫猜想:每個(gè)大于2的偶數(shù)是兩個(gè)素?cái)?shù)之和。子圖覆蓋四色問題的一個(gè)等價(jià)形式:每個(gè)2-邊連通平面圖可被兩個(gè)偶圖覆125圖論:每個(gè)2-邊連通圖可被3個(gè)偶圖覆蓋。數(shù)論:每個(gè)充分大的奇數(shù)是3個(gè)素?cái)?shù)之和。陳景潤(rùn)定理:每個(gè)充分大的偶數(shù)是一個(gè)素?cái)?shù)與不超過兩個(gè)素?cái)?shù)的乘積之和。Seymour定理:每個(gè)2-邊連通圖可被一個(gè)偶圖及不超過兩個(gè)偶圖的并所覆蓋。子圖覆蓋圖論:每個(gè)2-邊連通圖可被3個(gè)偶圖覆蓋。子圖覆蓋126哥尼斯堡七橋問題哥尼斯堡七橋問題127哥尼斯堡七橋問題1735年,歐拉(Euler)證明哥尼斯堡七橋問題無解,由此開創(chuàng)了數(shù)學(xué)的一個(gè)新分支---圖論.歐拉將哥尼斯堡七橋問題轉(zhuǎn)化為圖論問題:求圖中一條跡(walk),過每條邊一次且僅一次.后人將具有這種性質(zhì)的跡稱為歐拉跡,閉的歐拉跡也稱為歐拉回路.歐拉定理:

連通圖存在歐拉跡當(dāng)且僅當(dāng)圖中奇度數(shù)的點(diǎn)的個(gè)數(shù)至多為2(若為0,則存在歐拉回路,這種圖稱為歐拉圖,也稱為偶圖)哥尼斯堡七橋問題1735年,歐拉(Euler)證明哥尼斯堡128哥尼斯堡七橋問題哥尼斯堡七橋問題129歐拉定理

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

子圖覆蓋歐拉定理(圖論最古老的定理,1735年)：子圖覆蓋130Hajos猜想：n個(gè)點(diǎn)的歐拉圖可被[n/2]個(gè)邊不交的圈覆蓋。Erdos-Goodman-Posa猜想(1966):存在常數(shù)c,n個(gè)點(diǎn)的歐拉圖可被cn

個(gè)邊不交的圈覆蓋。定理

(范更華，2003年)：n個(gè)點(diǎn)的歐拉圖可被[n/2]個(gè)圈覆蓋，且每條邊恰好被覆蓋奇數(shù)次。子圖覆蓋Hajos猜想：n個(gè)點(diǎn)的歐拉圖可被[n/2]個(gè)邊不交的圈覆131圈k-覆蓋:給定一個(gè)圖，對(duì)哪些正整數(shù)k，存在一組圈，使得圖中的每條邊恰好在k個(gè)圈上?這樣一組圈稱為該圖的一個(gè)圈k-覆蓋。 當(dāng)k為奇數(shù)時(shí)，這個(gè)問題已解決；

然而當(dāng)k為偶數(shù)時(shí)，至今仍未完全解決。60年代中，Edmonds（JohnvonNeumann獎(jiǎng)得主）的匹配多面體理論為人們提供了有力工具，得以證明圈k-覆蓋對(duì)某個(gè)偶數(shù)k存在，但無法確定這個(gè)偶數(shù)的值。子圖覆蓋圈k-覆蓋:給定一個(gè)圖，對(duì)哪些正整數(shù)k，存在一組圈，使得圖132定理(BJJ1983)：當(dāng)k是4的倍數(shù)，圈k-覆蓋存在。定理(Fan1992)：當(dāng)k是6的倍數(shù)，圈k-覆蓋存在。推論：當(dāng)k是大于2的偶數(shù)時(shí)，圈k-覆蓋存在。 唯獨(dú)k=2未能解決。圈2-覆蓋也被稱為圈雙覆蓋，至今仍是圖論界的一個(gè)著名難題。它是曲面拓?fù)渲械膹?qiáng)嵌入猜想的一個(gè)弱形式。子圖覆蓋定理(BJJ1983)：當(dāng)k是4的倍數(shù)，圈k-覆蓋存在。子133圈雙覆蓋猜想（CycleDoubleCoverConjecture）每個(gè)2-邊連通圖存在圈2-覆蓋。

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

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

1985年，Alon（2002年世界數(shù)學(xué)家大會(huì)作１小時(shí)報(bào)告）證明存在長(zhǎng)度不超過m+7(n-1)/3的圈覆蓋。l

1994年，Thomassen（丹麥科學(xué)院院士）證實(shí)了計(jì)算機(jī)算法專家Papadimitriou的猜測(cè)：短圈覆蓋問題是NP-完全。l

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

1985年，Alon（2002年世界數(shù)學(xué)家大會(huì)作１小136未解決問題

(Itai-Rodeh，1978)：是否存在長(zhǎng)度不超過7m/5的圈覆蓋？若答案是肯定的，則推出圈2-覆蓋猜想成立。已知最好結(jié)果(BJJ，1983；Alon-Tarsi，1985)：存在長(zhǎng)度不超過5m/3的圈覆蓋。子圖覆蓋未解決問題(Itai-Rodeh，1978)：是否存在長(zhǎng)度137整數(shù)流問題 給圖的每條邊一個(gè)定向及一個(gè)整數(shù)值,使得在圖的每個(gè)點(diǎn),進(jìn)入該點(diǎn)的所有邊的整數(shù)值之和等于離開該點(diǎn)的所有邊的整數(shù)值之和。整數(shù)流問題 給圖的每條邊一個(gè)定向及一個(gè)整數(shù)值,使得在圖的整數(shù)流的一個(gè)例子

整數(shù)流的一個(gè)例子139整數(shù)流的抽象定義

給定圖G和k階可換群A。若對(duì)G的某個(gè)定向,存在一個(gè)函數(shù)f

:從G的邊集到A的非零元素,使得在圖的每個(gè)一點(diǎn),進(jìn)入該點(diǎn)的邊的函數(shù)值之和等于離開該點(diǎn)的邊函數(shù)值之和,則稱f為G的一個(gè)k-流。整數(shù)流的抽象定義給定圖G和k階可換

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

◆四色問題等價(jià)于平面圖的4-流存在性整數(shù)流與平面圖著色 Tutte定理(1954年):平面圖可k著色當(dāng)且僅當(dāng)該圖

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

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

整數(shù)流與數(shù)學(xué)其他領(lǐng)域的一些著名問題有關(guān)聯(lián):

組合學(xué):LonelyRunner

數(shù)論:DiophantineApproximation

幾何學(xué):ViewObstruction有限域線性空間:AdditiveBasis

整數(shù)流理論整數(shù)流與數(shù)學(xué)其他領(lǐng)域的一些著名問題有關(guān)聯(lián):整數(shù)流理論144離散數(shù)學(xué)課件145孤獨(dú)的跑步者

n個(gè)人繞跑道以各自固有的速度跑步。他們?cè)谕粫r(shí)間、同一起點(diǎn)起跑。是否存在某一時(shí)刻，某個(gè)跑步者“遠(yuǎn)離”其余跑步者？孤獨(dú)的跑步者n個(gè)人繞跑道以各自固有的速度跑步。他們數(shù)學(xué)定量描述

設(shè)跑道一圈的長(zhǎng)度為1個(gè)單位。是否存在某個(gè)時(shí)刻、某跑步者與所有其余跑步者的距離至少是1/n單位。數(shù)學(xué)定量描述設(shè)跑道一圈的長(zhǎng)度為1個(gè)單位。是等價(jià)描述

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

？等價(jià)描述n-1個(gè)人繞單位長(zhǎng)度跑道以各自固數(shù)學(xué)描述

n-1

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

。

1

圈跑道相當(dāng)于數(shù)軸上的一個(gè)單位，2

圈2

個(gè)單位，…,k圈k

個(gè)單位…。這樣，每個(gè)正整數(shù)均相當(dāng)于跑道起點(diǎn)。是否存在時(shí)間t

,對(duì)每個(gè)i,tai

與最近整數(shù)的距離至少是1/n?數(shù)學(xué)描述n-1個(gè)跑步者的速度分別

數(shù)論難題（丟番圖逼近）

給定n-1個(gè)正整數(shù)a1,a2,…,an-1,

是否存在實(shí)數(shù)t,使得對(duì)每個(gè)i,tai與最近整數(shù)的距離至少為1/n?

對(duì)n﹥5,

未解決世界難題。數(shù)論難題（丟番圖逼近）觀察者問題(ViewObstruction)觀察者問題(ViewObstruction)151大規(guī)模集成電路（VLSI）VeryLargeScaleIntegration

用半導(dǎo)體工藝技術(shù)將電子電路的電子元器件（電阻、電容、電感、晶體管、二極管、傳感器等）在一塊半導(dǎo)體材料（硅、砷化鎵）芯片上“一氣呵成”，互連成有獨(dú)立功能的電路和系統(tǒng)。亦稱為“芯片”（Chip）。大規(guī)模集成電路（VLSI）

集成電路產(chǎn)業(yè)包括設(shè)計(jì)、芯片制造、封裝檢測(cè)三大部分?？尚蜗蟮乇扔鳛閷憰?、印刷、裝訂。顯然，設(shè)計(jì)最具原創(chuàng)性。“863”、“973”，及國(guó)家重大專項(xiàng)都把集成電路設(shè)計(jì)列入其中。集成電路設(shè)計(jì)所依賴的關(guān)鍵軟件EDA(ElectronicDesignAutomation),基本上全是進(jìn)口。

(EDA軟件的研制涉及大量的圖論和組合優(yōu)化問題.)集成電路產(chǎn)業(yè)集成電路產(chǎn)業(yè)包括設(shè)計(jì)、芯片制造、封裝檢測(cè)三大部分?？尚蜗?53

《國(guó)家中長(zhǎng)期科學(xué)和技術(shù)發(fā)展規(guī)劃綱要》確定了16個(gè)重大專項(xiàng)作為我國(guó)科技發(fā)展的重中之重（總投資超過1萬億）。其中與集成電路有關(guān)的占了兩項(xiàng):◆核心電子器件、高端通用芯片及基礎(chǔ)軟件◆極大規(guī)模集成電路制造技術(shù)及成套工藝我國(guó)集成電路產(chǎn)業(yè)發(fā)展前景《國(guó)家中長(zhǎng)期科學(xué)和技術(shù)發(fā)展規(guī)劃綱要》確定了16個(gè)重大專項(xiàng)154硅園片上的芯片硅襯底drain硅襯底頂部保護(hù)層金屬層絕緣層凹進(jìn)導(dǎo)電層導(dǎo)電層硅園片上的芯片硅襯底drain硅襯底頂部保護(hù)層金屬層絕緣層凹1551961年早期芯片

4個(gè)晶體管和若干電阻1961年早期芯片4156

1990年Intel奔騰處理器芯片1.5cm2310萬晶體管1990年Intel奔騰處理器芯片157奔Ⅳ芯片結(jié)構(gòu)圖

2000年，0.18μm工藝，4千2百萬個(gè)晶體管奔Ⅳ芯片結(jié)構(gòu)圖2000年，0.18μm工藝，4千2頭發(fā)對(duì)最小特征尺寸為0.18μm的比較ContactholeLinewidth

Space~90mmMinimumICfeaturesize=0.18mm90mm0.18mm=500Crosssectionofhumanhair頭發(fā)對(duì)最小特征尺寸為0.18μm的比較Contacthol芯片中金屬層（介質(zhì)腐蝕后呈立交橋狀）MetalLayersinaChip芯片中金屬層（介質(zhì)腐蝕后呈立交橋狀）MetalLayers973項(xiàng)目：數(shù)學(xué)與其它領(lǐng)域交叉的若干專題（2006.6-2010.12)課題

：大規(guī)模集成電路設(shè)計(jì)中的圖論與代數(shù)方法負(fù)責(zé)人：范更華承擔(dān)單位：福州大學(xué)參加單位：北京大學(xué)、南開大學(xué)、山東大學(xué)

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃973項(xiàng)目：數(shù)學(xué)與其它領(lǐng)域交叉的若干專題國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展161新一輪973項(xiàng)目：信息及相關(guān)領(lǐng)域若干重大需求的應(yīng)用數(shù)學(xué)研究（2011.1-2015.12)課題

：大規(guī)模集成電路物理設(shè)計(jì)中關(guān)鍵應(yīng)用數(shù)學(xué)理論和方法負(fù)責(zé)人：范更華承擔(dān)單位：福州大學(xué)參加單位：北大、南開、山東大學(xué)、四川大學(xué)

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃新一輪973項(xiàng)目：信息及相關(guān)領(lǐng)域若干重大需求的應(yīng)用數(shù)學(xué)研究（162

研究大規(guī)模集成電路設(shè)計(jì)中的電路劃分、布圖、布線等問題。以圖論、組合優(yōu)化、算法設(shè)計(jì)為主，為研制具有自主知識(shí)產(chǎn)權(quán)的大規(guī)模集成電路設(shè)計(jì)應(yīng)用軟件提供理論支持，提高我國(guó)在EDA（ElectronicDesignAutomation）工具研制這一領(lǐng)域的基礎(chǔ)理論研究水平。973課題概述研究大規(guī)模集成電路設(shè)計(jì)中的電路劃分、布圖、布線等電路劃分布局布線原理圖輸入芯片制造版圖驗(yàn)證數(shù)據(jù)導(dǎo)出芯片版圖設(shè)計(jì)電路劃分布局布線原芯片制造版圖驗(yàn)證數(shù)據(jù)導(dǎo)出芯片版圖設(shè)計(jì)三個(gè)主要部分：電路劃分、布圖、布線涉及大量圖論問題芯片版圖設(shè)計(jì)三個(gè)主要部分：芯片版圖設(shè)計(jì)165大規(guī)模集成電路設(shè)計(jì)的關(guān)鍵一步，其結(jié)果會(huì)影響后續(xù)的布局、布線等過程。由于需要布局的電路太大，且輸入輸出引腳數(shù)目受到芯片封裝工藝的限制，需要將整個(gè)電路劃分成若干模塊，要考慮模塊的大小、模塊間的連線等。電路劃分大規(guī)模集成電路設(shè)計(jì)的關(guān)鍵一步，其結(jié)果會(huì)影響后續(xù)的布

是一個(gè)多約束、多目標(biāo)的優(yōu)化問題。它的理論抽象是圖論中的點(diǎn)集劃分（VertexPartition）問題:

給定一個(gè)圖G及邊集E(G)上的一個(gè)權(quán)函數(shù)w.對(duì)正整數(shù)k≤t，求點(diǎn)集V(G)的一個(gè)劃分(A1,A2,...,Am)使得k≤|Ai|≤t，1≤i≤m，且∑i<jw(Ai,Aj)盡可能小。電路劃分是一個(gè)多約束、多目標(biāo)的優(yōu)化問題。它的理論抽

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

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

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

aijbπ(i)π(j)

盡可能小。布局若只考慮模塊間的互連關(guān)系，則問題成為典型的“二次分配”問

目標(biāo)是完成模塊間的互連，且滿足一定的要求，如減小連線總長(zhǎng)度，減輕走線擁擠度，減少層間通孔數(shù)等。布線分為總體布線和詳細(xì)布線?？傮w布線是在布局完成后，將線網(wǎng)分配到合適的布線區(qū)域，確保布通率而不考慮走線的具體位置。詳細(xì)布線則最終確定走線的具體位置。

布線目標(biāo)是完成模塊間的互連，且滿足一定的要求，如減小連線173最小斯坦納樹(MinimumSteinerTree)問題：

給定一個(gè)賦權(quán)圖G及點(diǎn)集V(G)的一個(gè)子集S，求G中一個(gè)連結(jié)S的所有點(diǎn)的最小權(quán)樹。

S中的點(diǎn)對(duì)應(yīng)模塊，通過添加斯坦納點(diǎn)構(gòu)造斯坦納樹，減小連線總長(zhǎng)度?？傮w布線中的數(shù)學(xué)問題最小斯坦納樹(MinimumSteinerTree)問題174總體布線中的數(shù)學(xué)問題總體布線中的數(shù)學(xué)問題總體布線中的數(shù)學(xué)問題總體布線中的數(shù)學(xué)問題詳細(xì)布線中的數(shù)學(xué)問題通道布線(兩層模型)

i:表示線網(wǎng)Ｎi的引腳，1≤i≤5；0:空線網(wǎng)。目標(biāo)：用最少的線槽(Track)完成線網(wǎng)引腳的連接。所需線槽數(shù)稱為通道寬度(ChannelWidth)。１５２０２１１０３４０３０１25340023tracktrunkbranchviadogleg詳細(xì)布線中的數(shù)學(xué)問題通道布線(兩層模型)１５２詳細(xì)布線中的數(shù)學(xué)問題對(duì)應(yīng)每個(gè)通道布線可構(gòu)造兩個(gè)圖。水平約束圖（horizontalconstraintgraph）：

頂點(diǎn)集

V={vi

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

邊集

E={vivj:I(Ni)與I(Nj)相交}這是個(gè)無向的區(qū)間圖（intervalgraph）詳細(xì)布線中的數(shù)學(xué)問題對(duì)應(yīng)每個(gè)通道布線可構(gòu)造兩個(gè)圖。1

5

2

021103405301253400231234HCG詳細(xì)布線中的數(shù)學(xué)問題1520211詳細(xì)布線中的數(shù)學(xué)問題

設(shè)e=vivj

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

的引腳的連接。

HCG的團(tuán)數(shù)(CliqueNumber)給出通道寬度（線槽數(shù)）的下界。詳細(xì)布線中的數(shù)學(xué)問題設(shè)e=vivj是詳細(xì)布線中的數(shù)學(xué)問題垂直約束圖(verticalconstraintgraph)頂點(diǎn)集

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

={(vi