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

圖論是離散數(shù)學(xué)的一個主要分支廣泛應(yīng)用背景的基礎(chǔ)研究與計(jì)算機(jī)科學(xué)密切相關(guān)離散數(shù)學(xué)圖論是離散數(shù)學(xué)的一個主要分支離散數(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)波長分配問題

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

給圖的每個點(diǎn)著色，有邊相連的點(diǎn)須著不同的顏色。所用顏色盡可能少。波長分配問題轉(zhuǎn)化為圖論問題每條信道看作圖的一個點(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ù)庫技術(shù)：數(shù)據(jù)的存儲、檢索理論計(jì)算機(jī)科學(xué)：

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

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

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

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

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

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

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

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

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

定理(1907年):n點(diǎn)圖的邊數(shù)大于n2/4時,該圖含三角形,且n2/4是具有該性質(zhì)的最小數(shù).上述定理是Turan定理(1941年)的特殊情形.極值圖論一般敘述:圖的邊數(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ù)時,n個點(diǎn)的平衡完全二部圖不含三角形,且邊數(shù)恰為n2/4.因此,n2/4是具有該性質(zhì)的最小數(shù).極值圖論Mantel定理的證明:設(shè)G是不含三角形的n點(diǎn)圖,其最大點(diǎn)201852年,Morgan教授的一位學(xué)生問他:能否給出一個理由,為什么只需4

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

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

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

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

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

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

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

個邊不交的圈覆蓋。定理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

弱3-流猜想：存在常數(shù)t，使得每個t-邊連通圖有3-流。此猜想與有限域向量空間堆壘基（AdditiveBasis）猜想有關(guān)聯(lián)，吸引了眾多國際一流學(xué)者。定理(Thomassen，2012):每個8-邊連通圖有3-流。(隨后被改進(jìn)到：6-邊連通圖有3-流。)弱3-流猜想弱3-流猜想：存在常數(shù)t，使得每個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個人繞跑道以各自固有的速度跑步。他們在同一時間、同一起點(diǎn)起跑。是否存在某一時刻，某個跑步者“遠(yuǎn)離”其余跑步者？孤獨(dú)的跑步者n個人繞跑道以各自固有的速度跑步。他們數(shù)學(xué)定量描述

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

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

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

n-1

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

。

1

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

圈2

個單位，…,k圈k

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

,對每個i,tai

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

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

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

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

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

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

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

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

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

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

Space~90mmMinimumICfeaturesize=0.18mm90mm0.18mm=500Crosssectionofhumanhair頭發(fā)對最小特征尺寸為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é)

國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃973項(xiàng)目：數(shù)學(xué)與其它領(lǐng)域交叉的若干專題國家重點(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é)

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

研究大規(guī)模集成電路設(shè)計(jì)中的電路劃分、布圖、布線等問題。以圖論、組合優(yōu)化、算法設(shè)計(jì)為主，為研制具有自主知識產(chǎn)權(quán)的大規(guī)模集成電路設(shè)計(jì)應(yīng)用軟件提供理論支持，提高我國在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ì)三個主要部分：電路劃分、布圖、布線涉及大量圖論問題芯片版圖設(shè)計(jì)三個主要部分：芯片版圖設(shè)計(jì)66大規(guī)模集成電路設(shè)計(jì)的關(guān)鍵一步，其結(jié)果會影響后續(xù)的布局、布線等過程。由于需要布局的電路太大，且輸入輸出引腳數(shù)目受到芯片封裝工藝的限制，需要將整個電路劃分成若干模塊，要考慮模塊的大小、模塊間的連線等。電路劃分大規(guī)模集成電路設(shè)計(jì)的關(guān)鍵一步，其結(jié)果會影響后續(xù)的布

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

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

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

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

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

aijbπ(i)π(j)

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

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

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

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

S中的點(diǎn)對應(yīng)模塊，通過添加斯坦納點(diǎn)構(gòu)造斯坦納樹，減小連線總長度?？傮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é)問題對應(yīng)每個通道布線可構(gòu)造兩個圖。水平約束圖（horizontalconstraintgraph）：

頂點(diǎn)集

V={vi

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

邊集

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

5

2

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

設(shè)e=vivj

是水平約束圖（HCG)中的一條邊,那么線網(wǎng)Ni與Nj不能使用同一個線槽，至少需要兩個線槽來完成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)不能使用同一個線槽。如果存在有向圈則不可布。

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

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

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

給定圖G及G中一組路P

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

:

e∈Pi,1≤i≤k}|

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