基本概念

首先得知道链和反链是什么。

有向无环图( DAG ) 中,
链是满足任意两点 x, y 要么 x 可以到达 y 要么 y 可以到达 x 的点集 (即使只有一个点),
反链是任意两点没有路径的 点集

那么最长反链,就是点的个数最多的反链。

定理

不加证明地丢出两个定理:

  1. 最长反链长度 = 最小链覆盖(用最少的链覆盖所有顶点)
  2. 最长链长度 = 最小反链覆盖(用最少的反链覆盖所有顶点)

那么要求的其实是最小链覆盖。

不相交

假设最小链覆盖不会相交,怎么求出这个最小链覆盖?

把每个点 i 拆成 i1 和 i2 ,考虑建立二分图。
如果存在一条边 (x, y) ,那么就在二分图中建立 (x1, y2) 的边。
这样建立二分图之后,原图的点数 – 二分图最大匹配 = 原图的最小链覆盖
(链不相交)。

这样为什么是对的呢?
一个点也可以看作是一个链,因此可以将每个点独立来看做初始状态。
然后每次在二分图中选出一条边,就是将两条链连接成一条链,
使用的链数就减少一个。

而链不会相交,所以在二分图中选出的边也是不相交的,也就是二分图的最大匹配。

栗子

如果链可以相交呢?

举个栗子:

5 4 // 五个点四条边
1 3 // 1 连向 3
2 3 // 2 连向 3
3 4 // 3 连向 4
3 5 // 3 连向 5

这里不相交的最小链覆盖是 3 ,而实际的最小链覆盖是 2 。

观察不相交的最小链覆盖 {1-3-5, 2, 4} 与最小链覆盖 {1-3-5, 2-3-4} 。

发现由于不能相交, 1-3-5 这条链把 2-3-4 这条链切断了,
分成 2 和 4 两条链,因此比最小链覆盖多了一条链。

如果可以让 2 跨过 1-3-5 与 4 相连呢?

相交

将原图做一次 Floyd ,
之后就可以知道任意两点 x, y ,x 是否能到达 y 。

把建立二分图的方法改造了一下,只要 x 能到达 y ,
就直接连一条边 (x, y),这样就可以“跨过”其它链来连接两条链了。

这个时候,原图最长反链长度 = 最小链覆盖 = 二分图最大匹配。

分类: 问题

1 条评论

hard_to_name · 2019年4月12日 下午10:42

教我Floyd,快点

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: