我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:爱彩网 > 二分图 >

二分图的最大独立集能否用黑白染色做求反例。

归档日期:06-27       文本归类:二分图      文章编辑:爱尚语录

  求二分图的最大独立集,一般的算法是点数减去最大匹配数。现在我有下面这个算法,我觉得是对的,但是一些题目交上去会WA,求反例。我的算法:对于每个联通块进行黑白染色,然后把max(...

  求二分图的最大独立集,一般的算法是点数减去最大匹配数。现在我有下面这个算法,我觉得是对的,但是一些题目交上去会WA,求反例。 我的算法: 对于每个联通块进行黑白染色,然后把max(黑点,白点)加进答案。

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  这个二分图只有唯一的染色方法,最大独立集是4(下面4个)但黑白均只有3个点。(最大匹配此时就是2)

本文链接:http://pikeducation.com/erfentu/425.html