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

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

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

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

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

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

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

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

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

9、 (4) 是平面圖， (5) 是非平面圖。 (2) 是 (1) 的平面嵌入； (4) 是 (3) 的平面嵌入。28二、平面圖的面與次數(shù)定義 6.23 設(shè) G 是一個平面嵌入，（1）G 的面：由 G 的邊將平面劃分成的每一個區(qū)域。（2）無限面(外部面)：面積無限的面，用 R0 表示。（3）有限面(內(nèi)部面)：面積有限 的面，用 R1, R2, 表示。 （4）面 Ri 的邊界： 包圍 Ri 的所有邊構(gòu)成的回路組。（5）面 Ri 的次數(shù)： Ri 邊界的長度，用 deg(Ri) 表示。 說明： 構(gòu)成一個面的邊界的回路組， 可能是初級回路、簡單回路、復(fù)雜回路； 還可能是非連通的回路之并。29例 1：右圖有 個面。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說明： （1） 一個平面圖，可以有多個不同形式的平面嵌入， 它們