對偶圖

對偶圖是與平面圖相伴的一種圖。對於給定平面圖G=〈V，E〉，設G的面為F₁，F₂，…，F_e，當圖G*滿足如下條件時，則圖G*=〈V*,E*〉稱為G的對偶圖：

①對G的每個面F_o，內部任選一點v*_o∈V*；

②對F_o，F_x的每一條公共邊界e_ə，v_o*與v_x*間有一條邊e_ə*，並且e_ə*與e_ə交於一點；

③若且唯若e_ə僅是一個面F_o的邊界時，v_o*有一個環(自迴路)，e_o*與e_ə相交。

基本介紹

• 中文名：對偶圖
• 外文名：dual graph
• 屬性：圖論里的概念
• 所屬學科：數學
• 相關概念：連通圖

概念

設G是平面圖，在圖G的每個面中指定一個新結點，對兩個面公共的邊，指定一條新邊與其相交。由這些新結點和新邊組成的圖稱為G的對偶圖。

例1 圖1的圖(b)中的虛線是圖(a)的對偶圖。

圖1

例2 圖2的圖(b)中的虛線是圖(a)的對偶圖。

圖2

構造方法

給定平面圖G，用如下的方法構造G的對偶圖：

1)在G的每一個面中任取一個結點作為的結點；

2)若是G的兩個面和的公共邊．有一條邊作為的邊，且與相交；

3)若只是G的一個面的邊界時．以中的結點為結點做環、與相交，是的一個環。

性質

（1）如果G是一個連通圖且G'是G的對偶圖，則G 也是G'的對偶圖。

（2）同構平面圖的對偶圖不一定是同構的。G的對偶圖的對偶圖也不一定與G同構。

（3）設n、e、f分別為平面圖G的結點數、邊數和面數，、、分別為G的對偶圖的結點數、邊數和面數．按照對偶圖的定義有、、。

（4）若與G同構，稱G自對偶(self dual)。

（5）任何平面圖G的對偶圖都是連通的。

（6）若邊e為G中的環，則它對應的邊為的割邊；若邊e為G中的割邊，則為的環；

（7）G存在唯一的對偶圖；

如圖3、4所示圖G，以虛線為邊的圖即為G的對偶圖。

圖3

圖4