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

第八章

一些特殊圖

第一節(jié)

二部圖

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

。第11頁(yè)第二節(jié)

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

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

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

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

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

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

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