我正在处理优化问题，需要列出无向图的所有可能切割。具体来说，我有兴趣找到在两个顶点子集中断开图形的所有边子集。
详细说明:
在无向图 G(V,E) 中，其中 V 是顶点集，E 是边集。切割形成两个顶点子集 A 和 B，使得:
A 联合 B= V
和
A 交集 B=空集
A 和 B 建立 C(E 的子集)，使得 C 中的每条边连接两个顶点，一个在 A 中，一个在 B 中。我有兴趣找到所有可能的子集 C，这样:对于每个 C，它是一个没有切割 C' 的图形切割使得 C' 是 C 的子集。
非常感谢您的帮助。谢谢。
最佳答案
这是我想到的一个算法。它可能不是最有效的，但它会返回正确的结果。
想法是从一个顶点开始扩展一个区域，然后找到分隔该区域的切割。
为此，如果任何区域已经被检查过，我们将需要一个结构。一个简单的位图似乎适合这个。由于您最多使用 10 个顶点，因此 16 位或 32 位整数是合适的。您可以通过将引用包含的顶点的位设置为 1 来计算区域的索引。如果将所有检查过的区域索引放在哈希集中，您可以找出是否有任何区域(或其补码)在 O 中检查过(1).
所以从任何顶点开始(这将形成第一个区域)。将其区域索引放入哈希集中。入射到该顶点的所有边将形成第一个切割。通过任何相邻顶点增加区域。可以通过与现有索引进行 ORing 来增量计算区域索引。第二个切割将由从该区域中任何两个顶点开始并在其他地方结束的所有边形成。遍历整个图以找到所有可能的区域(在 BFS 或 DFS 中)。在进一步检查一个区域之前，请检查它或其补体是否已经被检查过。然后你可以打破。如果你对每个顶点都这样做，你会找到所有可能的切割。
在报告切割之前，您需要检查该区域的补码是否仍然连接。
关于algorithm - 查找无向图的所有可能切割，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31503279/