圖論III 幾種特殊的圖

1、1第二課第二課 幾種幾種特殊的圖特殊的圖 2.1 二部圖二部圖2.2 歐拉圖歐拉圖2.3 哈密頓圖哈密頓圖2.4 平面圖平面圖 22.1 二部圖二部圖 二部圖二部圖完全二部圖完全二部圖3二部圖二部圖 定義定義 設(shè)無向圖設(shè)無向圖 G=, 若能將若能將V 劃分成劃分成V1 和和 V2 (V1 V2=V, V1 V2=), 使得使得G中的每條邊的兩個端中的每條邊的兩個端點都一個屬于點都一個屬于V1, 另一個屬于另一個屬于V2, 則稱則稱G為為二部圖二部圖, 記為記為, 稱稱V1和和V2為為互補頂點子集互補頂點子集. 又若又若G是簡單圖是簡單圖, 且且V1中每個頂點都與中每個頂點都與V2中每個頂點相鄰

2、中每個頂點相鄰,則稱則稱G為為完全二部圖完全二部圖, 記為記為Kr,s, 其中其中r=|V1|, s=|V2|. 注意注意: n 階零圖為二部圖階零圖為二部圖. 4二部圖二部圖( (續(xù)續(xù)) ) 例例 下述各圖是否是二部圖下述各圖是否是二部圖? ? 定理定理 無向圖無向圖G=是二部圖當且僅當是二部圖當且僅當G中無奇圈中無奇圈 不是不是52.2 歐拉圖歐拉圖歐拉路與歐拉回路歐拉路與歐拉回路存在歐拉路和歐拉回路的充分必要條件存在歐拉路和歐拉回路的充分必要條件 6哥尼斯堡七橋問題哥尼斯堡七橋問題 要求找一條路線要求找一條路線,經(jīng)過每座橋一次且經(jīng)過每座橋一次且僅一次僅一次7歐拉圖歐拉圖 歐拉路歐拉路:

3、圖中經(jīng)過每個頂點且恰好經(jīng)過每條邊一次圖中經(jīng)過每個頂點且恰好經(jīng)過每條邊一次的路的路. 歐拉回路歐拉回路: 圖中經(jīng)過每個頂點恰好經(jīng)過每條邊一次圖中經(jīng)過每個頂點恰好經(jīng)過每條邊一次的回路的回路.歐拉圖歐拉圖: 有歐拉回路的圖有歐拉回路的圖.半歐拉圖半歐拉圖: 有歐拉路有歐拉路,但無歐拉回路的圖但無歐拉回路的圖.幾點說明：上述定義對無向圖和有向圖都適用幾點說明：上述定義對無向圖和有向圖都適用.規(guī)定平凡圖為歐拉圖規(guī)定平凡圖為歐拉圖.歐拉路是跡歐拉路是跡, 歐拉回路是閉跡歐拉回路是閉跡.環(huán)不影響圖的歐拉性環(huán)不影響圖的歐拉性. 8歐拉圖實例歐拉圖實例例例 是否是歐拉圖或半歐拉圖是否是歐拉圖或半歐拉圖?歐拉圖歐

4、拉圖歐拉圖歐拉圖半歐拉圖半歐拉圖半歐拉圖半歐拉圖不是不是不是不是9歐拉圖的判別法歐拉圖的判別法 定理定理 無向圖無向圖G為歐拉圖當且僅當為歐拉圖當且僅當G連通且無奇度頂連通且無奇度頂點點. G是半歐拉圖當且僅當是半歐拉圖當且僅當G連通且恰有兩個奇度頂連通且恰有兩個奇度頂點點. 定理定理 有向圖有向圖D是歐拉圖當且僅當是歐拉圖當且僅當D連通且每個頂點連通且每個頂點的入度都等于出度的入度都等于出度. D是半歐拉圖當且僅當是半歐拉圖當且僅當D連通且連通且恰有兩個奇度頂點恰有兩個奇度頂點, 其中一個入度比出度大其中一個入度比出度大1, 另一個另一個出度比入度大出度比入度大1, 其余頂點的入度等于出度其

