離散數(shù)學(xué)及其應(yīng)用教育部重點(diǎn)實(shí)驗(yàn)室圖論及其應(yīng)用

1、范 更 華福州大學(xué)離散數(shù)學(xué)研究中心離散數(shù)學(xué)及其應(yīng)用教育部重點(diǎn)實(shí)驗(yàn)室圖論及其應(yīng)用 圖是由給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形?，F(xiàn)實(shí)世界中許多問題的數(shù)學(xué)抽象形式可以用圖來描述。如互聯(lián)網(wǎng)、交通網(wǎng)、通訊網(wǎng)、社團(tuán)網(wǎng)、大規(guī)模集成電路、分子結(jié)構(gòu)等都可以用圖來描述。對(duì)圖的研究形成了一個(gè)專門的數(shù)學(xué)分支圖論 。圖論(Graph Theory)圖的直觀定義：點(diǎn)與邊圖的抽象定義：一個(gè)集合上的二元關(guān)系圖的定義Petersen 圖點(diǎn)集：5個(gè)元素a,b,c,d,e的所有2-子集作為點(diǎn)邊集：兩點(diǎn)有邊相連當(dāng)且僅當(dāng)對(duì)應(yīng)的2-子集不交 abcdeabcdeaccebebdad離散數(shù)學(xué) 圖論是離散數(shù)學(xué)的一個(gè)主要分支廣泛應(yīng)用背景的基礎(chǔ)研

2、究與計(jì)算機(jī)科學(xué)密切相關(guān)離散數(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ā)展。圖 論結(jié)構(gòu)圖論隨機(jī)圖論代數(shù)圖論拓?fù)鋱D論圖論分支極值圖論圖論的起源哥尼斯堡七橋問題哥尼斯堡七橋問題1735年, 歐拉(Euler)證明哥尼斯堡七橋問題無解, 由此開創(chuàng)了數(shù)學(xué)的一個(gè)新分支-圖論。歐拉將哥尼斯堡七橋問題轉(zhuǎn)化為圖論問題: 求圖中一條跡(walk), 過每條邊一次且僅一次. 后人將具有這種性質(zhì)的跡稱為歐拉跡。哥尼斯堡七橋問題哥尼斯堡七橋問題歐拉定理: 連通圖存在歐拉跡當(dāng)且僅當(dāng)圖中奇度數(shù)的點(diǎn)的個(gè)數(shù)至多為2。1852年, Morgan教授的

3、一位學(xué)生問他: 能否給出一個(gè)理由,為什么只需 4 種顏色，就可給任意地圖的每個(gè)國(guó)家著色，使得有共同邊界的國(guó)家著不同的顏色。該問題成為數(shù)學(xué)史上最著名問題之一。將地圖看作一個(gè)平面圖：國(guó)界為邊，相交處為點(diǎn)，國(guó)家區(qū)域稱為面，則該問題可表述為：圖論的發(fā)展四色問題四色問題: 對(duì)每個(gè)平面圖，能否只用4種顏色對(duì)其面著色,使得任何兩個(gè)有公共邊的面得到不同顏色.1976年,兩位計(jì)算機(jī)專家借助計(jì)算機(jī)驗(yàn)證,解決了四色問題，但未被數(shù)學(xué)界普遍接受。數(shù)學(xué)家們?nèi)栽谂ふ壹償?shù)學(xué)的推理證明。四色問題當(dāng)年,那位學(xué)生告訴Morgan教授: 下面的例子說明3種顏色不夠,至少需4種顏色.四色問題一百多年來，貌似容易的四色問題讓許多一流

4、數(shù)學(xué)家栽了跟頭。后人評(píng)說德國(guó)大數(shù)學(xué)家Minkowski （曾是愛因斯坦的老師）時(shí)認(rèn)為，最讓Minkowski尷尬的不是他曾罵愛因斯坦 “懶蟲”，而是他被四色問題掛了黑板。1880年前后，Kempe 和Tait分別發(fā)表了證明四色問題的論文，大家都認(rèn)為四色問題從此也就解決了。十年后，人們發(fā)現(xiàn)這兩人的證明都是錯(cuò)誤的。 四色問題 Tait的錯(cuò)誤在于他認(rèn)為3-正則，3-連通的平面圖有一個(gè)圈包含所有點(diǎn)（哈密頓圈）。 可是他沒能證明這一點(diǎn)。半個(gè)多世紀(jì)后(1946年)，Tutte給出了第一個(gè)不含哈密頓圈的3-正則，3-連通平面圖，從而宣告了Tait證明的錯(cuò)誤是無法修補(bǔ)的。四色問題 圖論的經(jīng)典哈密頓圈問題Tai

