圖論GraphTheory-數(shù)學(xué)研究所課件

1、范 更 華福州大學(xué)離散數(shù)學(xué)研究中心離散數(shù)學(xué)及其應(yīng)用教育部重點(diǎn)實(shí)驗(yàn)室圖論及其應(yīng)用 圖論研究的對(duì)象是圖，它由點(diǎn)及連接兩點(diǎn)的線所構(gòu)成?，F(xiàn)實(shí)世界中許多問(wèn)題的數(shù)學(xué)抽象形式可以用圖來(lái)描述。如互聯(lián)網(wǎng)、交通網(wǎng)、通訊網(wǎng)、社團(tuán)網(wǎng)、大規(guī)模集成電路、分子結(jié)構(gòu)等都可以用圖來(lái)描述。對(duì)圖的研究形成了一個(gè)專門(mén)的數(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é)的一個(gè)主要分支。普林斯頓數(shù)學(xué)系自

2、2008年起，一直有每周一次的離散數(shù)學(xué)seminar，邀請(qǐng)世界各地的數(shù)學(xué)家作報(bào)告，主要側(cè)重圖論。中科院系統(tǒng)所曾引領(lǐng)中國(guó)圖論的發(fā)展。離散數(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論圖論分支極值圖論 我們將通過(guò)圖論發(fā)展歷程中的若干好問(wèn)題/猜想，來(lái)了解這一學(xué)科的歷史與現(xiàn)狀。好的數(shù)學(xué)問(wèn)題/猜想 簡(jiǎn)潔：簡(jiǎn)短而易理解的陳述出乎預(yù)料：似乎完全不同的概念融于一體一般性：適用性廣，涵蓋面寬核心性：與已知的著名定理和猜想有關(guān)聯(lián)經(jīng)久性：久而未決（至少20年）影響力：解決該問(wèn)題的嘗試產(chǎn)生新概念，新

3、證明技巧圖論的起源哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題1735年, 歐拉(Euler)證明哥尼斯堡七橋問(wèn)題無(wú)解, 由此開(kāi)創(chuàng)了數(shù)學(xué)的一個(gè)新分支-圖論.歐拉將七橋問(wèn)題轉(zhuǎn)化為圖論問(wèn)題: 求圖中一條跡(walk), 過(guò)每條邊一次且僅一次（這種性質(zhì)的跡稱為歐拉跡）。歐拉定理: 連通圖存在歐拉跡當(dāng)且僅當(dāng)圖中奇度數(shù)的點(diǎn)的個(gè)數(shù)至多為2。哥尼斯堡七橋問(wèn)題閉的歐拉跡也稱為歐拉回路。歐拉定理 (圖論最古老的定理, 1735年)：無(wú)奇度數(shù)點(diǎn)的連通圖存在歐拉回路且可分解成邊不交的圈。需要多少個(gè)圈？二百多年來(lái)，這個(gè)問(wèn)題一直未能解決。 歐拉定理Hajos猜想：n個(gè)點(diǎn)的歐拉圖可分解成至多n/2個(gè)圈（歐拉圖：無(wú)奇度數(shù)點(diǎn)的連通圖）E

4、rdos-Goodman-Posa 猜想 (1966): 存在常數(shù)c, n個(gè)點(diǎn)的歐拉圖可分解成cn 個(gè)圈。Pyber認(rèn)為此猜想的解決在目前是不可及的“out of reach at present”。圈分解猜想Gallai猜想：n個(gè)點(diǎn)的連通圖可分解成至多(n+1)/2條路。Lovasz定理：n個(gè)點(diǎn)的連通圖可分解成至多n/2條路和圈。Lovasz： 長(zhǎng)期從事圖論研究，51歲獲 Wolf獎(jiǎng)，曾任國(guó)際數(shù)學(xué)聯(lián)盟主席，多個(gè)國(guó)家的科學(xué)院院士，曾在微軟研究中心任職多年，現(xiàn)為匈牙利科學(xué)院院長(zhǎng)。路分解猜想1852年, Morgan教授的一位學(xué)生問(wèn)他: 能否給出一個(gè)理由,為什么只需 4 種顏色，就可給任意地圖的每

5、個(gè)國(guó)家著色，使得有共同邊界的國(guó)家著不同的顏色。該問(wèn)題成為數(shù)學(xué)史上最著名問(wèn)題之一。將地圖看作一個(gè)平面圖：國(guó)界為邊，相交處為點(diǎn)，國(guó)家區(qū)域稱為面，則該問(wèn)題可表述為：圖論的發(fā)展四色問(wèn)題四色問(wèn)題: 對(duì)每個(gè)平面圖，只用4種顏色對(duì)其面著色,使得任何兩個(gè)有公共邊的面得到不同顏色。Whitney（Wolf 獎(jiǎng)得主，微分拓?fù)鋵W(xué)奠基人）和Tutte（英國(guó)皇家學(xué)會(huì)會(huì)員）在四色問(wèn)題的研究上有過(guò)合作。 1976年,兩位計(jì)算機(jī)專家借助計(jì)算機(jī)驗(yàn)證,解決了四色問(wèn)題。數(shù)學(xué)家們?nèi)栽谂ふ壹兺评碜C明。四色問(wèn)題當(dāng)年,那位學(xué)生告訴Morgan教授: 下面的例子說(shuō)明3種顏色不夠,至少需4種顏色.四色問(wèn)題一百多年來(lái)，貌似容易的四色問(wèn)題讓許

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

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

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

