DAG上特殊顶点集的大小

Question

在新加坡，今年的国家信息学奥林匹克运动会( NOI )包括以下问题"ROCKCLIMBING" (我在比赛中未能解决)：

简化问题陈述

给定具有N <= 500顶点的DAG，在原始顶点的子集中找出顶点的最大数目，使集合中的一个顶点到同一集合中的另一个顶点没有路径，直接或间接地找到__。

溶液

解决方法是采用传递闭包算法，然后将每个顶点i复制成i'，形成二部图，使得如果顶点j可以直接或间接地从原始图中的顶点i 到达，则在新图中有一个从i到j'的有向边。

然而，在解决方案表示过程中，演示者没有解释新二分图的N - MCBM (MCBM是最大基数二分匹配)是如何或者为什么新二分图的顶点集的最大大小不能直接或间接到达原始中的。

我查找了其他与DAG和二分图相关的问题，例如DAG上的最小路径覆盖问题，但是我找不到任何解释这一点的东西。

有人知道如何证明这种平等吗？

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

提前谢谢你。

Answer 1

这里有两件事：

1. 集合是独立的当且仅当它的补码是顶点覆盖(参见维基百科 )。这意味着最大独立集的大小等于最小顶点覆盖的大小。
2. 柯尼格定理证明

在任意二部图中，最大匹配中的边数等于最小顶点覆盖中的顶点数。

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

Answer 2

另一种观点如下：

1. 如果我们用A<B来表示我们可以从A上升到B，我们已经定义了一个偏序集
2. 有一个结果叫做Dilworth定理，它说不可比较元素的最大数目等于最小链数。

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