5、t 對(duì)四色問題的錯(cuò)誤證明在于假定3-正則，3-連通平面圖有哈密頓圈（含所有點(diǎn)的圈）。哈密爾頓圈問題: 哪些圖有哈密頓圈？ 帶權(quán)哈密爾頓圈 哈密頓圈可看成過每個(gè)點(diǎn)恰好一次的回路；若每條邊有一個(gè)權(quán)(weight),求最優(yōu)哈密頓圈（總權(quán)和最小的哈密頓圈），就是找一條回路：過每個(gè)點(diǎn)恰好一次且行程最短旅行推銷員問題。 旅行推銷員問題問題提出: 一個(gè)推銷員從公司出發(fā), 訪問 若干指定城市, 最后返回公司,要求設(shè)計(jì)最優(yōu)旅行路線(行程最短或費(fèi)用最小) 數(shù)學(xué)抽象: 城市作為點(diǎn), 兩點(diǎn)間有邊相連, 如果對(duì)應(yīng)的城市間有直飛航班。里程或機(jī)票價(jià)作為每條邊的權(quán)。 問題: 在帶權(quán)圖中找一條回路：過每個(gè)點(diǎn)恰好一次,且邊的權(quán)之

6、和最小(帶權(quán)最優(yōu)哈密頓圈）難度: NP-完全問題應(yīng)用: 投幣電話、自動(dòng)取鈔機(jī)等旅行推銷員問題中國(guó)郵遞員問題: 在帶權(quán)圖中找一條回路：過每條邊至少一次,且邊的權(quán)之和最小(帶權(quán)最優(yōu)歐拉回路問題)難度: 有多項(xiàng)式算法(Edmonds, 1985 von NeumannPrize)應(yīng)用: 起源于中國(guó)郵遞（管梅谷，1962）中國(guó)郵遞員問題簡(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)兩兩不連。圖論的經(jīng)典Ramsey數(shù)問題一般化: 定義R(s,t)為最小整數(shù)使得任意R(s,t)個(gè)人中, 要么有 s 個(gè)

7、人兩兩認(rèn)識(shí), 要么有 t 個(gè)人兩兩不認(rèn)識(shí)。R(3,3)=6 R(4,4)=18 R(5,5)=?Ramsey問題 應(yīng)用廣、影響大。微軟研究中心的 Kim 因求解R(3, t)的工作而獲1997年 Fulkerson 獎(jiǎng)。 Ramsey數(shù)問題一般敘述: 圖的邊數(shù)大于某個(gè)數(shù)時(shí),該圖具有某種性質(zhì),此數(shù)的最小值稱為該性質(zhì)的極值.Mantel 定理(1907年): n點(diǎn)圖的邊數(shù)大于n2/4時(shí),該圖含三角形,且n2/4是具有該性質(zhì)的最小數(shù). 上述定理是Turan定理(1941年)的特殊情形.主要工具：正則引理；標(biāo)號(hào)代數(shù)(flag algebra)圖論的熱點(diǎn)極值問題圖論的前沿整數(shù)流問題 給定圖G 和k 階可

8、換群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ù)流問題整數(shù)流問題：對(duì)哪些整數(shù)k，存在k-流k-流的等價(jià)定義：給圖的每條邊一個(gè)定向及一個(gè)絕對(duì)值小于k的非零整數(shù), 使得在圖的每個(gè)點(diǎn), 進(jìn)入該點(diǎn)的所有邊的整數(shù)值之和等于離開該點(diǎn)的所有邊的整數(shù)值之和。整數(shù)流的一個(gè)例子 Tutte定理(1954年): 平面圖可 k 著色當(dāng)且僅當(dāng)該圖存在 k-流。 四色問題等價(jià)于平面圖的 4-流存在性。 整數(shù)流理論 整數(shù)流與數(shù)學(xué)其他領(lǐng)域的一些著名問題有關(guān)聯(lián): 組合學(xué): Lonely

9、 Runner 數(shù)論: Diophantine Approximation 幾何學(xué): View Obstruction 有限域線性空間: Additive Basis 整數(shù)流理論5-流猜想: 每個(gè)2-邊連通圖有 5-流。4-流猜想: 每個(gè)不含Petersen廣義子圖的2-邊連通圖有 4-流。3-流猜想: 每個(gè)4-邊連通圖有 3-流。Tutte整數(shù)流三大猜想 W.T. Tutte (1917-2002) W.T. Tutte (1917-2002) 英國(guó)皇家學(xué)會(huì)會(huì)員 創(chuàng)建滑鐵盧大學(xué)組合與優(yōu)化系 圖論與擬陣論兩大領(lǐng)域奠基性工作 二次世界大戰(zhàn)偉大無名英雄(Great unsung hero of W

10、orld War II) W.T. Tutte (1917-2002)Tutte的戰(zhàn)友Jerry Roberts(破譯小組最后一名成員)2014年3月25日去世，英國(guó)每日郵報(bào)報(bào)道的標(biāo)題是英國(guó)傳奇譯碼專家去世 曾助二戰(zhàn)提前兩年結(jié)束，文中寫道：由于Tutte成功破解了“金槍魚”系統(tǒng)的邏輯原理，他的團(tuán)隊(duì)得以破譯德軍最高級(jí)別的密碼“金槍魚”。 Paul Erdos (1913-1996) Paul Erdos (1913-1996) 美國(guó)、英國(guó)等8個(gè)國(guó)家科學(xué)院院士 沃爾夫獎(jiǎng)(Wolf Prizes,1983/4)頒獎(jiǎng)詞: , and for personally stimulating mathema

