Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:我的直观的理解In Reply To:我的直观的理解 Posted by:Kevin0602 at 2008-10-03 20:35:54 本来是求最大团 V'是最大团的点集 那么V' 属于 V 且对于任意u, v属于V',都有边 那么求补,在补图中,对于任意u, v属于V',都没有边 这就是个最大独立集 最大独立集 + 最小覆盖集 = V 这是应为独立集中没边,所以边都在覆盖集中 然后最小覆盖集 = 最大匹配 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator