圖論III 幾種特殊的圖

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

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

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

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

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

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

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

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

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

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

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

12、為簡(jiǎn)單圖. 根據(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 平面圖平面圖 平面圖與平面嵌入平面圖與平面嵌入平面圖的面平面圖的面極大平面圖與極小非平面圖極大平面圖與極小非平面圖歐拉公式歐拉公式平面圖的對(duì)偶圖平面圖的對(duì)偶圖地圖著色與四色定理地圖著色與四色定理 21平面圖和平面嵌入平面圖和平面嵌入 定義定義 如果能將圖如果能將圖G除頂點(diǎn)外邊不相交地畫(huà)在平面上除頂點(diǎn)外邊不相交地

13、畫(huà)在平面上, 則稱(chēng)則稱(chēng)G是是平面圖平面圖. 這個(gè)畫(huà)出的無(wú)邊相交的圖稱(chēng)作這個(gè)畫(huà)出的無(wú)邊相交的圖稱(chēng)作G的的平面嵌入平面嵌入. 沒(méi)有平面嵌入的圖稱(chēng)作沒(méi)有平面嵌入的圖稱(chēng)作非平面圖非平面圖. 例如例如 下圖中下圖中(1)(4)是平面圖是平面圖, (2)是是(1)的平面嵌入，的平面嵌入，(4)是是(3)的平面嵌入的平面嵌入. (5)是非平面圖是非平面圖.22平面圖和平面嵌入平面圖和平面嵌入( (續(xù)續(xù)) )今后稱(chēng)一個(gè)圖是平面圖今后稱(chēng)一個(gè)圖是平面圖, 可以是指定義中的平面圖可以是指定義中的平面圖, 又可以又可以是指平面嵌入是指平面嵌入, 視當(dāng)時(shí)的情況而定視當(dāng)時(shí)的情況而定. 當(dāng)討論的問(wèn)題與圖的畫(huà)當(dāng)討論的問(wèn)題與圖

14、的畫(huà)法有關(guān)時(shí)法有關(guān)時(shí), 是指平面嵌入是指平面嵌入. 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è)平面嵌入G的面的面: 由由G的邊將平面劃分成的每一個(gè)區(qū)域的邊將平面劃分成的每一個(gè)區(qū)域無(wú)限面無(wú)限面(外部面外部面): 面積無(wú)限的面面積無(wú)限的面, 用用R0表示表示有限面有限面(內(nèi)部面內(nèi)部

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

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

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

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

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

20、k+1)+r=2, 得證得證m=k+1時(shí)結(jié)論也成立時(shí)結(jié)論也成立. 29歐拉公式歐拉公式( (續(xù)續(xù)) )推論推論(歐拉公式的推廣歐拉公式的推廣) 設(shè)設(shè)G是有是有 p (p 2) 個(gè)連通分支個(gè)連通分支的平面圖的平面圖, 則則 n m + r = p + 1證證 設(shè)第設(shè)第 i 個(gè)連通分支有個(gè)連通分支有 ni個(gè)頂點(diǎn)個(gè)頂點(diǎn), mi 條邊和條邊和 ri 個(gè)面?zhèn)€面. 對(duì)各連通分支用歐拉公式對(duì)各連通分支用歐拉公式, 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條邊的連通簡(jiǎn)單平面圖條邊的連通簡(jiǎn)單平面圖, 若若n 3, 則則mn-6 推論推論 K5 和和 K3,3不是平面圖不是平面圖. K5K3,331同胚與收縮同胚與收縮 消去消去2度頂點(diǎn)度頂點(diǎn)v 如上圖從如上圖從(1)到到(2)插入插入2度頂點(diǎn)度頂點(diǎn)v 如上圖從如上圖從(2)到到(1)G1與與G2同胚同胚: G1與與G2同構(gòu)同構(gòu), 或或經(jīng)過(guò)反復(fù)插入、或消去經(jīng)過(guò)反復(fù)插入、或消去2度頂度頂點(diǎn)后同構(gòu)點(diǎn)后同構(gòu)收縮邊收縮邊e 如下圖從如下圖從(1)到到(2)32庫(kù)拉圖斯基定理庫(kù)拉圖斯基定理定理定理 G是平面圖是平面圖G中不含與中不含與K5同胚的子圖同胚的子圖, 也不也不含與含與K3,3同胚的子圖

22、同胚的子圖.定理定理 G是平面圖是平面圖G中無(wú)可收縮為中無(wú)可收縮為K5的子圖的子圖, 也無(wú)也無(wú)可收縮為可收縮為K3,3的子圖的子圖. 33非平面圖證明非平面圖證明例例 證明下述證明下述2個(gè)圖均為非平面圖個(gè)圖均為非平面圖. 收縮收縮2條邊條邊 收縮收縮2條邊條邊 K3,3取子圖取子圖K5取子圖取子圖34平面圖的對(duì)偶圖平面圖的對(duì)偶圖 定義定義 設(shè)平面圖設(shè)平面圖G, 有有n個(gè)頂點(diǎn)個(gè)頂點(diǎn), m條邊和條邊和r個(gè)面?zhèn)€面, G的的對(duì)偶圖對(duì)偶圖G*=如下：如下：在在G的每一個(gè)面的每一個(gè)面Ri中任取一個(gè)點(diǎn)中任取一個(gè)點(diǎn)vi*作為作為G*的頂點(diǎn)的頂點(diǎn), V*= vi*| i=1,2,r .對(duì)對(duì)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平面圖的對(duì)偶圖的實(shí)例平面圖的對(duì)偶圖的實(shí)例例例 黑色實(shí)線為原平面圖黑色實(shí)線為原平面圖, 紅色虛線為其對(duì)偶圖紅色虛線為其對(duì)偶圖 36平面圖的對(duì)偶圖的性質(zhì)平面圖的對(duì)偶圖的性質(zhì)性質(zhì)：性質(zhì)：對(duì)偶圖是平面圖，而且是平面嵌入對(duì)偶圖是平面圖，而且是平面嵌入.對(duì)偶圖是連通圖對(duì)偶圖是連通圖若邊若邊e為為G中的環(huán)，則中的環(huán)，則G*與與e對(duì)應(yīng)的邊對(duì)應(yīng)的邊e*為橋?yàn)闃? 若若e為橋，則為橋，則G*中與中與e對(duì)應(yīng)的邊對(duì)應(yīng)的邊e*為環(huán)為環(huán).同構(gòu)的平面圖的對(duì)偶圖不一定同構(gòu)同構(gòu)的平面圖的對(duì)偶圖不一定同構(gòu). 上頁(yè)兩個(gè)平面圖同構(gòu)上頁(yè)兩個(gè)平面圖同構(gòu), 它們的對(duì)偶圖不同構(gòu)它