版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
圖論及其應(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ì)作1小時(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ì)作1小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)Ni的引腳,1≤i≤5;0:空線網(wǎng)。目標(biāo):用最少的線槽(Track)完成線網(wǎng)引腳的連接。所需線槽數(shù)稱為通道寬度(ChannelWidth)。1520211034030125340023tracktrunkbranchviadogleg詳細(xì)布線中的數(shù)學(xué)問題通道布線(兩層模型)152詳細(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ì)作1小時(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ì)作1小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)Ni的引腳,1≤i≤5;0:空線網(wǎng)。目標(biāo):用最少的線槽(Track)完成線網(wǎng)引腳的連接。所需線槽數(shù)稱為通道寬度(ChannelWidth)。1520211034030125340023tracktrunkbranchviadogleg詳細(xì)布線中的數(shù)學(xué)問題通道布線(兩層模型)152詳細(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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 爬蟲課程設(shè)計(jì)題目
- 關(guān)于面團(tuán)的活動(dòng)課程設(shè)計(jì)
- 嬰兒上衣項(xiàng)目評(píng)價(jià)分析報(bào)告
- 熱工自動(dòng)調(diào)節(jié)課程設(shè)計(jì)
- 房地產(chǎn)地價(jià)設(shè)計(jì)課程設(shè)計(jì)
- 汽車尾燈課程設(shè)計(jì)揚(yáng)州
- 北京聯(lián)合大學(xué)《家庭教育學(xué)》2022-2023學(xué)年第一學(xué)期期末試卷
- 北京聯(lián)合大學(xué)《會(huì)展管理學(xué)》2022-2023學(xué)年第一學(xué)期期末試卷
- 拾音器項(xiàng)目可行性實(shí)施報(bào)告
- 室內(nèi)戶型改造課程設(shè)計(jì)
- 北師大版生物八年級(jí)上冊(cè) 第20章 第1節(jié) 遺傳和變異現(xiàn)象(1)(教案)
- SL-T+62-2020水工建筑物水泥灌漿施工技術(shù)規(guī)范
- 人教版 年六年級(jí)數(shù)學(xué)上冊(cè)教案(全冊(cè))
- 民航英語(yǔ)1(山東聯(lián)盟)智慧樹知到課后章節(jié)答案2023年下青島恒星科技學(xué)院
- 消防安全重點(diǎn)單位標(biāo)準(zhǔn)化管理操作手冊(cè)
- 小學(xué)思政課《愛國(guó)主義教育》
- 服務(wù)器設(shè)備到貨驗(yàn)收
- 2023年北京市通州區(qū)城管協(xié)管員招聘筆試題庫(kù)及答案解析
- 思想道德與法治 第三章
- 兒童行為評(píng)估
- 農(nóng)藥顆粒劑及除草水劑項(xiàng)目可行性研究報(bào)告模版
評(píng)論
0/150
提交評(píng)論