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

如果图G满足二分图条件,则可以用二分图匹配来做.最大独立集问题: (pku1466)

Posted by yuanchuanshun at 2010-07-28 20:38:12 on Problem 1466
在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值. 
如果图G满足二分图条件,则可以用二分图匹配来做.最大独立集点数 = N - 最大匹配数 

我拿网页上的测试数据看下了 ,构图可以用二分图来做,且能够验证上面的公式,
但是,上面的那句话“如果图G满足二分图条件”,如果它不满足二分图呢?能有办法构出这个二分图来吗????

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