5、余頂點的入度等于出度.10實例實例例例1 哥尼斯堡七橋問題哥尼斯堡七橋問題 4個奇度頂點個奇度頂點, 不存在不存在 歐拉路歐拉路, 更不存在更不存在 歐拉回路歐拉回路,例例2 下面兩個圖都是歐拉圖下面兩個圖都是歐拉圖. 從從A點出發(fā)點出發(fā), 如何一次成功地走出一條歐拉回路來？如何一次成功地走出一條歐拉回路來？ 112.3 哈密頓圖哈密頓圖 哈密頓路和哈密頓回路哈密頓路和哈密頓回路存在哈密頓路和哈密頓回路的充分條件與必要條存在哈密頓路和哈密頓回路的充分條件與必要條件件12哈密頓周游世界問題哈密頓周游世界問題每個頂點是一個城市每個頂點是一個城市, , 有有20個城市個城市, , 要求從一個要求從一

6、個城市出發(fā)城市出發(fā), , 恰好經(jīng)過每一個城市一次恰好經(jīng)過每一個城市一次, , 回到出發(fā)回到出發(fā)點點. .13哈密頓圖的定義哈密頓圖的定義哈密頓路哈密頓路: : 經(jīng)過圖中所有頂點一次且僅一次的路經(jīng)過圖中所有頂點一次且僅一次的路. .哈密頓回路哈密頓回路: : 經(jīng)過圖中所有頂點一次且僅一次的回路經(jīng)過圖中所有頂點一次且僅一次的回路. .哈密頓圖哈密頓圖: : 具有哈密頓回路的圖具有哈密頓回路的圖. .半哈密頓圖半哈密頓圖: : 具有哈密頓路而無哈密頓回路的圖具有哈密頓路而無哈密頓回路的圖. . 幾點說明：幾點說明：平凡圖是哈密頓圖平凡圖是哈密頓圖. .哈密頓路是通路，哈密頓回路是圈哈密頓路是通路，哈

7、密頓回路是圈. .環(huán)不影響圖的哈密頓性，對環(huán)不影響圖的哈密頓性，對3 3階以上圖，平行邊也不影響圖階以上圖，平行邊也不影響圖的哈密頓性的哈密頓性. .14實例實例例例 是否是哈密頓圖是否是哈密頓圖,半哈密頓圖半哈密頓圖?哈密頓圖哈密頓圖哈密頓圖哈密頓圖半哈密頓圖半哈密頓圖*不是不是*15無向哈密頓圖的一個必要條件無向哈密頓圖的一個必要條件 定理定理 設(shè)無向圖設(shè)無向圖G=是哈密頓圖是哈密頓圖, 則對于任意則對于任意V1 V且且V1, 均有均有 p(G V1) |V1|.證證 設(shè)設(shè)C為為G中一條哈密頓回路中一條哈密頓回路, 有有p(C V1) |V1|. 又因為又因為C G, 故故 p(G V1)

8、 p(C V1) |V1|. 幾點說明幾點說明定理中的條件是哈密頓圖的必要條件定理中的條件是哈密頓圖的必要條件, 但不是充分條件但不是充分條件.可利用該定理判斷某些圖不是哈密頓圖可利用該定理判斷某些圖不是哈密頓圖. 由定理可知由定理可知, Kr,s當當s r時不是哈密頓圖時不是哈密頓圖. 當當r 2時時, Kr,r是哈密頓圖是哈密頓圖, 而而Kr,r+1是半哈密頓圖是半哈密頓圖. 16實例實例例例 設(shè)設(shè)G為為n階無向連通簡單圖階無向連通簡單圖, 若若G中有割點或橋中有割點或橋, 則則G不是哈密頓圖不是哈密頓圖.證證 (1) 設(shè)設(shè)v為割點為割點, 則則p(G v) 2|v|=1. 根據(jù)定理根據(jù)定

9、理, G不是哈密頓圖不是哈密頓圖.(2) 若若G是是K2(K2有橋有橋), 它顯然不是哈密頓圖它顯然不是哈密頓圖. 除除K2外外, 其他的有橋連通圖均有割點其他的有橋連通圖均有割點. 由由(1), 得證得證G不是不是哈密頓圖哈密頓圖.17無向哈密頓圖的一個充分條件無向哈密頓圖的一個充分條件 定理定理 設(shè)設(shè)G是是n階無向簡單圖階無向簡單圖, 若任意兩個不相鄰的若任意兩個不相鄰的頂點的度數(shù)之和大于等于頂點的度數(shù)之和大于等于n 1, 則則G中存在哈密頓通中存在哈密頓通路路. 當當n 3時時, 若任意兩個不相鄰的頂點的度數(shù)之和若任意兩個不相鄰的頂點的度數(shù)之和大于等于大于等于n, 則則G中存在哈密頓回路

10、中存在哈密頓回路. 由定理由定理, 當當n 3時時, Kn均為哈密頓圖均為哈密頓圖.定理中的條件是充分條件定理中的條件是充分條件, 但不是必要條件但不是必要條件.例如例如, n( 5)個頂點的路徑存在哈密頓路個頂點的路徑存在哈密頓路, 但不滿但不滿足條件足條件. n( 5)個頂點的圈是哈密頓圖個頂點的圈是哈密頓圖, 不滿足條件不滿足條件.18判斷是否是哈密頓圖判斷是否是哈密頓圖的可行方法的可行方法n觀察出一條哈密頓回路觀察出一條哈密頓回路 例如例如 右圖右圖(周游世界問題周游世界問題)中紅中紅邊給出一條哈密頓回路邊給出一條哈密頓回路, 故它故它是哈密頓圖是哈密頓圖. n滿足充分條件滿足充分條件

11、例如例如 當當n 3時時, Kn中任何兩個不同的頂點中任何兩個不同的頂點 u,v, 均均有有d(u)+d(v) = 2(n 1) n, 所以所以Kn為哈密頓圖為哈密頓圖. 19應(yīng)用實例應(yīng)用實例例例 某次國際會議某次國際會議8人參加，已知每人至少與他人參加，已知每人至少與他4人人有共同語言，問服務(wù)員能否將他們安排在同一有共同語言，問服務(wù)員能否將他們安排在同一張圓桌就座，使得每個人都能與兩邊的人交談？張圓桌就座，使得每個人都能與兩邊的人交談？解解 作無向圖作無向圖G=, 其中其中V=v|v為與會者為與會者， E=(u,v) | u,v V, u與與v有共同語言有共同語言, 且且u v. G為簡單圖

12、為簡單圖. 根據(jù)條件根據(jù)條件, v V, d(v) 4. 于是，于是， u,v V, 有有d(u)+d(v) 8. 由定理可知由定理可知G為哈密頓圖為哈密頓圖. 服務(wù)員在服務(wù)員在G中找一條哈密頓回路中找一條哈密頓回路C，按，按C中相鄰關(guān)中相鄰關(guān)系安排座位即可系安排座位即可. 202.4 平面圖平面圖 平面圖與平面嵌入平面圖與平面嵌入平面圖的面平面圖的面極大平面圖與極小非平面圖極大平面圖與極小非平面圖歐拉公式歐拉公式平面圖的對偶圖平面圖的對偶圖地圖著色與四色定理地圖著色與四色定理 21平面圖和平面嵌入平面圖和平面嵌入 定義定義 如果能將圖如果能將圖G除頂點外邊不相交地畫在平面上除頂點外邊不相交地

13、畫在平面上, 則稱則稱G是是平面圖平面圖. 這個畫出的無邊相交的圖稱作這個畫出的無邊相交的圖稱作G的的平面嵌入平面嵌入. 沒有平面嵌入的圖稱作沒有平面嵌入的圖稱作非平面圖非平面圖. 例如例如 下圖中下圖中(1)(4)是平面圖是平面圖, (2)是是(1)的平面嵌入，的平面嵌入，(4)是是(3)的平面嵌入的平面嵌入. (5)是非平面圖是非平面圖.22平面圖和平面嵌入平面圖和平面嵌入( (續(xù)續(xù)) )今后稱一個圖是平面圖今后稱一個圖是平面圖, 可以是指定義中的平面圖可以是指定義中的平面圖, 又可以又可以是指平面嵌入是指平面嵌入, 視當時的情況而定視當時的情況而定. 當討論的問題與圖的畫當討論的問題與圖

