最小割
2026-08-17
前置知识
最大权闭合图
在一个有向图 G=(V,E) 中,对于其一个子图 G′=(V′,E′),若 ∀(u,v)∈E′,u∈V′,v∈V′,则称 G′ 为 G 的一个闭合子图。
最大权闭合图是指所有闭合子图中,点权和最大的。
最大权闭合图的求法建图是,新建源点 S 和汇点 T,将原图中所有点权 w>0 的点用汇点连边,所有 w<0 的点连向 T,所有新建边的边权为 ∣w∣,原图的边权为 +∞,然后在新图上跑最小割,原图最大权闭合图即为所有正点权之和减去最小割容量。
显然,最小割一定是有限的,而最小割的割边与 S 相连的为不选这个点,与 T 相连的是选这个点,由于我们用所有正点权减去这个值,得到的恰好是最大权闭合图。
最大密度子图
在一个无向图 G=(V,E) 中,选择一个点集和边集(可以为空),得到 G′=(V′,E′),若 ∀(u,v)∈E′,u∈V′,v∈V′,则其密度为 V′E′。
最大密度子图就是密度最大的,满足边约束的 G 的子图。
第一种求法是,考虑将其转换为最大权闭合图,即将一条边 (u,v) 拆成三个点,两条边 (x,u),(x,v),再在新图上求最大权闭合图,这种方法点数、边数较大,不是很优。
另一种方法是,二分一个 g,则等价于最大化 ∣E′∣−g∣V′∣,也就是最小化 g∣V′∣−∣E′∣,我们发现,点集固定时边数越多越优。
