流 & 割 & 路

路径的经过就是割

Posted by Ghastlcon on October 16, 2017
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 流 & 割 & 路

最大流 $f$

很熟悉吧。

最小割 $c$

也很熟悉吧。

最大最小定理这里就不证了。

最短路 $p$

这里指的是对偶图的最短路。

只有平面图才会有对偶图。

平面图的认识是非常感性的:如果能够把这个图“摊开”,使得所有的边都互不交叉,那么这个图就叫做平面图。


对偶图?

把原图的面看成点就得到了对偶图。

例子

很神奇吧。

如果让对偶图的边权等于原图的对应边权,那么平面图最小割等于对偶图最短路。

至于为什么,感性认识就好了。

结合最大最小定理 $f=c$,得

路径的经过就是割!


给定平面图,如何计算其对偶图?

很遗憾,并没有好的方法。

所以这种技巧仅能用在“已知图的形态”下,详情见模板题 BZOJ 1001



如果本文帮助到了你,希望你能撰写评论,非常感谢 $\text{w}$