14、的畫法有關(guān)時法有關(guān)時, 是指平面嵌入是指平面嵌入. K5和和K3,3是非平面圖是非平面圖設(shè)設(shè)G G, 若若G為平面圖為平面圖, 則則G 也是也是 平面圖平面圖; 若若G 為非平面圖為非平面圖, 則則G也也 是非平面圖是非平面圖. Kn(n 5), Kn,m(n,m 3)都是非平面圖都是非平面圖. 平行邊與環(huán)不影響圖的平面性平行邊與環(huán)不影響圖的平面性. 23平面圖的面與次數(shù)平面圖的面與次數(shù)設(shè)設(shè)G是一個平面嵌入是一個平面嵌入G的面的面: 由由G的邊將平面劃分成的每一個區(qū)域的邊將平面劃分成的每一個區(qū)域無限面無限面(外部面外部面): 面積無限的面面積無限的面, 用用R0表示表示有限面有限面(內(nèi)部面內(nèi)部

15、面): 面積有限的面面積有限的面, 用用R1, R2, Rk表示表示 面面Ri的邊界的邊界: 包圍包圍Ri的所有邊構(gòu)成的回路（組）的所有邊構(gòu)成的回路（組）面面Ri的次數(shù)的次數(shù): Ri邊界的長度，用邊界的長度，用deg(Ri)表示表示 定理定理 平面圖各面的次數(shù)之和等于邊數(shù)的平面圖各面的次數(shù)之和等于邊數(shù)的2倍倍.證證 每條邊可能在兩個面的公共邊界上，也可能只在一個面每條邊可能在兩個面的公共邊界上，也可能只在一個面的邊界上的邊界上. 前者前者, 在每個面的邊界上這條邊只出現(xiàn)一次在每個面的邊界上這條邊只出現(xiàn)一次, 計算計算兩次兩次. 后者后者, 它在這個面的邊界上出現(xiàn)它在這個面的邊界上出現(xiàn)2次次,

16、也計算兩次也計算兩次. 24平面圖的面與次數(shù)平面圖的面與次數(shù)( (續(xù)續(xù)) )例例1 右圖有右圖有4個面?zhèn)€面, deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8. 例例2 左邊左邊2個圖是同一個平面?zhèn)€圖是同一個平面圖的平面嵌入圖的平面嵌入. R1在在(1)中是中是外部面外部面, 在在(2)中是內(nèi)部面中是內(nèi)部面; R2在在(1)中是內(nèi)部面中是內(nèi)部面, 在在(2)中是中是外部面外部面. 其實其實, 在平面嵌入中在平面嵌入中可把任何面作為外部面可把任何面作為外部面.25極大平面圖極大平面圖 定義定義 若若G是簡單平面圖是簡單平面圖, 并且在任意兩個不相鄰的頂點之并且

17、在任意兩個不相鄰的頂點之間加一條新邊所得圖為非平面圖間加一條新邊所得圖為非平面圖, 則稱則稱G為為極大平面圖極大平面圖.例如例如, K5, K3,3若刪去一條邊是極大平面圖若刪去一條邊是極大平面圖. K1, K2, K3, K4都是極大平面圖都是極大平面圖(它們已無不相鄰頂點它們已無不相鄰頂點).極大平面圖必連通極大平面圖必連通*. 階數(shù)大于等于階數(shù)大于等于3的極大平面圖中不可能有割點和橋的極大平面圖中不可能有割點和橋*. 任何任何n(n 4)階極大平面圖階極大平面圖G均有均有 (G) 3. 定理定理 n(n 3)階簡單平面圖是極大平面圖當且僅當它連通且階簡單平面圖是極大平面圖當且僅當它連通且

18、每個面的次數(shù)都為每個面的次數(shù)都為3. 26實例實例例例 是否是極大平面圖是否是極大平面圖? 不是不是不是不是是是27極小非平面圖極小非平面圖 定義定義 若若G是非平面圖是非平面圖, 并且任意刪除一條邊所得圖并且任意刪除一條邊所得圖都是平面圖都是平面圖, 則稱則稱G為為極小非平面圖極小非平面圖.極小非平面圖必為簡單圖極小非平面圖必為簡單圖例如例如, K5, K3,3是極小非平面圖是極小非平面圖28歐拉公式歐拉公式 定理定理 (歐拉公式歐拉公式) 設(shè)設(shè)G為為n階階m條邊條邊r個面的連通平面圖個面的連通平面圖, 則則 n m+r=2. 證證 對邊數(shù)對邊數(shù)m做歸納證明做歸納證明. m=0, G為平凡圖

