对偶图

设G是平面图，在图G的每个面中指定一个新结点，对两个面公共的边，指定一条新边与其相交。由这些新结点和新边组成的图称为G的对偶图。^[2]

例1 图1的图(b)中的虚线是图(a)的对偶图。^[3]

图1

例2 图2的图(b)中的虚线是图(a)的对偶图。^[3]

图2

给定平面图G，用如下的方法构造G的对偶图：^[2]

1)在G的每一个面中任取一个结点作为的结点；

2)若是G的两个面和的公共边．有一条边作为的边，且与相交；

3)若只是G的一个面的边界时．以中的结点为结点做环、与相交，是的一个环。

（1）如果G是一个连通图且G'是G的对偶图，则G 也是G'的对偶图。^[4]

（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