Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:我的直观的理解

Posted by majia_ at 2008-10-03 20:39:25 on Problem 3692
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator