離散數(shù)學(xué)第八章

第八章

一些特殊的圖

第一節(jié)

二部圖

內(nèi)容：二部圖。重點(diǎn)：二部圖的定義及判定。本節(jié)討論的圖均為無(wú)向圖。一、二部圖的定義。1、若存在無(wú)向圖的頂點(diǎn)集的一個(gè)劃分，，，使得中任何一條邊的兩個(gè)端點(diǎn)分別在和中，則稱(chēng)為二部圖(或偶圖)。其中稱(chēng)互補(bǔ)頂點(diǎn)子集，記為。一、二部圖的定義。2、完全二部圖(或完全偶圖)。若中任一頂點(diǎn)與中每一頂點(diǎn)均有且只有一條邊相關(guān)聯(lián)，則稱(chēng)此二部圖為完全二部圖(或完全偶圖)。若，則記完全二部圖為，。例1、二部圖完全二部圖二部圖例1、完全二部圖二部圖二、判定定理。一個(gè)無(wú)向圖是二部圖當(dāng)且僅當(dāng)中無(wú)奇數(shù)長(zhǎng)度的回路。例2、判斷以下是否二部圖。(1)二部圖圖(1)中所有的回路長(zhǎng)度均為偶數(shù)。(思考，求其互補(bǔ)頂點(diǎn)子集)例2、判斷以下是否二部圖。二部圖例1同構(gòu)以上二圖均為。例2、判斷以下是否二部圖。例1同構(gòu)二部圖以上二圖均為。例2、判斷以下是否二部圖。不是二部圖，因圖中存在長(zhǎng)為3的回路

。第二節(jié)

歐拉圖內(nèi)容：歐拉圖。重點(diǎn)：1、歐拉圖的定義，2、無(wú)向圖是否具有歐拉通路或回路的判定。了解：有向圖是否具有歐拉通路或回路的判定。一、問(wèn)題的提出。1736年，瑞士數(shù)學(xué)家歐拉，哥尼斯堡七橋問(wèn)題二、定義。歐拉通路(歐拉跡)——通過(guò)圖中每條邊一次且僅一次，并且過(guò)每一頂點(diǎn)的通路。歐拉回路(歐拉閉跡)——通過(guò)圖中每條邊一次且僅一次，并且過(guò)每一頂點(diǎn)的回路。歐拉圖——存在歐拉回路的圖。注意：(1)歐拉通路與歐拉回路不同。(2)歐拉圖指具有歐拉回路(并非通路)的圖。(3)歐拉通路(回路)必是簡(jiǎn)單通路(回路)。(4)連通是具有歐拉通路(回路)的必要條件。(5)歐拉通路(回路)是經(jīng)過(guò)圖中所有邊的通路(回路)中最短的通路(回路)。三、無(wú)向圖是否具有歐拉通路或回路的判定。有歐拉通路連通，中只有兩個(gè)奇度頂點(diǎn)(它們分別是歐拉通路的兩個(gè)端點(diǎn))。有歐拉回路(為歐拉圖)連通，中均為偶度頂點(diǎn)。例1、以下圖形能否一筆畫(huà)成？例1、以下圖形能否一筆畫(huà)成？例2、兩只螞蟻比賽問(wèn)題。兩只螞蟻甲、乙分別處在圖中的頂點(diǎn)處，并設(shè)圖中各邊長(zhǎng)度相等。甲提出同乙比賽：從它們所在頂點(diǎn)出發(fā)，走過(guò)圖中所有邊最后到達(dá)頂點(diǎn)處。如果它們速度相同，問(wèn)誰(shuí)最先到達(dá)目的地？四、有向圖是否具有歐拉通路或回路的判定。有歐拉通路連通，除兩個(gè)頂點(diǎn)外，其余頂點(diǎn)的入度均等于出度，這兩個(gè)特殊的頂點(diǎn)中，一個(gè)頂點(diǎn)的入度比出度大1，另一個(gè)頂點(diǎn)的入度比出度小1。有歐拉回路(為歐拉圖)連通，中所有頂點(diǎn)的入度等于出度。例3、判斷以下有向圖是否歐拉圖。第三節(jié)

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

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

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

例如：都是極小非平面圖。，——若在非平面圖中任意刪除一條邊后，所得圖是平面圖，則面圖。為極小非平二、平面圖中面、次數(shù)與圖的頂點(diǎn)、邊數(shù)等的關(guān)系。1、定義：設(shè)是一個(gè)連通的平面圖(指某個(gè)平面嵌入)，的面——平面圖的區(qū)域(回路圍成的)，無(wú)限面(外部面)——面積無(wú)限的區(qū)域，記，有限面(內(nèi)部面)——面積有限的區(qū)域，邊界——包圍面的邊(回路)，二、平面圖中面、次數(shù)與圖的頂點(diǎn)、邊數(shù)等的關(guān)系。1、定義：設(shè)是一個(gè)連通的平面圖(指某個(gè)平面嵌入)，的次數(shù)——面邊界的長(zhǎng)度，記。若是非連通的平面圖，設(shè)有個(gè)連通分支，則的無(wú)限面的邊界由個(gè)回路形成。例2、的邊界為復(fù)雜回路

。注意：(1)一個(gè)平面圖的無(wú)限面只有一個(gè)。(2)同一個(gè)平面圖可以有不同形狀的平面嵌入(互相同構(gòu))。(3)不同的平面嵌入可能將某個(gè)有限面變成無(wú)限面，而將無(wú)限面變成有限面