将所有循环组合在一起的算法

Question

我有很多个循环（由数字值表示，例如，1-2-3-4 对应一个循环，有4条边，边1是{1:2}，边2是{2:3}，边3是{3,4}，边4是{4,1}，以此类推）。

如果两个循环仅共享一条边，则称这两个循环相连。

例如，假设我有两个循环1-2-3-4和5-6-7-8，那么就有两个循环组，因为这两个循环没有相连。如果我有两个循环1-2-3-4和3-4-5-6，那么只有一个循环组，因为这两个循环共享同一条边。

下图可以说明我的观点：

alt text http://lh5.ggpht.com/_SDci0Pf3tzU/SuBhd07xbWI/AAAAAAAAFMs/9OlMhN8uzzQ/s640/mst.jpg

上图中的R1、R2到R7是我所说的“循环”。在上图中，只有一个包含所有R1到R7的循环组。

找到所有循环组的最有效方法是什么？

- Graviton

---

也许你应该解释一下你想要实现什么，这可能会给出为什么你称其为“循环”以及为什么它具有“边缘”的线索，以及所有这些的含义。 - Guffa

这绝对不是针对数学溢出的。据我所知，这要么是一个图算法问题，要么是一个字符串匹配问题，具体取决于输入的方式。 - IVlad

你具体是在寻找什么？循环群的数量？循环群中的边/顶点？还是每个循环群内的完整循环列表？找到完整循环列表没有高效的方法（列表可能呈指数级增长），但对于其他问题可能有相对较快的算法。 - Daniel

@John：MathOverflow专为研究级问题而设（请参阅其FAQ）。如果您不是学术人员，或者没有在研究生水平以上学习，则不应在其上提问。虽然拥有一个“适用于数学的Stack Overflow”可能很好，但MathOverflow并非如此。 - Steve Jessop

你说“循环”，但实际上你已经挑选出了平面图的（非无限）面。你的图是否是一般平面图？ - user287792

Answer 1

首先找到图中的所有环并为它们标记，例如 A、B、C 等。现在创建一个新图，其中每个在原图中找到的环都转换为新图中的单个节点。如果旧图中对应的环是“连接”的（使用您相当不寻常的连接定义），则在新图中使用一条边将这些节点连接起来。

“循环组”的数量就是新图中的连通分量的数量。

- Mark Byers

---

@感谢Mark，但有没有办法检索每个循环组内部的所有周期？ - Graviton

@Mark，此外，问题在问如何判断环是否连接，但是在您的答案中，您说我需要加入节点，可以更明确地说明吗？ - Graviton

@Ngu：我会把检测循环的部分留给其他人。要确定两个循环是否相连，计算它们共享的边数。一旦你检测到了这些循环，就可以创建一个新图G'。在你的例子中，G'将包含7个节点，每个节点代表你检测到的一个循环。将这些新节点命名为R1、R2、...、R7。如果两个循环相连，则在G'中它们之间创建一条边。例如，R1应该与R6和R7相连，R2应该与R3和R7相连，以此类推。使用维基百科上的任何标准算法计算该图的连通分量数量——答案是1。 - Mark Byers

现在更清楚了，你有关于连通分量计数的维基百科参考资料吗？可以分享一下吗？ - Graviton

@Ngu Soon Hui：http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29#Algorithms - Mark Byers

Answer 2

我相信这不是最有效的方法，但这将是我的初始尝试：

首先交换边缘和顶点：所以对于你的例子循环 1-2-3-4，3-4-5-6 和 5-6-7-8，你需要：

"12" => "A"
"23" => "B"
"34" => "C"
"45" => "D"
"56" => "E"
"67" => "F"
"78" => "G"
"41" => "H"
"63" => "I"
"85" => "J"

这将给你最多(v*(v-1))/2个顶点，但好吧 - 对于O(v^2)算法来说可能仍然足够好。

然后将循环表示为位域： "1-2-3-4" 变成 ABCH

ABCDEFGHIJ
1110000100

并且“3-4-5-6”变成了CDEI

ABCDEFGHIJ
0011100010 

所以它们只有一个共同的比特，这意味着在原始图中，它们只有一条公共边。可以通过 O(v^2) 的逐位检查或二分搜索(首先通过 AND 操作进行检查，如果它们有任何共同的比特，则检查前半部分比特的 AND 操作等)来进行检查。

- Chris Lercher

---

不要认为你的解决方案可行，如果两个不直接连接但仍属于同一循环组的周期呢？ - Graviton

@Ngu：我的意图是先测试两个周期，如果它们连接在一起，就将它们合并成一个（合并可以通过OR操作轻松完成）。然后继续下一个周期。我希望我正确理解了分组的概念，因为它在这里被使用！ - Chris Lercher

如果您想提高性能，您也可以尝试通过AND运算测试三个或四个周期，以一次测试多个周期（取决于这些周期是否可能在同一组中，您可以通过这种方式调整性能）。然后，如果匹配发生，则仅针对周期对进行“深入挖掘”。甚至可以尝试从AND运算的一个周期集合开始，并递归地“挖掘”下去... - Chris Lercher