查找无向图的所有可能切割
Find all possible cuts of an undirected graph
我正在处理优化问题，需要列出无向图的所有可能切割。具体来说，我有兴趣找到在两个顶点子集中断开图形的所有边子集。
详细：
在无向图 G(V,E) 中，其中 V 是顶点集，E 是边集。切割形成两个顶点子集 A 和 B，使得：
A 联合 B= V
和
A交集B=空集
A 和 B 建立 C（E 的子集），使得 C 中的每条边连接两个顶点，一个在 A 中，一个在 B 中。我有兴趣找到所有可能的子集 C，使得：对于每个 C是没有切割 C' 的图形切割，使得 C' 是 C 的子集。
非常感谢您的帮助。谢谢。
这是我想到的一个算法。它可能不是最有效的，但它会 return 正确的结果。
想法是从一个顶点开始扩展一个区域，然后找到分隔该区域的切割。
为此，如果任何区域已经被检查过，我们将需要一个结构。一个简单的位图似乎适合这个。由于您最多使用 10 个顶点，因此 16 位或 32 位整数是合适的。您可以通过将引用包含的顶点的位设置为 1 来计算区域的索引。如果将所有检查过的区域索引放在哈希集中，您可以找出是否有任何区域（或其补码）在 O 中检查过(1).
所以从任何顶点开始（这将形成第一个区域）。将其区域索引放入哈希集中。入射到该顶点的所有边将形成第一个切割。通过任何相邻顶点增加区域。可以通过与现有索引进行 ORing 来增量计算区域索引。第二个切割将由从该区域中任何两个顶点开始并在其他地方结束的所有边形成。遍历整个图以找到所有可能的区域（在 BFS 或 DFS 中）。在进一步检查一个区域之前，请检查它或其补体是否已经被检查过。然后你可以打破。如果你对每个顶点都这样做，你会发现所有可能的切割。
报割之前，您需要检查该区域的补码是否仍然连接。
听起来任何 A 和 B 都可以形成切割，只要它们不相交，即 A 不必连接，B 也类似。在那种情况下，因为你说你有 10 个或更少的顶点，如果你想要一些非常简单的东西，只需选择大小为 5 或更小（通过对称）的顶点子集的 A，并让 B 为补集，然后对于每个边测试它是否是 A 和 B 之间的边。所有这些边缘形成你的切口。存储每次切割的边集。最多会有 512 次截然不同的切割。
现在你说你想要 "minimal" 切割，即切割使得没有适当的边缘子集是切割。同样，由于您只有 512 个最大可能切割，每个边的子集的大小不超过 (10 选择 5)^2 个边，只需比较每对切割 C1、C2，使 C1 的大小小于或等于到 C2 的大小。如果您对每对切割的每个切割中的边缘进行排序，或者使用新的散列 table 对每对切割的每个切割中的边缘进行散列，这将更容易。
无论如何，关键是只有 512 次切割，每次切割不超过 (10 选择 5)^2 条边，你可以在几秒钟或更短的时间内完成这个计算（可能是几分之一第二）在一个好的现代 a CPU 上，至少如果你有一个像 java 或 c/c++ 这样的低级语言的体面的实现。
我正在处理优化问题，需要列出无向图的所有可能切割。具体来说，我有兴趣找到在两个顶点子集中断开图形的所有边子集。
详细：
在无向图 G(V,E) 中，其中 V 是顶点集，E 是边集。切割形成两个顶点子集 A 和 B，使得：
A 联合 B= V
和
A交集B=空集
A 和 B 建立 C（E 的子集），使得 C 中的每条边连接两个顶点，一个在 A 中，一个在 B 中。我有兴趣找到所有可能的子集 C，使得：对于每个 C是没有切割 C' 的图形切割，使得 C' 是 C 的子集。
非常感谢您的帮助。谢谢。
这是我想到的一个算法。它可能不是最有效的，但它会 return 正确的结果。
想法是从一个顶点开始扩展一个区域，然后找到分隔该区域的切割。
为此，如果任何区域已经被检查过，我们将需要一个结构。一个简单的位图似乎适合这个。由于您最多使用 10 个顶点，因此 16 位或 32 位整数是合适的。您可以通过将引用包含的顶点的位设置为 1 来计算区域的索引。如果将所有检查过的区域索引放在哈希集中，您可以找出是否有任何区域（或其补码）在 O 中检查过(1).
所以从任何顶点开始（这将形成第一个区域）。将其区域索引放入哈希集中。入射到该顶点的所有边将形成第一个切割。通过任何相邻顶点增加区域。可以通过与现有索引进行 ORing 来增量计算区域索引。第二个切割将由从该区域中任何两个顶点开始并在其他地方结束的所有边形成。遍历整个图以找到所有可能的区域（在 BFS 或 DFS 中）。在进一步检查一个区域之前，请检查它或其补体是否已经被检查过。然后你可以打破。如果你对每个顶点都这样做，你会发现所有可能的切割。
报割之前，您需要检查该区域的补码是否仍然连接。
听起来任何 A 和 B 都可以形成切割，只要它们不相交，即 A 不必连接，B 也类似。在那种情况下，因为你说你有 10 个或更少的顶点，如果你想要一些非常简单的东西，只需选择大小为 5 或更小（通过对称）的顶点子集的 A，并让 B 为补集，然后对于每个边测试它是否是 A 和 B 之间的边。所有这些边缘形成你的切口。存储每次切割的边集。最多会有 512 次截然不同的切割。
现在你说你想要 "minimal" 切割，即切割使得没有适当的边缘子集是切割。同样，由于您只有 512 个最大可能切割，每个边的子集的大小不超过 (10 选择 5)^2 个边，只需比较每对切割 C1、C2，使 C1 的大小小于或等于到 C2 的大小。如果您对每对切割的每个切割中的边缘进行排序，或者使用新的散列 table 对每对切割的每个切割中的边缘进行散列，这将更容易。
无论如何，关键是只有 512 次切割，每次切割不超过 (10 选择 5)^2 条边，你可以在几秒钟或更短的时间内完成这个计算（可能是几分之一第二）在一个好的现代 a CPU 上，至少如果你有一个像 java 或 c/c++ 这样的低级语言的体面的实现。