DAG最小路径点覆盖

Author Avatar
洛水·锦依卫 1月 28, 2019

DAG最小路径点覆盖

问题

给出一个有向无环图 ($DAG$),求出最少使用其中多少条互不相交的路径覆盖所有点。

解法

若有 $n$ 个点,对于每个点 $i$ ,我们将它拆成两个点 $i$ 与 $i’$,分别放在一个二分图的两侧,然后,对于有向图中的每条边 $(a,b)$ 我们在二分图中将 $(a,b’)$ 这两个点连在一起。

当所有边在二分图中已经相应连好之后,我们跑二分图最大匹配,可以使用匈牙利,不过个人更倾向建立一个超级源点连向左侧每个点,建立一个超级汇点被右侧每个点所连,然后跑网络最大流。

假设最大流为 $maxflow$ ,则最小路径覆盖数为 $n-maxflow$ 。

证明

由于要求选出的每条路径都要不相交,那么对于每条路径中的点,它的入度与出度均不会大于 $1$ 。尤其对于每个起点,入度必定为 $0$ ,每个终点出度必定为 $0$ 。

那么由于 $DAG$ 中的每条边都已经放到了二分图里,对于 $DAG$ 最小路径选边的情况必定已经能够在二分图里选出来了。

接着我们考虑一下所要求的问题,显然一条路径只会有一个终点,且一个终点必定属于某条路径。而终点的出度又必定为 $0$ 。那么这样对应的选边情况放到二分图里呢?我们就会发现:

  • 对于一个点 $i$ ,它指向 $j$ 的出边必定在二分图上为 $(i,j’)$
  • 对于一个点 $i$ ,如果它的出度为 $0$ ,那么二分图上的 $i$ 必定不与任意一个 $j’$ 所匹配。
  • 选出的路径最少 $\Leftrightarrow$ 终点最少 $\Leftrightarrow$ 二分图左侧的未匹配点最少 $\Leftrightarrow$ 二分图匹配数最大

那么根据以上证明,可以得出:最少路径= 最少终点 = 总点数-最大匹配数 = $n-maxflow$ 。

证毕。