北大離散數(shù)學(xué)chap8名師優(yōu)質(zhì)課獲獎市賽課一等獎?wù)n件

第八章

一些特殊圖

第一節(jié)

二部圖

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

。第11頁第二節(jié)

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

哈密爾頓圖第23頁內(nèi)容：哈密爾頓圖。重點(diǎn)：哈密爾頓圖定義。第24頁一、問題提出。1859年，英國數(shù)學(xué)家哈密爾頓，周游世界游戲。第25頁二、哈密爾頓圖。哈密爾頓通路——經(jīng)過圖中每個頂點(diǎn)一次且僅一次通路。哈密爾頓回路——經(jīng)過圖中每個頂點(diǎn)一次且僅一次回路。哈密爾頓圖——存在哈密爾頓回路圖。第26頁注意：(1)哈密爾頓通路與哈密爾頓回路不一樣。(2)哈密爾頓圖是指含有哈密爾頓回路(并非通路)圖。(3)哈密爾頓通路(回路)必是初級通路(回路)。

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

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

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

。第43頁注意：(1)一個平面圖無限面只有一個。(2)同一個平面圖能夠有不一樣形狀平面嵌入(相互同構(gòu))。(3)不一樣平面嵌入可能將某個有限面變成無限面，而將無限面變成有限面。第44頁例3、圖(2)，(3)都是圖(1)平面嵌入，圖(2)中，，圖(3)中，，它們即使形狀不一樣，但都與(1)同構(gòu)。第45頁2、平面圖中面次數(shù)與邊數(shù)關(guān)系。為面數(shù))(3、歐拉公式。設(shè)為連通平面圖，頂點(diǎn)數(shù)為，邊數(shù)為，面數(shù)為，則第46頁如例3中，圖(1)中，，則第47頁第八章

小結(jié)與例題第48頁一、二部圖。1、基本概念。二部圖，完全二部圖。2、利用。判定一個圖是否二部圖或完全二部圖。第49頁二、歐拉圖。1、基本概念。歐拉通路，歐拉回路，歐拉圖。2、利用。判定無向圖是否含有歐拉通路或回路。第50頁三、哈密爾頓圖。1、基本概念。哈密爾頓通路，哈密爾頓回路，哈密爾頓圖。2、利用。判斷無向圖是否含有哈密爾頓通路或回路。第51頁四、平面圖。1、基本概念。平面圖；平面圖面及次數(shù)。2、利用。利用定義判斷一些圖是否為平面圖。第52頁例1、畫出完全二部圖，和。解：第53頁例2、完全二部圖中，邊數(shù)為多少？解：例3、設(shè)完全二部圖，問：(1)當(dāng)為何值時，為歐拉圖。解：當(dāng)均為偶數(shù)時，為歐拉圖。(2)當(dāng)為何值時，為哈密爾頓圖。解：當(dāng)時，為哈密爾頓圖。第54頁例2、完全二部圖中，邊數(shù)為多少？解：例3、設(shè)完全二部圖，問：(3)各舉出一個完全二部圖是平面圖和非平面圖例子。解：，都是平面圖，，，是非平面圖。第55頁例4、畫一個歐拉圖，使它含有：(1)偶數(shù)個頂點(diǎn)，偶數(shù)條邊。(2)奇數(shù)個頂點(diǎn)，奇數(shù)條邊。解：解：第56頁例4、畫一個歐拉圖，使它含有：(3)偶數(shù)個頂點(diǎn)，奇數(shù)條邊。(4)奇數(shù)個頂點(diǎn)，偶數(shù)條邊。解：解：第57頁例5、今有七個人，已知以下事實(shí)：會講英語；會講英語和漢語；會講英語、意大利語和俄語；會講日語和漢語；會講德語和意大利語；會講法語、日語和俄語；會講法語和德語。試問這七個人應(yīng)怎樣排座位，才能使每個人都能和他身邊兩個人交談？第58頁解：語言就連一條邊，這么得到無向圖，再求哈密爾頓回路。用七個頂點(diǎn)表示七個人，若兩人之間有共同圖哈－回路第59頁例6、下列圖中哪些是歐拉圖，哪些是哈密爾頓圖，哪些是平面圖，哪些是二部圖？(1)解：不是歐拉圖，不是哈密爾頓圖，是平面圖，不是二部圖。第60頁例6、下列圖中哪些是歐拉圖，哪些是哈密爾頓圖，哪些是平面圖，哪些是二部圖？解：是歐拉圖，是哈密爾頓圖，是平面圖，但不是二部圖。(2)第61頁例6、下列圖中哪些是歐拉圖，哪些是哈密爾頓圖，哪些是平面圖，哪些是二部圖？解：不是歐拉圖，是哈密爾頓圖，是平面圖，不是二部圖。(3)第62頁例6、下列圖中哪些是歐拉圖，哪些是哈密爾頓圖，哪些是平面圖，哪些是二部圖？解：不是歐拉圖，是哈密爾頓圖，不是平面圖，不是二部圖。(4)第63頁解：因?yàn)槊總€頂點(diǎn)度數(shù)均為，故當(dāng)為奇數(shù)時，為歐拉圖。解：要使僅存在歐拉通路，中只能有2個奇度頂點(diǎn)，而不含偶度頂點(diǎn)(因每個頂點(diǎn)均為度)，故只