Open Kewth opened 4 years ago
https://kewth.github.io/2019/10/01/%E6%9C%80%E9%95%BF%E5%8F%8D%E9%93%BE%E9%95%BF/
基本概念首先得知道链和反链是什么。在 有向无环图（ DAG ） 中，链是满足任意两点 x, y 要么 x 可以到达 y 要么 y 可以到达 x 的点集 （即使只有一个点），反链是任意两点没有路径的 点集 。那么最长反链，就是点的个数最多的反链。定理不加证明地丢出两个定理： 最长反链长度 = 最小链覆盖（用最少的链覆盖所有顶点） 最长链长度 = 最小反链覆盖（用最少的反链覆盖所有顶点）
https://kewth.github.io/2019/10/01/%E6%9C%80%E9%95%BF%E5%8F%8D%E9%93%BE%E9%95%BF/
基本概念首先得知道链和反链是什么。在 有向无环图（ DAG ） 中，链是满足任意两点 x, y 要么 x 可以到达 y 要么 y 可以到达 x 的点集 （即使只有一个点），反链是任意两点没有路径的 点集 。那么最长反链，就是点的个数最多的反链。定理不加证明地丢出两个定理： 最长反链长度 = 最小链覆盖（用最少的链覆盖所有顶点） 最长链长度 = 最小反链覆盖（用最少的反链覆盖所有顶点）