離散數學教學課件：第8章 一些特殊的圖

第八章

一些特殊的圖

第一節(jié)

二部圖

內容：二部圖。重點：二部圖的定義及判定。本節(jié)討論的圖均為無向圖。一、二部圖的定義。1、若存在無向圖的頂點集的一個劃分，，，使得中任何一條邊的兩個端點分別在和中，則稱為二部圖

(或偶圖)。其中稱互補頂點子集，記為。一、二部圖的定義。2、完全二部圖

(或完全偶圖)。若中任一頂點與中每一頂點均有且只有一條邊相關聯，則稱此二部圖為完全二部圖

(或完全偶圖)。若，則記完全二部圖為，。例1、二部圖完全二部圖二部圖例1、完全二部圖二部圖二、判定定理。一個無向圖是二部圖當且僅當中無奇數長度的回路。例2、判斷以下是否二部圖。(1)二部圖圖(1)中所有的回路長度均為偶數。(思考，求其互補頂點子集)例2、判斷以下是否二部圖。二部圖例1同構以上二圖均為。例2、判斷以下是否二部圖。例1同構二部圖以上二圖均為。例2、判斷以下是否二部圖。不是二部圖，因圖中存在長為3的回路

。第二節(jié)

歐拉圖內容：歐拉圖。重點：1、歐拉圖的定義，2、無向圖是否具有歐拉通路或回路的判定。了解：有向圖是否具有歐拉通路或回路的判定。一、問題的提出。1736年，瑞士數學家歐拉，哥尼斯堡七橋問題二、定義。歐拉通路

(歐拉跡)——通過圖中每條邊一次且僅一次，并且過每一頂點的通路。歐拉回路

(歐拉閉跡)——通過圖中每條邊一次且僅一次，并且過每一頂點的回路。歐拉圖——存在歐拉回路的圖。注意：(1)歐拉通路與歐拉回路不同。(2)歐拉圖指具有歐拉回路(并非通路)的圖。(3)歐拉通路(回路)必是簡單通路(回路)。(4)連通是具有歐拉通路(回路)的必要條件。(5)歐拉通路(回路)是經過圖中所有邊的通路(回路)中最短的通路(回路)。三、無向圖是否具有歐拉通路或回路的判定。有歐拉通路連通，中只有兩個奇度頂點(它們分別是歐拉通路的兩個端點)。有歐拉回路(為歐拉圖)連通，中均為偶度頂點。例1、以下圖形能否一筆畫成？例1、以下圖形能否一筆畫成？例2、兩只螞蟻比賽問題。兩只螞蟻甲、乙分別處在圖中的頂點處，并設圖中各邊長度相等。甲提出同乙比賽：從它們所在頂點出發(fā)，走過圖中所有邊最后到達頂點處。如果它們速度相同，問誰最先到達目的地？四、有向圖是否具有歐拉通路或回路的判定。有歐拉通路連通，除兩個頂點外，其余頂點的入度均等于出度，這兩個特殊的頂點中，一個頂點的入度比出度大1，另一個頂點的入度比出度小1。有歐拉回路(為歐拉圖)連通，中所有頂點的入度等于出度。例3、判斷以下有向圖是否歐拉圖。第三節(jié)

哈密爾頓圖內容：哈密爾頓圖。重點：哈密爾頓圖的定義。一、問題的提出。1859年，英國數學家哈密爾頓，周游世界游戲。二、哈密爾頓圖。哈密爾頓通路——通過圖中每個頂點一次且僅一次的通路。哈密爾頓回路——通過圖中每個頂點一次且僅一次的回路。哈密爾頓圖——存在哈密爾頓回路的圖。注意：(1)哈密爾頓通路與哈密爾頓回路不同。(2)哈密爾頓圖是指具有哈密爾頓回路(并非通路)的圖。(3)哈密爾頓通路(回路)必是初級通路(回路)。

(4)連通是具有哈密爾頓通路(回路)的必要條件。注意：(5)若圖通路。具有哈密爾頓回路，則必有哈密爾頓(6)階圖的哈密爾頓通路長為，回路長為。三、判定。采用嘗試的辦法。例1、判斷下圖是否具有哈密爾頓回路，通路。解：存在哈密爾頓通路，但不存在哈密爾頓回路。例1、判斷下圖是否具有哈密爾頓回路，通路。解：是哈密爾頓圖，存在哈密爾頓回路和通路。例1、判斷下圖是否具有哈密爾頓回路，通路。解：不存在哈密爾頓回路，也不存在哈密爾頓通路。例2、畫一個無向圖，使它(1)具有歐拉回路和哈密爾頓回路，解：(2)具有歐拉回路而沒有哈密爾頓回路，解：例2、畫一個無向圖，使它(3)具有哈密爾頓回路而沒有歐拉回路，(4)既沒有歐拉回路，也沒有哈密爾頓回路。解：解：第四節(jié)

