離散數(shù)學課件

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

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

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

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

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

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

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

交通網(wǎng)

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

計算機處理器連接方式

集成電路板

分子結構圖

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

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

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

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

DNA序列分析：圖的歐拉回路問題具體應用13

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

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

數(shù)學抽象:點代表人,兩點相連當且僅當對應的兩人認識。該圖要么有三角形,要么有三個點兩兩不連。Ramsey數(shù)問題簡單情形:任意六個人中,必有3個互相Ramsey數(shù)問題證明：令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數(shù)問題證明：令G是6個點的圖，x為G中一個點。與xRamsey數(shù)問一般化:定義R(s,t)為最小整數(shù)使得任意R(s,t)個人中,要么有s個人兩兩認識,要么有t個人兩兩不認識。

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

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

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

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

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

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

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

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

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

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

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

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

個邊不交的圈覆蓋。定理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

整數(shù)流與數(shù)學其他領域的一些著名問題有關聯(lián):

組合學:LonelyRunner

數(shù)論:DiophantineApproximation

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

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

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

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

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

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

n-1

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

。

1

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

圈2

個單位，…,k圈k

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

,對每個i,tai

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

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

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

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

對n﹥5,

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

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

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

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

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

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

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

2000年，0.18μm工藝，4千2百萬個晶體管奔Ⅳ芯片結構圖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項目：數(shù)學與其它領域交叉的若干專題（2006.6-2010.12)課題

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

國家重點基礎研究發(fā)展計劃973項目：數(shù)學與其它領域交叉的若干專題國家重點基礎研究發(fā)展62新一輪973項目：信息及相關領域若干重大需求的應用數(shù)學研究（2011.1-2015.12)課題

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

國家重點基礎研究發(fā)展計劃新一輪973項目：信息及相關領域若干重大需求的應用數(shù)學研究（63

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

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

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

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

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

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

aijbπ(i)π(j)

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

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

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

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

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

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

頂點集

V={vi

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

邊集

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

5

2

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

設e=vivj

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

的引腳的連接。

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

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

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

5

2

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

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

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

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

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

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

2007):求MG的弦子圖(chordalsubgraph)的團數(shù)，給出通道寬度下界。詳細布線中的數(shù)學問題因HCG是區(qū)間圖，有多項式算法求它的詳細布線中的數(shù)學問題定理(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詳細布線中的數(shù)學問題定理(FanandLiu,2011詳細布線中的數(shù)學問題定理(FanandLiu,2011):設D是MG上的一個無圈定向。若D包含VCG的定向，則定向D中最長有向路的長度給出通道寬度（線槽數(shù)）的上界；且存在這樣一個定向D*，使得D*中最長有向路的長度給出通道寬度的精確值。比較：MG的團數(shù)只能給出通道寬度的下屆，無法給出精確值。詳細布線中的數(shù)學問題定理(FanandLiu,2011詳細布線中的數(shù)學問題定理(Szeszler,2003):n個線網(wǎng)的通道布線問題，若可解，則通道寬度（線槽數(shù)）至多為7n/4，且可多項式時間完成布線。定理(FanandGeng,2011):n個線網(wǎng)的通道布線問題，若可解，則通道寬度（線槽數(shù)）至多為3n/2，且可多項式時間完成布線。詳細布線中的數(shù)學問題定理(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ù)。詳細布線中的數(shù)學問題路覆蓋(PathCovering)問題：詳細布線中的數(shù)學問90P

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

e∈E(G)}

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

給定n點圖G，是否存在一組路

P

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

e，

1≤P(e)≤m若對k

不加限制，則答案顯然。若對k

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

交通網(wǎng)

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

計算機處理器連接方式

集成電路板

分子結構圖

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

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

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

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

DNA序列分析：圖的歐拉回路問題具體應用112

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

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

數(shù)學抽象:點代表人,兩點相連當且僅當對應的兩人認識。該圖要么有三角形,要么有三個點兩兩不連。Ramsey數(shù)問題簡單情形:任意六個人中,必有3個互相Ramsey數(shù)問題證明：令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數(shù)問題證明：令G是6個點的圖，x為G中一個點。與xRamsey數(shù)問一般化:定義R(s,t)為最小整數(shù)使得任意R(s,t)個人中,要么有s個人兩兩認識,要么有t個人兩兩不認識。

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

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

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

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

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

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

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

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

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

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

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

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

個邊不交的圈覆蓋。定理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

整數(shù)流與數(shù)學其他領域的一些著名問題有關聯(lián):

組合學:LonelyRunner

數(shù)論:DiophantineApproximation

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

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

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

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

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

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

n-1

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

。

1

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

圈2

個單位，…,k圈k

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

,對每個i,tai

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

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

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

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

對n﹥5,

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

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

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

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

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

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

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

2000年，0.18μm工藝，4千2百萬個晶體管奔Ⅳ芯片結構圖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項目：數(shù)學與其它領域交叉的若干專題（2006.6-2010.12)課題

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

國家重點基礎研究發(fā)展計劃973項目：數(shù)學與其它領域交叉的若干專題國家重點基礎研究發(fā)展161新一輪973項目：信息及相關領域若干重大需求的應用數(shù)學研究（2011.1-2015.12)課題

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

國家重點基礎研究發(fā)展計劃新一輪973項目：信息及相關領域若干重大需求的應用數(shù)學研究（162

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

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

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

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

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

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

aijbπ(i)π(j)

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

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

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

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

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

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

頂點集

V={vi

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

邊集

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

5

2

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

設e=vivj

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

的引腳的連接。

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

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

={(vi