9、認(rèn)識(shí), 要么有 t 個(gè)人兩兩不認(rèn)識(shí)。R(3,3)=6 R(4,4)=18 R(5,5)=?Ramsey問(wèn)題 應(yīng)用廣、影響大。微軟研究中心的Kim因求解R(3, t)的工作而獲1997年 Fulkerson獎(jiǎng)。 Ramsey數(shù)問(wèn)題一般敘述: 圖的邊數(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)極值問(wèn)題圖論的前沿整數(shù)流問(wèn)題 給定圖G 和k 階可換群A。若對(duì)

10、G 的某個(gè)定向, 存在一個(gè)函數(shù)f : 從G 的邊集到A的非零元素, 使得在圖的每個(gè)一點(diǎn), 進(jìn)入該點(diǎn)的邊的函數(shù)值之和等于離開(kāi)該點(diǎn)的邊函數(shù)值之和, 則稱f 為G 的一個(gè) k-流。 整數(shù)流問(wèn)題整數(shù)流問(wèn)題：對(duì)哪些整數(shù)k，存在k-流k-流的等價(jià)定義：給圖的每條邊一個(gè)定向及一個(gè)絕對(duì)值小于k 的非零整數(shù), 使得在圖的每個(gè)點(diǎn), 進(jìn)入該點(diǎn)的所有邊的整數(shù)值之和等于離開(kāi)該點(diǎn)的所有邊的整數(shù)值之和。整數(shù)流的一個(gè)例子 Tutte定理(1954年): 平面圖可 k 著色當(dāng)且僅當(dāng)該圖存在 k-流。 四色問(wèn)題等價(jià)于平面圖的 4-流存在性。 整數(shù)流理論 整數(shù)流與數(shù)學(xué)其他領(lǐng)域的一些著名問(wèn)題有關(guān)聯(lián): 組合學(xué): Lonely Runn

11、er 數(shù)論: Diophantine Approximation 幾何學(xué): View Obstruction 有限域線性空間: Additive Basis 整數(shù)流理論孤獨(dú)的跑步者 n 個(gè)人繞跑道以各自固有的速度跑步。他們?cè)谕粫r(shí)間、同一起點(diǎn)起跑。是否存在某一時(shí)刻，某個(gè)跑步者 “遠(yuǎn)離” 其余跑步者？數(shù)學(xué)定量描述 設(shè)跑道一圈的長(zhǎng)度為 1 個(gè)單位。是否存在某個(gè)時(shí)刻、某跑步者與所有其余跑步者的距離至少是 1/n 單位。 n-1 個(gè)人繞單位長(zhǎng)度跑道以各自固有的速度從同一起點(diǎn)起跑。是否存在某個(gè)時(shí)刻，所有跑步者與起點(diǎn)的距離至少是 1 / n ？數(shù)學(xué)定量描述 k 個(gè)跑步者的速度分別為q1, q2, , qk

