教案2013第6-7章-圖論基礎(chǔ)4簡(jiǎn)

1、16.4 幾種特殊的圖6.4.1 二部圖6.4.2 歐拉圖（Euler）6.4.3 哈密爾頓圖（Hamilton）6.4.4 平面圖26.4.1 二部圖定義 6.19 設(shè) 無(wú)向圖 G = ， 若 V1, V2 使得V1V2 = V，V1V2 = ， 且 G 中的每條邊的兩個(gè)端點(diǎn)都 一個(gè)屬于V1， 另一個(gè)屬于V2， 則稱 G 為二部圖。記為： G = 。 若 G 是簡(jiǎn)單圖，且V1中每個(gè)頂點(diǎn)均與 V2中每個(gè)頂點(diǎn)相鄰， 則稱 G 為完全二部圖，記為 Kr, s 。3定理 6.7 無(wú)向圖 G = 是二部圖，當(dāng)且僅當(dāng) G 中無(wú)奇長(zhǎng)度的回路。 6.4.1 二部圖K23K334實(shí) 例非二部圖非二部圖5例 6

2、.12 某中學(xué)有 3 個(gè)課外活動(dòng)小組：數(shù)學(xué)組、計(jì)算機(jī)組、生物組。有 趙、錢(qián)、孫、李、周 5 名學(xué)生，問(wèn)分別在下述 3 種情況下，能否選出 3 人各任一個(gè)組的組長(zhǎng)? (1)數(shù)學(xué)組：趙、錢(qián) 計(jì)算機(jī)：趙、孫、李 生物組：孫、李、周 (2) 數(shù)學(xué)組：趙 計(jì)算機(jī)組：錢(qián)、孫、李 生物組：錢(qián)、孫、李、周 二部圖的應(yīng)用：6解：以課程組及學(xué)生為頂點(diǎn)集，作二部圖如下。由作圖可知： (1)，(2) 有多種方案可選；(3) 不可能。(1)數(shù)計(jì)生趙錢(qián)孫李周(2)數(shù)計(jì)生趙錢(qián)孫李周(3)數(shù)計(jì)生趙錢(qián)孫李周二部圖的應(yīng)用：76.4.2 歐拉圖（Euler）一、問(wèn)題的提出1736年瑞士數(shù)學(xué)家歐拉發(fā)表了圖論的第一篇著名論文“哥尼斯堡

3、七橋問(wèn)題”(簡(jiǎn)稱七橋問(wèn)題)。 這個(gè)問(wèn)題是：哥尼斯堡城有一條橫貫全城的普雷格爾河，城的各部分用七橋聯(lián)結(jié)，每逢節(jié)假日，有些城市居民進(jìn)行環(huán)城周游。 于是便產(chǎn)生了能否“從某地出發(fā)，通過(guò)每座橋恰好一次，在走遍了七橋后又返回到原處”的問(wèn)題。8哥尼斯堡城七橋問(wèn)題 圖普雷格爾河 “從某地出發(fā)，通過(guò)每座橋恰好一次，在走遍了七橋后，又返回到原處”9歐拉巧妙地把哥尼斯堡城圖化為圖 2 所示的圖，把陸地設(shè)為圖 2 中的頂點(diǎn)，把橋畫(huà)成聯(lián)結(jié)陸地結(jié)點(diǎn)的邊。圖 1 哥尼斯堡七橋問(wèn)題 圖 2 10 歐拉在這篇論文中提出了一條簡(jiǎn)單準(zhǔn)則，確定七橋問(wèn)題無(wú)解。后來(lái)簡(jiǎn)化為一筆畫(huà)問(wèn)題。 即一個(gè)圖，能否一筆不斷，也不重復(fù)地畫(huà)出來(lái)? 例： 下

4、面的各圖，是否可以一筆畫(huà)出？NYYN11 二、相關(guān)概念 設(shè)圖 G = 是連通圖（無(wú)向或有向圖）。 1、歐拉通路：G 中經(jīng)過(guò)每條邊一次且僅一次的通路。 2、歐拉回路：G 中經(jīng)過(guò)每條邊一次且僅一次的回路。 3、歐拉 圖：含歐拉回路的圖。說(shuō)明：（1）規(guī)定平凡圖為歐拉圖。（2）歐拉通路是簡(jiǎn)單通路、歐拉回路是簡(jiǎn)單回路。（3）圖中存在環(huán)，不影響圖的歐拉性。 6.4.2 歐拉圖（Euler）12三、歐拉圖判別定理 1（無(wú)向圖）定理 6.8 （1）無(wú)向圖 G 是歐拉圖， 當(dāng)且僅當(dāng)G 是連通的、且無(wú)奇度頂點(diǎn)。（2）無(wú)向圖 G 具有歐拉通路，但無(wú)歐拉回路， 當(dāng)且僅當(dāng) G 是連通的、且有且僅有 2 個(gè) 奇度頂點(diǎn)。

