我要投搞

标签云

收藏小站

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

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

二分图最大独立集问题

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

  首先看定义:最大独立集:在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值二分图最大独立集=定点数-最大匹配数;如果有边1-2,2-3,3-4,那最大匹配数不就是3了吗,,那...

  首先看定义:最大独立集:在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值

  如果有边1-2,2-3,3-4,那最大匹配数不就是3了吗,,那最大独立集=4-3=1;

  可是很明显1和3组成的独立集就有2个啊,不止1.。。请问是不是我哪里理解错了??

  。。。假如有这样一个题,已知图有4个点,有边1-2,2-3,3-4,求在此图中选出m个点,是这m个点两两之间没有边,求m最大值。。请问这个怎么做?? 。。

  今天我又看了一下,,发现自己确实没有理解透彻。。如果要建图就需1-2,2-1,2-3,3-2,3-4,4-3,求最大匹配后是4然后顶点数4-42=2,得到正确解。。之前错误原因是将二分图和普通连接矩阵弄混了,如果要用公式顶点数-最大匹配数就要把矩阵装换为二分图才行。否则要除以2.。展开我来答

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

  2010-08-18展开全部最大独立集=8-3=5.你看清定义(注意这是二分图)。

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