11、ticians the world over. 將榮譽(yù)博士學(xué)位退還滑鐵盧大學(xué) Paul Erdos (1913-1996)圖論(Graph Theory)圖論的起源：哥尼斯堡七橋問題圖論的發(fā)展：四色問題圖論的經(jīng)典：哈密頓圈， Ramsey數(shù)問題圖論的熱點(diǎn)：極值問題圖論的前沿：整數(shù)流問題圖論的應(yīng)用：大規(guī)模集成電路設(shè)計(jì)問題大規(guī)模集成電路（VLSI） Very Large Scale Integration 用半導(dǎo)體工藝技術(shù)將電子電路的電子元器件（電阻、電容、電感、晶體管、二極管、傳感器等）在一塊半導(dǎo)體材料（硅、砷化鎵）芯片上，互連成有獨(dú)立功能的電路和系統(tǒng)。亦稱為“芯片”（Chip）。 集成電路產(chǎn)業(yè)

12、包括設(shè)計(jì)、芯片制造、封裝檢測(cè)三大部分。可形象地比喻為寫書、印刷、裝訂。顯然，設(shè)計(jì)最具原創(chuàng)性。“863”、“973”，及國(guó)家重大專項(xiàng)都把集成電路設(shè)計(jì)列入其中。 集成電路設(shè)計(jì)所依賴的關(guān)鍵軟件EDA (Electronic Design Automation), 基本上全是進(jìn)口。 (EDA軟件的研制涉及大量的圖論和組合優(yōu)化問題.)集成電路產(chǎn)業(yè)硅園片上的芯片硅襯底drain硅襯底頂部保護(hù)層金屬層絕緣層凹進(jìn)導(dǎo)電層導(dǎo)電層1961年早期芯片 4個(gè)晶體管和若干電阻 1990年Intel奔騰處理器芯片1.5cm2310萬晶體管奔芯片結(jié)構(gòu)圖 2000年，0.18 m工藝，4千2百萬個(gè)晶體管頭發(fā)對(duì)最小特征尺寸為0.

13、18m的比較Contact holeLine width Space90 mmMinimum IC feature size = 0.18 m (180nm)90 mm0.18 mm= 500Cross section of human hair芯片中金屬層（介質(zhì)腐蝕后呈立交橋狀）Metal Layers in a Chip電路劃分布局布線原理圖輸入芯片制造版圖驗(yàn)證數(shù)據(jù)導(dǎo)出芯片版圖設(shè)計(jì)三個(gè)主要部分：電路劃分、布圖、布線涉及大量圖論問題芯片版圖設(shè)計(jì) 是大規(guī)模集成電路設(shè)計(jì)的關(guān)鍵一步，其結(jié)果會(huì)影響后續(xù)的布局、布線等過程。由于需要布局的電路太大，需要將整個(gè)電路劃分成若干模塊，要考慮模塊的大小、模塊間的

14、連線等。電路劃分 是一個(gè)多約束、多目標(biāo)的優(yōu)化問題。它的理論抽象是圖論中的點(diǎn)集劃分（Vertex Partition）問題: 給定一個(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，且ij w(Ai, Aj) 盡可能小。電路劃分 在完成電路劃分之后，通過布局規(guī)劃（floorplanning）把模塊安置在芯片的適當(dāng)位置上，并滿足一定的要求，如面積最小、模塊間的連線最短且容易布通等。由于模塊間連線要占用芯片面積，布局時(shí)要為后一步的布線留下必要的布線通道。布 局 模塊間的互連，且滿足一定的要求，如減小

15、連線總長(zhǎng)度，減輕走線擁擠度，減少層間通孔數(shù)等。布線分為總體布線和詳細(xì)布線。布 線最小斯坦納樹(Minimum Steiner Tree)問題： 給定一個(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)度。總體布線中的數(shù)學(xué)問題總體布線中的數(shù)學(xué)問題總體布線中的數(shù)學(xué)問題詳細(xì)布線中的數(shù)學(xué)問題 在完成總體布線后，進(jìn)行詳細(xì)布線?？赊D(zhuǎn)化為在圖中找一組路連接指定點(diǎn)集且滿足若干條件，如要求每條邊不能被太多路共同使用。圖的邊對(duì)應(yīng)于布線通道，也即要求該通道不能太擁擠。 詳細(xì)布線的一個(gè)主要問題就是用圖的某些參數(shù)給出通道寬度

16、（線槽數(shù)）的估計(jì)。973項(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)目：信息及相關(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ì)劃 研究大規(guī)模集成電路設(shè)計(jì)中的電路劃分、布圖、布線等問題。以圖論、組合優(yōu)化、算法設(shè)計(jì)為主，為研制具有自主知識(shí)產(chǎn)權(quán)的大規(guī)模集成電路設(shè)計(jì)應(yīng)用軟件提供理論支持，提高我國(guó)在 EDA（Electronic Design Automation）工具研制這一領(lǐng)域的基礎(chǔ)理論研究水平。973課題概述德國(guó)波恩(Bonn)大學(xué)離散數(shù)學(xué)研究所Re