是否有一种算法可以找到有向图的所有独立集? 从我读过的内容来看,一个独立的集合代表一个由不相邻的节点形成的集合。
所以对于这个例子,我有 {1} {2} {1,3} 那么怎么可能找到所有这些,我正在考虑一些递归的东西,但我真的不知道算法,如果有人能指出我正确的方向,我将不胜感激!
谢谢!
最佳答案
寻找独立集的典型方法是考虑图的补集。图的补集被定义为具有相同的一组顶点和一对之间的边当且仅当原始图中它们之间没有边时的图。图中的一个独立集对应于补集中的一个团。找到所有派系的复杂性呈指数级增长,因此您无法提高蛮力。我仍然相信考虑图的补充可能会使问题更容易处理。
关于独立图集的算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20053345/