平面图转对偶图
2022/7/8 23:53:12
本文主要是介绍平面图转对偶图,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
平面图转对偶图常用于解决平面图的最小割问题。
所谓平面图,就是能够在纸上画出来任意两边不在非顶点处相交的图。
对偶图是相对于一个平面图而言的。由于平面图的性质,你可以在纸上看到一些由边围成的许多封闭的面,假如把这些面编个号,看成节点,把两个面的交边映射到两个面所代表的节点之间的连边,则由面所代表的节点构成的新图叫做原平面图的对偶图。
举个例子,下面这个无向平面图和它的对偶图:
你可能会问:0 和 17 不是在一个面,为什么算两个节点?答:为了不构成环从而不方便处理。这一招在后续的对偶图最短路中很实用。
接下来说一下怎么把平面图转对偶图。
对于无向图,按照上面的方法实现即可;对于有向图,对偶图中的方向只要边之间的相对方向是和原来相符的,你就可以自己定方向(比如下面的网格图,我们可以把以(1,1)-(n,n)对角线为分界线的右上面和左下面作为0和5,将原边顺时针旋转90°)
接下来说一下平面图转对偶图在平面(有向)图最小割中的应用。平面图按照经典算法求最小割的复杂度非常大的时候,转换为对偶图只需要求一次 O(nlogn) 的最短路即可解决。
具体来说,上图转换为平面图,将原来的边的边权对应赋给对偶图上的边权,那么原图的割对应对偶图上的一条从 s=0 到 t=5 的路径,从而只需要算出一条最短路即可。
经典题:[NOI2020]海拔。(本题须注意最小割可以蜿蜒,所以所有的边都是有用的,合起来建一张图跑 Dij)
这篇关于平面图转对偶图的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?