第6章特殊的圖

1、第第6章章 特殊的圖特殊的圖教學要求教學要求v了解二部圖的概念了解二部圖的概念v了解歐拉圖的概念了解歐拉圖的概念v了解哈密頓圖的概念了解哈密頓圖的概念1.了解平面圖的概念了解平面圖的概念6.1 二部圖（僅討論無向圖）二部圖（僅討論無向圖）1.二部圖與完全二部圖：二部圖與完全二部圖：P140 定義定義6.1問題：給定一個圖，判斷它是否是二部圖？問題：給定一個圖，判斷它是否是二部圖？定理：定理： P140 定理定理6.12.匹配，極大匹配，最大匹配匹配，極大匹配，最大匹配 ，完美匹配：，完美匹配：P140定義定義6.23.完備匹配：完備匹配： P140定義定義6.3 判定完備匹配的充要條件：判定完

2、備匹配的充要條件： P141定理定理6.2和定理和定理6.34.二部圖的應用：解決分配問題 例1 P141例6.1 例2 在新學期開始時，某大學的計算機系對課程進行安排，下表給出了計算機系教師能承擔的課程情況,判定是否所有的課程都能有教師承擔，并給出一種排課方案教師承擔的課程趙老師(z)數據庫原理(DB1) 、大型數據庫(DB2) 、計算機組成原理(O) 錢老師(q)數據庫原理(DB1) 、大型數據庫(DB2)、數據結構(D) 孫老師(s)數據庫原理(DB1) 、大型數據庫(DB2)、數據結構(D)、Java (J) 李老師(l)Java (J)馮老師(f)數據結構(D)、Java (J)6.

3、2 歐拉圖歐拉圖(對所有邊的環(huán)游問題）對所有邊的環(huán)游問題）1.歐拉通路、歐拉回路：歐拉通路、歐拉回路：P142 定義定義6.4 注意注意：允許某個頂點通過兩次以上，但每條邊只能經過：允許某個頂點通過兩次以上，但每條邊只能經過一次一次問題：無向圖歐拉通路、歐拉回路的判別？問題：無向圖歐拉通路、歐拉回路的判別？無向圖歐拉路的判別：無向圖歐拉路的判別：P142 定理定理6.4(歐拉路的充要條件）歐拉路的充要條件）有向圖有向圖歐拉路歐拉路的判別：的判別：P142 定理定理6.52.歐拉圖：存在歐拉回路的圖歐拉圖：存在歐拉回路的圖3.歐拉圖的應用acdeb例：設某城市的街道布局如左圖所示，每條邊代表一條

4、特定街道的一段街區(qū)，每個結點代表街區(qū)間的交點。掃雪車車庫位于結點d，證明存在一條路線使得掃雪車清掃每個街區(qū)恰好一次且清掃完最后一個街區(qū)正好返回車庫。同時為這個掃雪車找出完成任務的路線6.3 哈密頓圖（對所有點的環(huán)游問題）哈密頓圖（對所有點的環(huán)游問題）1.哈密頓通路與回路：哈密頓通路與回路：P144定義定義6.5哈密頓圖的判別：世界難題！哈密頓圖的判別：世界難題！2.哈密頓圖：存在哈密頓回路的圖哈密頓圖：存在哈密頓回路的圖3.哈密頓圖的必要條件：哈密頓圖的必要條件：P144 定理定理6.66.4 平面圖（無向圖）平面圖（無向圖）1.平面圖的基本概念平面圖的基本概念舉例：設有一個電路有六個元件，三

5、個分為一組，舉例：設有一個電路有六個元件，三個分為一組，連接如（連接如（a）圖，是否有這樣的接線法，使得導線圖，是否有這樣的接線法，使得導線互不交叉？互不交叉？平面圖的定義：平面圖的定義：P146 定義定義6.62 平面圖的區(qū)域：平面圖的區(qū)域：P146 定義定義6.7 相關概念：外部面，內部面，邊界，次數相關概念：外部面，內部面，邊界，次數deg（R） （1）（2）3.平面圖中的數量問題（1）P146 定理6.9（描述平面圖中面的次數與邊數的數量關系）（2）歐拉公式（描述平面圖中邊,頂點及區(qū)域數量的關系） n-m+r =2其中：n為平面圖中的頂點數，m為邊數，r為面數由歐拉公式可推得：定理1：

6、設G為有v個結點e條邊的連通平面圖，若v3，則e3v-6由定理1可證明K5為非平面圖定理2：設G為一個平面簡單連通圖，其結點數v4，邊數為e，且G不以K3為其子圖，則e2v-4由定理2可證明K3,3為非平面圖說明：同一個平面圖可以有不同形狀的平面嵌入說明：同一個平面圖可以有不同形狀的平面嵌入,它們它們 是同構的是同構的4.平面圖的判別：庫拉托夫斯基定理平面圖的判別：庫拉托夫斯基定理兩種對圖的同胚操作：（兩種操作是互逆的） 對邊對邊e的切割操作的切割操作。 設G中有邊e=(u,v)，取消e邊，增加頂點w，以及邊e1=(u ,w),邊e2=(w ,v) 對頂點對頂點v的貫通操作的貫通操作。設G中有

7、二度頂點v，它是邊e1=(u ,v),邊e2=(v ,w)的共同端點，取消頂點v，以及邊e1，邊e2，增加邊e=(u ,w)例：a為圖G ，b，c分別是邊e切割和頂點v貫通操作的結果庫拉托夫斯基定理：庫拉托夫斯基定理：P149 定理定理6.13和定理和定理6.145階無向完全圖K5無向完全二部圖K3,3例：下圖例：下圖a為一非平面圖，為一非平面圖，b是是a的子圖，的子圖，c為經同胚操為經同胚操作后的圖，可證作后的圖，可證c為二部圖，且為為二部圖，且為K3,3 5. 對偶圖與地圖著色（1）對偶圖的定義：）對偶圖的定義：P150 定義定義6.11（2）對平面連通圖對平面連通圖G構造其對偶圖構造其對

8、偶圖G*的方法的方法：a.在G的每一個面ri的內部作一個G*的頂點vi*b.若G中面ri與rj有公共邊界，那么過邊界的每一邊ek作關聯(lián)vi*與vj*的一條邊ek* ， ek*與G*的其他邊不相交c.當ek為面ri的邊界而非ri與其他面的公共邊界時，作vi*的一條環(huán)與ek相交（且僅交于一處）。所作的環(huán)不與G*的邊相交(3)地圖的著色問題 地圖的著色可以用平面圖的著色來刻畫，而平面圖的著色可以轉換為同等的結點著色問題 例：給出平面圖G，對圖G著色可使用Welch-Powell算法（4） 四色定理：任意平面圖都是4可著色的小 結v二部圖的判別v歐拉圖的判別人有了知識，就會具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