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

2、究與計算機科學密切相關離散數學 以蒸汽機的出現為標志的工業革命促進了以微積分為基礎的連續數學的發展。 以計算機的出現為標志的信息革命將促進離散數學的發展。圖 論結構圖論隨機圖論代數圖論拓撲圖論圖論分支極值圖論圖論的起源哥尼斯堡七橋問題哥尼斯堡七橋問題1735年, 歐拉(Euler)證明哥尼斯堡七橋問題無解, 由此開創了數學的一個新分支-圖論。歐拉將哥尼斯堡七橋問題轉化為圖論問題: 求圖中一條跡(walk), 過每條邊一次且僅一次. 后人將具有這種性質的跡稱為歐拉跡。哥尼斯堡七橋問題哥尼斯堡七橋問題歐拉定理: 連通圖存在歐拉跡當且僅當圖中奇度數的點的個數至多為2。1852年, Morgan教授的

3、一位學生問他: 能否給出一個理由,為什么只需 4 種顏色，就可給任意地圖的每個國家著色，使得有共同邊界的國家著不同的顏色。該問題成為數學史上最著名問題之一。將地圖看作一個平面圖：國界為邊，相交處為點，國家區域稱為面，則該問題可表述為：圖論的發展四色問題四色問題: 對每個平面圖，能否只用4種顏色對其面著色,使得任何兩個有公共邊的面得到不同顏色.1976年,兩位計算機專家借助計算機驗證,解決了四色問題，但未被數學界普遍接受。數學家們仍在努力尋找純數學的推理證明。四色問題當年,那位學生告訴Morgan教授: 下面的例子說明3種顏色不夠,至少需4種顏色.四色問題一百多年來，貌似容易的四色問題讓許多一流

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

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

6、和最小(帶權最優哈密頓圈）難度: NP-完全問題應用: 投幣電話、自動取鈔機等旅行推銷員問題中國郵遞員問題: 在帶權圖中找一條回路：過每條邊至少一次,且邊的權之和最小(帶權最優歐拉回路問題)難度: 有多項式算法(Edmonds, 1985 von NeumannPrize)應用: 起源于中國郵遞（管梅谷，1962）中國郵遞員問題簡單情形: 任意六個人中, 必有3個互相認識, 或三個互相不認識。數學抽象: 點代表人, 兩點相連當且僅當對應的兩人認識。該圖要么有三角形,要么有三個點兩兩不連。圖論的經典Ramsey數問題一般化: 定義R(s,t)為最小整數使得任意R(s,t)個人中, 要么有 s 個

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

8、換群A。若對G 的某個定向, 存在一個函數f : 從G 的邊集到A的非零元素, 使得在圖的每個一點, 進入該點的邊的函數值之和等于離開該點的邊函數值之和, 則稱f 為G 的一個 k-流。 整數流問題整數流問題：對哪些整數k，存在k-流k-流的等價定義：給圖的每條邊一個定向及一個絕對值小于k的非零整數, 使得在圖的每個點, 進入該點的所有邊的整數值之和等于離開該點的所有邊的整數值之和。整數流的一個例子 Tutte定理(1954年): 平面圖可 k 著色當且僅當該圖存在 k-流。 四色問題等價于平面圖的 4-流存在性。 整數流理論 整數流與數學其他領域的一些著名問題有關聯: 組合學: Lonely

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

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

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

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

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

14、連線等。電路劃分 是一個多約束、多目標的優化問題。它的理論抽象是圖論中的點集劃分（Vertex Partition）問題: 給定一個圖G 及邊集E(G)上的一個權函數w. 對正整數 k t，求點集V(G)的一個劃分(A1, A2, ., Am) 使得 k |Ai| t，1 i m，且ij w(Ai, Aj) 盡可能小。電路劃分 在完成電路劃分之后，通過布局規劃（floorplanning）把模塊安置在芯片的適當位置上，并滿足一定的要求，如面積最小、模塊間的連線最短且容易布通等。由于模塊間連線要占用芯片面積，布局時要為后一步的布線留下必要的布線通道。布 局 模塊間的互連，且滿足一定的要求，如減小

15、連線總長度，減輕走線擁擠度，減少層間通孔數等。布線分為總體布線和詳細布線。布 線最小斯坦納樹(Minimum Steiner Tree)問題： 給定一個賦權圖G 及點集 V(G)的一個子集S，求G 中一個連結S 的所有點的最小權樹。 S 中的點對應模塊，通過添加斯坦納點構造斯坦納樹，減小連線總長度。總體布線中的數學問題總體布線中的數學問題總體布線中的數學問題詳細布線中的數學問題 在完成總體布線后，進行詳細布線。可轉化為在圖中找一組路連接指定點集且滿足若干條件，如要求每條邊不能被太多路共同使用。圖的邊對應于布線通道，也即要求該通道不能太擁擠。 詳細布線的一個主要問題就是用圖的某些參數給出通道寬度

16、（線槽數）的估計。973項目：數學與其它領域交叉的若干專題 （2006.6-2010.12)課題 ：大規模集成電路設計中的圖論與代數方法負責人：范 更 華承擔單位：福州大學參加單位：北京大學、南開大學、山東大學國家重點基礎研究發展計劃新一輪973項目：信息及相關領域若干重大需求的應用數學研究（2011.1-2015.12)課題 ：大規模集成電路物理設計中 關鍵應用數學理論和方法負責人：范 更 華承擔單位：福州大學參加單位：北大、南開、山東大學、四川大學 國家重點基礎研究發展計劃 研究大規模集成電路設計中的電路劃分、布圖、布線等問題。以圖論、組合優化、算法設計為主，為研制具有自主知識產權的大規模集成電路設計應用軟件提供理論支持，提高我國在 EDA（Electronic Design Automation）工具研制這一領域的基礎理論研究水平。973課題概述德國波恩(Bonn)大學離散數學研究所Re