19、為平凡圖, 結(jié)論為真結(jié)論為真.設(shè)設(shè)m=k(k 0)結(jié)論為真結(jié)論為真, m=k+1時分情況討論如下時分情況討論如下: (1) 若若G中有一個中有一個1度頂點度頂點v, 則則G =G-v 連通連通, 有有n-1個頂點個頂點, k條邊和條邊和r個面?zhèn)€面. 由由歸納假設(shè)歸納假設(shè), (n-1)-k+r=2, 即即n-(k+1)+r=2, 得證得證m=k+1時結(jié)論成立時結(jié)論成立. (2) 否則否則, G中必有圈中必有圈. 刪除一個圈上的一條邊刪除一個圈上的一條邊,記作記作G . G 連通連通, 有有n個頂點個頂點,k條邊和條邊和r-1個面?zhèn)€面. 由由歸納假設(shè)歸納假設(shè), n-k+(r-1)=2, 即即n-(

20、k+1)+r=2, 得證得證m=k+1時結(jié)論也成立時結(jié)論也成立. 29歐拉公式歐拉公式( (續(xù)續(xù)) )推論推論(歐拉公式的推廣歐拉公式的推廣) 設(shè)設(shè)G是有是有 p (p 2) 個連通分支個連通分支的平面圖的平面圖, 則則 n m + r = p + 1證證 設(shè)第設(shè)第 i 個連通分支有個連通分支有 ni個頂點個頂點, mi 條邊和條邊和 ri 個面?zhèn)€面. 對各連通分支用歐拉公式對各連通分支用歐拉公式, ni mi + ri = 2, i = 1, 2, , p求和并注意求和并注意 r + p 1 = r1+rp, 即得即得 n m + r = p + 130平面圖的性質(zhì)平面圖的性質(zhì)定理定理 設(shè)設(shè)

21、G為為n階階m條邊的連通簡單平面圖條邊的連通簡單平面圖, 若若n 3, 則則mn-6 推論推論 K5 和和 K3,3不是平面圖不是平面圖. K5K3,331同胚與收縮同胚與收縮 消去消去2度頂點度頂點v 如上圖從如上圖從(1)到到(2)插入插入2度頂點度頂點v 如上圖從如上圖從(2)到到(1)G1與與G2同胚同胚: G1與與G2同構(gòu)同構(gòu), 或或經(jīng)過反復(fù)插入、或消去經(jīng)過反復(fù)插入、或消去2度頂度頂點后同構(gòu)點后同構(gòu)收縮邊收縮邊e 如下圖從如下圖從(1)到到(2)32庫拉圖斯基定理庫拉圖斯基定理定理定理 G是平面圖是平面圖G中不含與中不含與K5同胚的子圖同胚的子圖, 也不也不含與含與K3,3同胚的子圖

22、同胚的子圖.定理定理 G是平面圖是平面圖G中無可收縮為中無可收縮為K5的子圖的子圖, 也無也無可收縮為可收縮為K3,3的子圖的子圖. 33非平面圖證明非平面圖證明例例 證明下述證明下述2個圖均為非平面圖個圖均為非平面圖. 收縮收縮2條邊條邊 收縮收縮2條邊條邊 K3,3取子圖取子圖K5取子圖取子圖34平面圖的對偶圖平面圖的對偶圖 定義定義 設(shè)平面圖設(shè)平面圖G, 有有n個頂點個頂點, m條邊和條邊和r個面?zhèn)€面, G的的對偶圖對偶圖G*=如下：如下：在在G的每一個面的每一個面Ri中任取一個點中任取一個點vi*作為作為G*的頂點的頂點, V*= vi*| i=1,2,r .對對G每一條邊每一條邊ek

23、, 若若ek在在G的面的面Ri與與Rj的公共邊界上的公共邊界上, 則作邊則作邊ek*=(vi*,vj*), 且與且與ek相交相交; 若若ek為為G中的橋且在中的橋且在面面Ri的邊界上的邊界上, 則作環(huán)則作環(huán)ek*=(vi*,vi*). E*= ek*| k=1,2, ,m . 35平面圖的對偶圖的實例平面圖的對偶圖的實例例例 黑色實線為原平面圖黑色實線為原平面圖, 紅色虛線為其對偶圖紅色虛線為其對偶圖 36平面圖的對偶圖的性質(zhì)平面圖的對偶圖的性質(zhì)性質(zhì)：性質(zhì)：對偶圖是平面圖，而且是平面嵌入對偶圖是平面圖，而且是平面嵌入.對偶圖是連通圖對偶圖是連通圖若邊若邊e為為G中的環(huán)，則中的環(huán)，則G*與與e對應(yīng)的邊對應(yīng)的邊e*為橋為橋; 若若e為橋，則為橋，則G*中與中與e對應(yīng)的邊對應(yīng)的邊e*為環(huán)為環(huán).同構(gòu)的平面圖的對偶圖不一定同構(gòu)同構(gòu)的平面圖的對偶圖不一定同構(gòu). 上頁兩個平面圖同構(gòu)上頁兩個平面圖同構(gòu), 它們的對偶圖不同構(gòu)它