我不相信存在一种算法,可以在二分图中找到最大独立顶点集,除了通过暴力方法找到所有可能的独立集合中的最大值。
我想知道如何编写伪代码来查找所有可能的顶点集。
假设有一个具有4个蓝色顶点和4个红色顶点的二分图。目前,我会使用以下方法:
Start with an arbitrary blue,
find all red that don't match this blue
put all these red in Independent Set
find all blue that dont match these red
put these blue in Independent Set
Repeat for next vertex in blue
Repeat all over again for all blue then all vertices in red.
我明白这种方法并不能给出所有可能的独立集合组合,因为在第一步之后,我选择的是所有不匹配的下一个颜色顶点,而不是遍历每一个可能性。
例如,给定一个有匹配的图形:
B R
1 1
1 3
2 1
2 3
3 1
3 3
4 2
4 4
Start with blue 1
Choose red 2 and 4 since they dont match
Add 2, 4 to independent Set
Choose 2 and 3 from blue since they dont with 2 or 4 from red
Add 2 and 3 from blue to independent set as well.
Independent Set = 1,2,3 from blue 2,4 from red
Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set)
有没有办法改进这个算法以更好地搜索所有可能性。我知道二分图的最大集合等于红色加蓝色减最大匹配数。这个问题出现在如果一开始选择了所有可能的红色,如果它们连接到所有其他可能的蓝色,那么我的集合只有一个蓝色和其余都是红色。