第6章特殊的圖

第6章特殊的圖教學(xué)要求了解二部圖的概念了解歐拉圖的概念了解哈密頓圖的概念了解平面圖的概念6.1二部圖（僅討論無向圖）1.二部圖與完全二部圖：P140定義6.1問題：給定一個(gè)圖，判斷它是否是二部圖？定理：P140定理6.12.匹配，極大匹配，最大匹配，完美匹配：P140定義6.23.完備匹配：P140定義6.3判定完備匹配的充要條件：P141定理6.2和定理6.34.二部圖的應(yīng)用：解決分配問題

例1P141例6.1

例2在新學(xué)期開始時(shí)，某大學(xué)的計(jì)算機(jī)系對課程進(jìn)行安排，下表給出了計(jì)算機(jī)系教師能承擔(dān)的課程情況,判定是否所有的課程都能有教師承擔(dān)，并給出一種排課方案教師承擔(dān)的課程趙老師(z)數(shù)據(jù)庫原理(DB1)、大型數(shù)據(jù)庫(DB2)、計(jì)算機(jī)組成原理(O)

錢老師(q)數(shù)據(jù)庫原理(DB1)、大型數(shù)據(jù)庫(DB2)、數(shù)據(jù)結(jié)構(gòu)(D)

孫老師(s)數(shù)據(jù)庫原理(DB1)、大型數(shù)據(jù)庫(DB2)、數(shù)據(jù)結(jié)構(gòu)(D)、Java(J)

李老師(l)Java(J)馮老師(f)數(shù)據(jù)結(jié)構(gòu)(D)、Java(J)6.2歐拉圖(對所有邊的環(huán)游問題）1.歐拉通路、歐拉回路：P142定義6.4

注意：允許某個(gè)頂點(diǎn)通過兩次以上，但每條邊只能經(jīng)過一次問題：無向圖歐拉通路、歐拉回路的判別？無向圖歐拉路的判別：P142定理6.4(歐拉路的充要條件）有向圖歐拉路的判別：P142定理6.52.歐拉圖：存在歐拉回路的圖3.歐拉圖的應(yīng)用acdeb例：設(shè)某城市的街道布局如左圖所示，每條邊代表一條特定街道的一段街區(qū)，每個(gè)結(jié)點(diǎn)代表街區(qū)間的交點(diǎn)。掃雪車車庫位于結(jié)點(diǎn)d，證明存在一條路線使得掃雪車清掃每個(gè)街區(qū)恰好一次且清掃完最后一個(gè)街區(qū)正好返回車庫。同時(shí)為這個(gè)掃雪車找出完成任務(wù)的路線6.3哈密頓圖（對所有點(diǎn)的環(huán)游問題）1.哈密頓通路與回路：P144定義6.5哈密頓圖的判別：世界難題！2.哈密頓圖：存在哈密頓回路的圖3.哈密頓圖的必要條件：P144定理6.66.4平面圖（無向圖）1.平面圖的基本概念舉例：設(shè)有一個(gè)電路有六個(gè)元件，三個(gè)分為一組，連接如（a）圖，是否有這樣的接線法，使得導(dǎo)線互不交叉？平面圖的定義：P146定義6.62平面圖的區(qū)域：P146定義6.7相關(guān)概念：外部面，內(nèi)部面，邊界，次數(shù)deg（R）（1）（2）3.平面圖中的數(shù)量問題（1）P146定理6.9（描述平面圖中面的次數(shù)與邊數(shù)的數(shù)量關(guān)系）（2）歐拉公式（描述平面圖中邊,頂點(diǎn)及區(qū)域數(shù)量的關(guān)系）

n-m+r=2其中：n為平面圖中的頂點(diǎn)數(shù)，m為邊數(shù)，r為面數(shù)由歐拉公式可推得：定理1：設(shè)G為有v個(gè)結(jié)點(diǎn)e條邊的連通平面圖，若v≥3，則e≤3v-6由定理1可證明K5為非平面圖定理2：設(shè)G為一個(gè)平面簡單連通圖，其結(jié)點(diǎn)數(shù)v≥4，邊數(shù)為e，且G不以K3為其子圖，則e≤2v-4由定理2可證明K3,3為非平面圖說明：同一個(gè)平面圖可以有不同形狀的平面嵌入,它們是同構(gòu)的4.平面圖的判別：庫拉托夫斯基定理兩種對圖的同胚操作：（兩種操作是互逆的）⑴

對邊e的切割操作。設(shè)G中有邊e=(u,v)，取消e邊，增加頂點(diǎn)w，以及邊e1=(u,w),邊e2=(w,v)⑵對頂點(diǎn)v的貫通操作。設(shè)G中有二度頂點(diǎn)v，它是邊e1=(u,v),邊e2=(v,w)的共同端點(diǎn)，取消頂點(diǎn)v，以及邊e1，邊e2，增加邊e=(u,w)例：a為圖G，b，c分別是邊e切割和頂點(diǎn)v貫通操作的結(jié)果庫拉托夫斯基定理：P149定理6.13和定理6.145階無向完全圖K5無向完全二部圖K3,3例：下圖a為一非平面圖，b是a的子圖，c為經(jīng)同胚操作后的圖，可證c為二部圖，且為K3,3

5.對偶圖與地圖著色（1）對偶圖的定義：P150定義6.11（2）對平面連通圖G構(gòu)造其對偶圖G*的方法：a.在G的每一個(gè)面ri的內(nèi)部作一個(gè)G*的頂點(diǎn)vi*b.若G中面ri與rj有公共邊界，那么過邊界的每一邊ek作關(guān)聯(lián)vi*與vj*的一條邊ek*，ek*與G*的其他邊不相交c.當(dāng)ek為面ri的邊界而非ri與其他面的公共邊界時(shí)，作vi*的一條環(huán)與ek相交（且僅交于一處）。所作的環(huán)不與G*的邊相交(3)地圖的著色問題地圖的著色可以用平面圖的著色來刻畫，而平面圖的著色可以轉(zhuǎn)換為同等的結(jié)點(diǎn)著色問題例：給出平面圖G，對圖G著色可使用Welch-Powell算法（4）四色定理：任意平面圖都是4可著色的小結(jié)二部圖的判別歐拉圖的判別人有了知識，就會具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中自有黃金屋