最小割树学习笔记

发现自己完全不会最小割树,于是来学一学.

概念

一张 $n$ 个点的图上,两点之间只存在 $n-1$ 种本质不同的最小割.

可以构造出一棵带边权的树,满足树上两点的最小割 (即两点路径上最小边权) 等于原图上两点最小割.

这样的树称为最小割树,也称 Gomory-Hu Tree .

构造方法

先任意选取两个节点 $u,v​$ ,求出它们的最小割 ${\rm cut}(u,v)​$ ,跑最大流时,满流的边就对应最小割中割掉的边.

通过这组割,可以把图划分成两个部分, $u$ 所在的点集记作 $U$ , $v$ 所在的点集记作 $V$ .

对于任意 $x\in U,y\in V​$ ,有 ${\rm cut}(x,y)\le {\rm cut}(u,v)​$ .

否则用 ${\rm cut}(u,v)​$ 的花费一定无法割开 $x,y​$ ,也就割不开 $u,v​$ ,就矛盾了.

在最小割树上新建一条边 $(u,v)$ ,边权为 ${\rm cut}(u,v)$ ,然后对点集 $U,V$ 内的点分别递归执行以上算法.

最后恰好计算了 $n-1$ 次最小割,也建出了最小割树.

考虑树上路径 $x\to y$ 经过的每条边 $u\to v$ .

那么在建出 $u\to v$ 这条边时, $x,y$ 被分入了不同集合,有 ${\rm cut}(x,y)\le {\rm cut}(u,v)$ .

简单归纳就可以得到这样的构造满足了概念中的性质,即,树上两点路径上最小边权等于原图上两点最小割.

那么我们只做了 $O(n)$ 次最小割,就可以支持询问任意两点之间的最小割了.