对偶图duiou tu

与平面图相伴的一种图.对于给定平面图G=〈V,E〉，设G的面为F₁,F₂…，F_k，当图G^*满足如下条件时，则图G^*＝〈V^*,E^*〉称为G的对偶图：
❶对G的每个面F_i，内部任选一点v^*_i∈V^*;

❷对F_i,F_j的每一条公共边界e_l,v_i^*与v_j^*间有一条边e_l^*，并且e_l^*与e_l交于一点；

❸当且仅当e_l仅是一个面F_i的边界时，vi^*有一个环（自回路）,e_i^*与e_l相交.
例如，下面用虚线及实心圆点表示的图是用实线及空心圆点表示的图的对偶图.

设G^*是G的对偶图，则G和G^*有相同数目的边，而G的面数等于G^*的点数，G的点数等于G^*的面数；并且，G恰为G^*的对偶图，即G,G^*互为对偶图.
易知，连通平面图的对偶图也是平面图.
这样，平面图的面着色问题（相邻的面着不同颜色）可以转换成它的对偶图的点着色的问题了（相邻的点着不同颜色）.