12、。 1 圈跑道相當(dāng)于數(shù)軸上的一個(gè)單位， 2 圈2 個(gè)單位， , k 圈k 個(gè)單位 。這樣，每個(gè)正整數(shù)均相當(dāng)于跑道起點(diǎn)。是否存在時(shí)間t , 對(duì)每個(gè) i, tqi 與最近整數(shù)的距離至少是1/ k ?數(shù)學(xué)定量描述 數(shù)論難題（丟番圖逼近） 若取速度為正整數(shù)q, 與tq最近的整數(shù)記為p,則tq與p的距離是|tq-p|=q|t-p/q|。對(duì)|t-p/q| 的估計(jì)是數(shù)論中經(jīng)典的對(duì)實(shí)數(shù)的有理逼近。t: 實(shí)數(shù)；p/q: 有理數(shù)觀察者問(wèn)題 (View Obstruction)5-流猜想: 每個(gè)2-邊連通圖有 5-流。4-流猜想: 每個(gè)不含Petersen廣義子圖的2-邊連通圖有 4-流。3-流猜想: 每個(gè)4-邊連

13、通圖有 3-流。Tutte整數(shù)流三大猜想Seymour 6-流定理: 每個(gè)2-邊連通圖有6-流。Seymour: 普林斯頓數(shù)學(xué)系教授，1994年世界數(shù)學(xué)家大會(huì)小時(shí)報(bào)告。 Thomassen（丹麥科學(xué)院院士）解決了弱 3-流猜想，證明: 每個(gè)8-邊連通圖有3-流；已被改進(jìn)到：每個(gè)6-邊連通圖有3-流。整數(shù)流三大猜想進(jìn)展定義：若一個(gè)圖的邊集可表為某些子圖的邊集之和，則稱該圖是這些子圖之和。 子圖和問(wèn)題：將一個(gè)圖表為盡可能少的子圖之和。偶圖：每個(gè)點(diǎn)與偶數(shù)條邊關(guān)聯(lián)。 圖論的前沿子圖和問(wèn)題偶圖和是下面兩個(gè)偶圖之和四色問(wèn)題的一個(gè)等價(jià)形式: 每個(gè)2-邊連通平面圖是兩個(gè)偶圖之和。 哥德巴赫猜想: 每個(gè)大于2的

14、偶數(shù)是兩個(gè)素?cái)?shù)之和。 偶圖和數(shù)論: 每個(gè)充分大的奇數(shù)是3個(gè)素?cái)?shù)之和。圖論: 每個(gè)2-邊連通圖是3個(gè)偶圖之和。陳景潤(rùn)定理: 每個(gè)充分大的偶數(shù)是一個(gè)素?cái)?shù)與不超過(guò)兩個(gè)素?cái)?shù)的乘積之和。Seymour定理: 每個(gè)2-邊連通圖是一個(gè)偶圖與不超過(guò)兩個(gè)偶圖的有向并之和。 偶圖和vs素?cái)?shù)和 W.T. Tutte (1917-2002) W.T. Tutte (1917-2002) 英國(guó)皇家學(xué)會(huì)會(huì)員 創(chuàng)建滑鐵盧大學(xué)組合與優(yōu)化系 圖論與擬陣論兩大領(lǐng)域奠基性工作 二次世界大戰(zhàn)偉大無(wú)名英雄(Great unsung hero of World War II) W.T. Tutte (1917-2002)Tutte的戰(zhàn)友

15、Jerry Roberts(破譯小組最后一名成員)2014年3月25日去世，英國(guó)每日郵報(bào)報(bào)道的標(biāo)題是英國(guó)傳奇譯碼專家去世 曾助二戰(zhàn)提前兩年結(jié)束，文中寫(xiě)道：由于Tutte成功破解了“金槍魚(yú)”系統(tǒng)的邏輯原理，他的團(tuán)隊(duì)得以破譯德軍最高級(jí)別的密碼“金槍魚(yú)”。 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 mathematicians the world over. 將榮譽(yù)博士學(xué)位退還滑鐵盧大學(xué) Paul

