对偶图_数学术语 - 线报百科mbji.cn

对偶图

数学术语

对偶图是与平面图相伴的一种图。对于给定平面图G=〈V，E〉，设G的面为F1，F2，…，Fe，当图G*满足如下条件时，则图G*=〈V*,E*〉称为G的对偶图：

概念

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

例1 图1的图(b)中的虚线是图(a)的对偶图。

例2 图2的图(b)中的虚线是图(a)的对偶图。

构造方法

给定平面图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的对偶图。

参考资料

最新修订时间：2022-09-24 10:38

条目作者

概述

概念

构造方法

性质

参考资料