关于平面图到对偶图的转化

大家好，又见面了，我是你们的朋友全栈君。

闲话

哇对偶图真的是个好东西， 昨天考NOI2010的时候前两道很快做完了， 看着t3发呆了1个多小时， 啥也想不出来. 看着网格图突然想到听说bzoj1001狼抓兔子可以用对偶图求解. 对偶图是啥我也不知道， 听说把面看成点， 连边后跑一边最短路就可以了. 但是当时想到这个突然发现自己不会建对偶图， 看时间还有一个多小时， 于是建了8种可能的图， 每一个都跑一遍spfa， 发现有一个可以过样例， 手动模拟一下觉得这种建图没错， 就交上去了. 没想到居然还对了， 哈哈NOI2010我居然290(spfa被卡了一个点)， 心中狂喜， 但是一想到t1做过， t3蒙对也就不敢说什么了， 而且这是10年的题了， 时代在进步啊…

什么是平面图?

平面图的定义就是所有的边只在顶点处相交， 这里就是一个例子.

这里写图片描述

你看， 边与边之间没有相交吧~. 其实这是论文PPT的图， 本人画的太丑就不挂出来了.

So…对偶图?

对于每一个平面图， 都有与其相对应的对偶图. 我们假设上面的例图是图G， 与其对应的对偶图G*， 那么对于G*来说， G*上面的每一个点， 对应的是G里面的每一个面. 比如说下面就是G*.

这里写图片描述

上面的点就是对偶图G里的点. 那么关于对偶图G*里的边呢 ? 对于G中本来的每条边e， 他是两个面(比如说面f1和f2)的交边， 那么在对偶图里， 我们对这两个面(f1， f2)所映射在G*里的点连线(f1* 连向f2*). 如果f1 == f2(比如说G中5， 6这条边， 边的两侧都是同一个面， 那我们就建一条回边. 图就长这样(回边在5， 6那里).

这里写图片描述

这个就是对偶图了.

平面图与对偶图之间的关系

1.G*中的环与G中的割一一对应.(割就是一些边， 如果割掉这些边使图分成两个互不连通的子图的话， 就称之为割). 举例: 1*-2*-3*-4*这个G*里的环， 对应的是G中1-3， 2-3， 3-4， 3-5这个割. TIPS:这个性质对于平面图的最小割有巨大的作用.

2.G的面数等于G*的点数， G与G*的边数相同.

The END

希望能对大家有所帮助. 平面图转对偶图在平面图网络流问题里面作用巨大. 最小割转对偶图最短路问题解法:Click Here.

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/141132.html原文链接：https://javaforall.cn