5、這 2 個(gè)奇度頂點(diǎn)，是每條歐拉通路的端點(diǎn)。13YNYN例：下面4 個(gè)圖中，哪些是歐拉圖？14由歐拉圖的判別定理知，哥尼斯堡七橋問(wèn)題無(wú)解！15例 6.13（P.179）無(wú)歐拉通路歐拉圖歐拉圖有歐拉通路非歐拉圖有歐拉通路非歐拉圖無(wú)歐拉通路16三、歐拉圖判別定理 2（有向圖）定理 6.9 （1）有向圖 D 是歐拉圖，當(dāng)且僅當(dāng) D 是連通的、 且每個(gè)頂點(diǎn)的入度出度(頂點(diǎn)度為偶數(shù))。（2）有向圖 D 有歐拉通路、但沒(méi)有歐拉回路， 當(dāng)且僅當(dāng) D 是連通的且存在兩個(gè)奇度頂點(diǎn)： 一個(gè)頂點(diǎn)，其 入度 - 出度 = 1； 一個(gè)頂點(diǎn)，其 出度 - 入度 = 1； 其余的頂點(diǎn)，入度 = 出度。17例 6.14（P.1

6、80）歐拉圖無(wú)歐拉通路無(wú)歐拉通路有歐拉通路無(wú)歐拉回路無(wú)歐拉通路有歐拉通路無(wú)歐拉回路181859 年，愛(ài)爾蘭數(shù)學(xué)家 哈密爾頓 首先提出 “環(huán)球周游”問(wèn)題。他用一個(gè) 正十二面體的20個(gè)頂點(diǎn)，代表世界上的20個(gè)大城市，這個(gè)正十二面體同構(gòu)于一個(gè)平面圖 。要求旅游者能否找到沿著正十二面體的棱，從某個(gè)頂點(diǎn)（即城市）出發(fā)，經(jīng)過(guò)每個(gè)頂點(diǎn)恰好一次，然后回到該頂點(diǎn)？6.4.3 哈密爾頓圖（Hamilton）19哈密爾頓圖20哈密爾頓圖21周游世界問(wèn)題(W.Hamilton, 1859年)22一、相關(guān)概念設(shè)圖 G = 是無(wú)向圖或有向圖。（1）哈密頓通路： 經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的通路。（2）哈密頓回路： 經(jīng)過(guò)

7、圖中所有頂點(diǎn)一次且僅一次的回路。（3）哈密頓圖： 具有哈密頓回路的圖。初級(jí)通路初級(jí)回路注：環(huán)與平行邊不影響圖的哈密頓性。23例：下面圖中，是否存在哈密爾頓通路或回路？有哈通路有哈回路有哈回路哈密爾頓圖哈密爾頓圖24三、哈密頓圖的應(yīng)用 （P.190 例 6.18）例：有 7 個(gè)人， A 會(huì)講英語(yǔ)， B 會(huì)講英語(yǔ)和漢語(yǔ)， C 會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)， D 會(huì)講日語(yǔ)和漢語(yǔ)， E 會(huì)講德語(yǔ)和意大利語(yǔ)， F 會(huì)講法語(yǔ)、日語(yǔ)和俄語(yǔ)， G 會(huì)講法語(yǔ)和德語(yǔ). 問(wèn)能否將他們沿圓桌安排就坐成一圈，使得每個(gè)人都能與兩旁的人交談?解：作無(wú)向圖， 每人是一個(gè)頂點(diǎn)。兩人之間聯(lián)一條邊 他們有共同的語(yǔ)言。A B C D E

8、 FG結(jié)論：ACEGFDBA 是一條哈密頓回路， 按此順序就坐即可。25例 ： 有 7 個(gè)人， A 會(huì)講英語(yǔ)， B 會(huì)講英語(yǔ)和漢語(yǔ)， C 會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)， D 會(huì)講日語(yǔ)和漢語(yǔ)， E 會(huì)講德語(yǔ)和意大利語(yǔ)， F 會(huì)講法語(yǔ)、日語(yǔ)和俄語(yǔ)， G 會(huì)講法語(yǔ)和德語(yǔ). 266.4.4 平面圖 平面圖與平面嵌入 平面圖的面及其次數(shù) 極大平面圖 極小非平面圖 歐拉公式 庫(kù)拉圖斯基定理 平面圖的對(duì)偶圖27一、平面圖與非平面圖定義 6.22 如果能將圖 G 除頂點(diǎn)處外邊不交叉地畫(huà)在平面上， 則稱 G 是平面圖。這個(gè)畫(huà)出的無(wú)邊交叉的圖稱作 G 的 平面嵌入。 沒(méi)有平面嵌入的圖，稱作非平面圖。 上圖中： (1)

9、 (4) 是平面圖， (5) 是非平面圖。 (2) 是 (1) 的平面嵌入； (4) 是 (3) 的平面嵌入。28二、平面圖的面與次數(shù)定義 6.23 設(shè) G 是一個(gè)平面嵌入，（1）G 的面：由 G 的邊將平面劃分成的每一個(gè)區(qū)域。（2）無(wú)限面(外部面)：面積無(wú)限的面，用 R0 表示。（3）有限面(內(nèi)部面)：面積有限 的面，用 R1, R2, 表示。 （4）面 Ri 的邊界： 包圍 Ri 的所有邊構(gòu)成的回路組。（5）面 Ri 的次數(shù)： Ri 邊界的長(zhǎng)度，用 deg(Ri) 表示。 說(shuō)明： 構(gòu)成一個(gè)面的邊界的回路組， 可能是初級(jí)回路、簡(jiǎn)單回路、復(fù)雜回路； 還可能是非連通的回路之并。29例 1：右圖有 個(gè)面。4deg(R1)=deg(R2)=deg(R3)=deg(R0)=1328R1 的邊界：R2 的邊界：R3 的邊界：R0 的邊界：ab c ef ga b c d d e，f g30(1)R1R2R3(2)R1R2R3說(shuō)明： （1） 一個(gè)平面圖，可以有多個(gè)不同形式的平面嵌入， 它們