平面圖內容：平面圖。重點：1、平面圖的概念，2、常見的非平面圖，，3、平面圖中面的次數與邊數關系4、平面圖的歐拉公式。了解：極大平面圖，極小非平面圖。本節(jié)討論的圖均為無向圖。一、平面圖的概念。1、定義：一個圖如果能以這樣的方式畫在平面上：除頂點處外沒有邊交叉出現，則稱為平面圖，畫出的沒有邊交叉出現的圖稱為的一個平面嵌入或的一個平面圖。例1、例1、2、極大平面圖，極小非平面圖。極大平面圖——若在平面圖中任意不相鄰的兩個頂點之間再加一條邊，所得圖為非平面圖，則為極大平面圖。例如：為極大平面圖。，2、極大平面圖，極小非平面圖。極小非平面圖

例如：都是極小非平面圖。，——若在非平面圖中任意刪除一條邊后，所得圖是平面圖，則面圖。為極小非平二、平面圖中面、次數與圖的頂點、邊數等的關系。1、定義：設是一個連通的平面圖

(指某個平面嵌入)，的面——平面圖的區(qū)域

(回路圍成的)，無限面

(外部面)——面積無限的區(qū)域，記，有限面

(內部面)——面積有限的區(qū)域，邊界——包圍面的邊

(回路)，二、平面圖中面、次數與圖的頂點、邊數等的關系。1、定義：設是一個連通的平面圖

(指某個平面嵌入)，的次數——面邊界的長度，記。若是非連通的平面圖，設有個連通分支，則的無限面的邊界由個回路形成。例2、的邊界為復雜回路

。注意：(1)一個平面圖的無限面只有一個。(2)同一個平面圖可以有不同形狀的平面嵌入(互相同構)。(3)不同的平面嵌入可能將某個有限面變成無限面，而將無限面變成有限面。例3、圖(2)，(3)都是圖(1)的平面嵌入，圖(2)中，，圖(3)中，，它們雖然形狀不同，但都與(1)同構。2、平面圖中面次數與邊數的關系。為面數)(3、歐拉公式。設為連通的平面圖，頂點數為，邊數為，面數為，則如例3中，圖(1)中，，則第八章

小結與例題一、二部圖。1、基本概念。二部圖，完全二部圖。2、運用。判定一個圖是否二部圖或完全二部圖。二、歐拉圖。1、基本概念。歐拉通路，歐拉回路，歐拉圖。2、運用。判定無向圖是否具有歐拉通路或回路。三、哈密爾頓圖。1、基本概念。哈密爾頓通路，哈密爾頓回路，哈密爾頓圖。2、運用。判斷無向圖是否具有哈密爾頓通路或回路。四、平面圖。1、基本概念。平面圖；平面圖的面及次數。2、運用。利用定義判斷某些圖是否為平面圖。例1、畫出完全二部圖，和。解：例2、完全二部圖中，邊數為多少？解：例3、設完全二部圖，問：(1)當為何值時，為歐拉圖。解：當均為偶數時，為歐拉圖。(2)當為何值時，為哈密爾頓圖。解：當時，為哈密爾頓圖。例2、完全二部圖中，邊數為多少？解：例3、設完全二部圖，問：(3)各舉出一個完全二部圖是平面圖和非平面圖的例子。解：，都是平面圖，，，是非平面圖。例4、畫一個歐拉圖，使它具有：(1)偶數個頂點，偶數條邊。(2)奇數個頂點，奇數條邊。解：解：例4、畫一個歐拉圖，使它具有：(3)偶數個頂點，奇數條邊。(4)奇數個頂點，偶數條邊。解：解：例5、今有七個人，已知下列事實：會講英語；會講英語和漢語；會講英語、意大利語和俄語；會講日語和漢語；會講德語和意大利語；會講法語、日語和俄語；會講法語和德語。試問這七個人應如何排座位，才能使每個人都能和他身邊的兩個人交談？解：語言就連一條邊，這樣得到無向圖，再求的哈密爾頓回路。用七個頂點表示七個人，若兩人之間有共同圖的哈－回路例6、下圖中哪些是歐拉圖，哪些是哈密爾頓圖，哪些是平面圖，哪些是二部圖？(1)解：不是歐拉圖，不是哈密爾頓圖，是平面圖，不是二部圖。例6、下圖中哪些是歐拉圖，哪些是哈密爾頓圖，哪些是平面圖，哪些是二部圖？解：是歐拉圖，是哈密爾頓圖，是平面圖，但不是二部圖。(2)例6、下圖中哪些是歐拉圖，哪些是哈密爾頓圖，哪些是平面圖，哪些是二部圖？解：不是歐拉圖，是哈密爾頓圖，是平面圖，不是二部圖。(3)例6、下圖中哪些是歐拉圖，哪些是哈密爾頓圖，哪些是平面圖，哪些是二部圖？解：不是歐拉圖，是哈密爾頓圖，不是平面圖，不是二部圖。(4)解：由于的每個頂點的度數均為，故當為奇數時，為歐拉圖。解：要使僅存在歐拉通路，中只能有2個奇度頂點，而不含偶度頂點(因每個頂點均為度)，故只有符合