Gomory-Hu Tree学习笔记

9AC8E2 · 2020-09-24 19:17:14 · 个人记录

关于Gomory-Hu Tree

Gomory-Hu Tree就是最小割树,用来解决无向图任意两点间最小割.不过,Gomory-Hu Tree只能得到最小割的大小,并不能得到方案

Gomory-Hu Tree上两点 s,t 之间的最小边权,就是原图中s,t 之间的最小割

给定一个无向联通图,边有边权,每条边被割断的代价就是它的边权.给定两个点 s,t ,求使得 s,t 不联通的最小代价

与有向图最小割相似,无向图最小割也可以用最大流求解.具体的说,对一条无向边建两条方向相反的边显然不会影响答案,因为相反边的流量可以看作当前边的负流量,两条边任意时刻显然只会有一条边有流量.

但是如果询问次数较多,这个方法显然不是很优秀.这个时候就需要Gomory-Hu Tree.

考虑分治.

每次在当前点集中随便选两个点 s,t,暴力计算关于 s,t 的最小割,在Gomory-Hu Tree上连一条连接 s,t,边权为最小割大小的边,对与 s,t 联通的点集分别递归继续操作

$V_s$ 表示按最小割分割后与 $s$ 联通的点的点集 $Meg_{u,v}$ 表示Gomory-Hu Tree上 $u,v$ 两点间边权的最小值 # 一条引理 >$\forall u\in V_s,v\in V_t$,有$Cut_{u,v}\leq Cut_{s,t}

十分显然,如果用 Cut_{s,t} 的代价不能使 u,v 不连通,同时 u 与 s 联通,v 与 t 联通,那么显然 s 与t联通

对于一个点对 u,v,考虑在构造Gomory-Hu Tree的每一次分治过程中,如果 u,v 在选择的点对 s,t 的两侧,都有Cut_{u,v}\leq Cut_{s,t}

那么必然有 Cut_{u,v}\leq Meg_{u,v}

对于任意三点 a,b,c,必然有 Cut_{a,b}\geq\min\{Cut_{a,c},Cut_{b,c}\}

考虑 Cut_{a,b},Cut_{a,c},Cut_{b,c} 中最小的一对,不妨设它为 Cut_{a,b}

再考虑割掉关于 a,b 的最小割之后,c 与 a 联通还是与 b 联通,不妨设与 b 联通

根据之前那个引理,有 Cut_{a,b}\geq Cut_{a,c}

因为钦点了 Cut_{a,b} 是最小的,又有 Cut_{a,b}\leq Cut_{a,c}

所以 Cut_{a,b}=Cut_{a,c}

那么在 Cut_{a,b},Cut_{a,c},Cut_{b,c} 中一定有两个较小值,一个较大值,所以引理成立

将 3 个点的情况推广到任意多个点,那么有 Cut_{a,b}\geq \min\{Cut_{a,w_1},Cut_{w_1,w_2}...Cut_{w_k,b}\}

如果把这个结论放在Gomory-Hu Tree上,那么又有 Cut_{u,v}\geq Meg_{u,v}

结合以上两条引理,那么有 Cut_{u,v}=Meg_{u,v}

对于一个 n 个点的无向图,最多只有 n-1 种值不同的最小割

很多地方的题解都认为这条定理是在证明Gomory-Hu Tree中必要的.但是根据以上构造过程以及两条引理,我们并没有使用这条定理.倒不如说,通过Gomory-Hu Tree证明这条定理是非常显然的.

在这里