DAG 上特殊顶点集的大小

Question

在新加坡，今年 (2016) 的 NOI（全国信息学奥林匹克竞赛）包括以下问题 "ROCKCLIMBING"（我在比赛中未能解决。 ) :

删节问题陈述

给定一个有 N <= 500 个顶点的 DAG，找到原始顶点子集中的最大顶点数，使得集合中的 1 个顶点到集合中的另一个顶点没有路径同一套，直接或间接.

解决方案

解决方案是使用传递闭包算法，然后通过复制每个顶点 i 形成二分图来形成 i' 这样如果顶点 j 可以从原图中的顶点i 直接或间接，则新图中有从i到j'的有向边

然而，在解决方案演示期间，演示者没有解释新二分图的N - MCBM （MCBM 是最大基数二分匹配） 是如何或为什么也是原始 DAG 中无法相互 直接或间接 的顶点集的最大大小。

我查找了与 DAG 和二分图相关的其他问题，例如 DAG 上的最小路径覆盖问题，但我找不到任何可以解释这个问题的内容。

有谁知道证明这个等式的方法吗？

问题陈述可以在这里找到：ROCKCLIMBING

提前谢谢你。

Answer 1

这里发生了两件事：

1. 一个集合是独立的当且仅当它的补集是一个顶点覆盖（见wikipedia）。这意味着最大独立集的大小等于最小顶点覆盖的大小。

2. Konig's theorem 证明

In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

因此为了找到最大独立集的大小，我们首先计算最大匹配的大小MCBM，然后计算其补码等于N-MCBM。

Answer 2

另一种观点如下：

1. 如果我们用A<B表示我们可以从A爬到B，我们定义了一个partially ordered set

2. 有一个叫迪尔沃斯定理的结果说不可比较元素的最大数量等于链的最小数量

proof 展示了如何通过在二分图中构造最大匹配来构造最小链数。