注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

最长反链与最小链覆盖  

2012-10-19 11:52:59|  分类: 知识点 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
大前提:在有向无环图中

链是一个点的集合,这个集合中任意两个元素v、u,要么v能走到u,要么u能走到v。
反链是一个点的集合,这个集合中任意两点谁也不能走到谁。
最长反链是反链中最长的那个。

那么最长反链怎么求呢?

另一个东西叫:最小链覆盖。就是用最少的链,经过所有的点至少一次(为什么不叫最少链覆盖啊囧……)
于是啥啥定理来了:最长反链长度 = 最小链覆盖数
下面来证明:

首先,最长反链中的每个点,一定在不同的链中,所以得到:最长反链长度 ≤ 最小链覆盖数
下面关心的是,最长反链长度 ≥ 最小链覆盖数吗?
用数学归纳法。
首先空的图显然成立。
假设对于所有点数小于图G的图都成立,现在来证G也满足条件。

两个定义:源:没有一个点能走到它的点。(入度为0)  汇:不能走到任何一个点的点。(出度为0)
设:
这个图点集为V
这个图的最长反链为A
能走到A中某个点的点的集合为B,A中某个点能走到的点构成的集合为C。
(1)若A中至少有一个点既不是源也不是汇
则:
1. B ≠ V (否则反链的点全是汇)
2. C ≠ V (否则反链的点全是源)
3. B ∪ C = V:反证法,假设有一个点v既不属于B也不属于C,那么说明反链上任何一点不能到v,v也不能到反链上任何一个点,反链加上v之后能成为更长的反链,与假设矛盾。
 4. B ∩ C = A:反证法,假设有一个点v既属于B也属于C但不属于A,那么说明反链上某点a能到v,v能到反链上某点b。若a = b,则与图是有向无环图矛盾。若a ≠ b,则a能先到v,在从v到达b,与a、b都在反链上矛盾。

设B构成的子图、C构成的子图的最小链覆盖的链的集合分别为C[B]和C[C]。因为|B| < |V|,|C| < |V|,由归纳假设,C[B]、C[C]大小分别等于B构成的子图和C构成的子图的最长反链的大小。
考虑一条链c ∈ C[B],则c中必然存在一个在最长反链上的点v,不然最小链覆盖会大于最长反链,与归纳假设矛盾。因为B ∩ C = A,所以C[B]中v不能到任何一个点。所以v必为c的汇。
于是得到:A中的点都是C[B]中某条链的汇。
同理:A中的点都是C[C]中某条链的源。
又B ∪ C = V,B ∩ C = A,C[B]中某条链的汇必为C[C]中某条链的源,于是把C[B]和C[C]拼起来,就得到一个原图G的一种可行的链覆盖了!
考虑这个链覆盖,发现这个链覆盖大小 = 最长反链长度,得到最小链覆盖大小 ≤ 最长反链长度。又由前面的最小链覆盖大小 ≥ 最长反链长度,所以G中最小链覆盖大小 = 最长反链长度

(2)若A是所有源的集合或所有汇的集合 
若A是所有源的集合,那么从A中随便取一个元素v(这个可以随便找到吧)
再从V中随便找一个汇u,使得v可以到u(这个也可以随便找到吧)(u可以等于v)
然后G中去掉v、u形成图G'。则G'的最长反链大小一定小于等于|A| - 1,不然的就可以在G中找到一条不选v、u的最长反链,利用(1)的结论可以证明正确性。
由于归纳假设,则G'中一定可以找到一个数量为|A| - 1的链覆盖。再加上{v} ∪ {u}这条链,则可以在G中找到一个数量为|A|的链覆盖,所以G的最小链覆盖 ≤ 最长反链长度。
又由前面的最小链覆盖大小 ≥ 最长反链长度,所以G中最小链覆盖大小 = 最长反链长度。

证完了,这就是传说中的Dilworth定理:最小链覆盖数 = 最长反链长度
其对偶定理:最长链长度 = 最小反链覆盖数 就不证了,网上的证明烂大街了。

那么求最小链覆盖数的方法,就是首先传递闭包,然后就变成了最小路径覆盖。拆点,用二分图匹配解决之。这是后话,不说了。

应用:
NOIP 1999 导弹拦截
CTSC2008 祭祀
Topcoder SRM 557 550-point problem

参考资料:
《2008 全国信息学奥林匹克年鉴》
  评论这张
 
阅读(2843)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017