平面图和对偶图

平面图：每条边交点都是顶点的图
如下图，左边的是平面图，右边则不是
image

对偶图:对于平面图分出来的每个相邻平面连边建出来的图。
如下图红色部分是黑色部分的对偶图。
image

请问这个有什么用呢？
很显然原图的最小割可以转化为新图的最短路。
习题：https://www.luogu.com.cn/problem/P4001

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Xxhdjr/p/14940945.html