16、 Erdos (1913-1996)圖論(Graph Theory)圖論的起源：哥尼斯堡七橋，歐拉定理圖論的發(fā)展：四色問(wèn)題圖論的經(jīng)典：哈密頓圈， Ramsey數(shù)圖論的熱點(diǎn)：極值問(wè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è)包括設(shè)計(jì)、芯片制造、封裝檢測(cè)三大部分?？尚蜗蟮乇扔鳛閷?xiě)書(shū)、印刷、裝訂。顯然，設(shè)計(jì)最具

17、原創(chuàng)性。“863”、“973”，及國(guó)家重大專項(xiàng)都把集成電路設(shè)計(jì)列入其中。 集成電路設(shè)計(jì)所依賴的關(guān)鍵軟件EDA (Electronic Design Automation), 基本上全是進(jìn)口。 (EDA軟件的研制涉及大量的圖論和組合優(yōu)化問(wèn)題)。集成電路產(chǎn)業(yè) 國(guó)家中長(zhǎng)期科學(xué)和技術(shù)發(fā)展規(guī)劃綱要確定了16個(gè)重大專項(xiàng)作為我國(guó)科技發(fā)展的重中之重。其中與集成電路有關(guān)的占了兩項(xiàng): 核心電子器件、高端通用芯片及基礎(chǔ)軟件 極大規(guī)模集成電路制造技術(shù)及成套工藝我國(guó)集成電路產(chǎn)業(yè)發(fā)展前景硅園片上的芯片硅襯底drain硅襯底頂部保護(hù)層金屬層絕緣層凹進(jìn)導(dǎo)電層導(dǎo)電層1961年早期芯片 4個(gè)晶體管和若干電阻 1990年Intel

18、奔騰處理器芯片1.5cm2310萬(wàn)晶體管奔芯片結(jié)構(gòu)圖 2000年，0.18 m工藝，4千2百萬(wàn)個(gè)晶體管頭發(fā)對(duì)最小特征尺寸為0.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è)主要部分：電路劃分、布圖、布線涉及大量圖論問(wèn)題芯片版圖設(shè)計(jì) 是大規(guī)模集成電路設(shè)計(jì)的

19、關(guān)鍵一步，其結(jié)果會(huì)影響后續(xù)的布局、布線等過(guò)程。由于需要布局的電路太大，需要將整個(gè)電路劃分成若干模塊，要考慮模塊的大小、模塊間的連線等。電路劃分 是一個(gè)多約束、多目標(biāo)的優(yōu)化問(wèn)題。它的理論抽象是圖論中的點(diǎn)集劃分（Vertex Partition）問(wèn)題: 給定一個(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ò)布局規(guī)劃（floorplanning）把模塊安置在芯片的適當(dāng)位置上，并滿足一定的要求，如面積最小、模塊間的連線最短且容易布通等。布 局 模塊間的互連，且滿足一定的要求，如減小連線總長(zhǎng)度，減輕走線擁擠度，減少層間通孔數(shù)等。布線分為總體布線和詳細(xì)布線。布 線最小斯坦納樹(shù)(Minimum Steiner Tree)問(wèn)題： 給定一個(gè)賦權(quán)圖G 及點(diǎn)集 V(G)的一個(gè)子集S，求G 中一個(gè)連結(jié)S 的所有點(diǎn)的最小權(quán)樹(shù)。 S 中的點(diǎn)對(duì)應(yīng)模塊，通過(guò)添加斯坦納點(diǎn)構(gòu)造斯坦納樹(shù)，減小連線總長(zhǎng)度。總體布線詳細(xì)布線 在完成總體布線后，進(jìn)行詳細(xì)布線?？赊D(zhuǎn)化為在圖中找一組路連接指定點(diǎn)集且滿足若干條件，如要求每條邊不能被太多路共同使用。圖的邊對(duì)應(yīng)于布線通道，也即要求該通道不能太擁擠。97