找出无向图的所有可能的切口

Question

我正在研究一个优化问题，需要列出一个无向图的所有可能割集。具体来说，我感兴趣的是在两个顶点子集中找到所有断开图的边子集。

详细地：

在无向图G（V，E）中，V是顶点集，E是边集。割形成两个顶点子集a和B，这样：

A联合B=V

和

A交叉点B=空集

A和B建立C（E的子集），使得C中的每条边连接两个顶点，一个在A中，一个在B中。我感兴趣的是找到所有可能的子集C，这样：对于每一个C，它是一个图的割，没有割C，C'是C的子集。

非常感谢你的帮助。谢谢你。

Answer 1

听起来任何一个A和B都可以形成一个切口，只要它们是不相交的，也就是说，A不必连接，对B来说也是如此。在这种情况下，既然你说你有10个或更少的顶点，如果你想要一个非常简单的东西，只要从大小为5或更小的顶点子集中选择一个，让B作为补充，然后对每个边缘进行测试，看它是否是A和B之间的边缘。所有这些边缘都形成了你的切口。为每个切口存储一组边缘。最多会有512个不同的切口。

现在您说您想要“最小”切割，即切割使得没有合适的边缘子集是切割。同样，由于您只有512个最大可能的切割，每个边缘的子集大小不超过（10选择5）^2个边缘，只需比较每对切割C1、C2，使得C1的大小小于或等于C2的大小。如果您对每对切割的每个切割中的边缘进行排序，或者使用新的哈希表对每对切割的每个切割中的边缘进行散列，这将会更容易。

无论如何，关键是，只要有512次切割，每一次切割不超过（10次选择5次）^2条边，你就可以在一个好的现代CPU上用几秒钟或更短的时间（可能是几分之一秒）完成这个计算，至少如果你有一个像java或c/c这样的低级语言的不错的实现。

Answer 2

我想到了一个算法。它可能不是最有效的方法，但会返回正确的结果。

其思想是从一个顶点开始生长一个区域，并找到分割该区域的切口。

为此，我们需要一个结构，如果已经对任何地区进行了审查，该结构将保持不变。一个简单的位图似乎就可以了。由于最多使用10个顶点，因此16位或32位整数是合适的。通过将引用包含顶点的位设置为1，可以计算区域的索引。如果你把所有检查过的区域索引放在一个散列集中，你可以发现是否有任何区域（或其补码）在O（1）中检查过。

所以从任何顶点开始（这将形成第一个区域）。将其区域索引放入哈希集中。与该顶点相关的所有边将形成第一个切割。按任意相邻顶点增长该区域。通过对现有索引进行ORing，可以增量计算区域索引。第二个切割将由从该区域的两个顶点中的任何一个开始并在其他地方结束的所有边形成。遍历整个图形以找到所有可能的区域（在BFS或DFS中）。在进一步检查某个区域之前，请检查该区域或其补体是否已被检查过。然后你就可以Rest了。如果你对每个顶点都这样做，你会发现所有可能的切割。

在报告切割之前，需要检查该区域的补体是否仍然连接。