图算法检测偶数循环

Question

我有一个无向图。该图中的一条边是特殊的。我想找到所有其他边，这些边是包含第一条边的偶数环的一部分。

我不需要枚举所有的环，因为那本质上是NP问题。我只需要知道对于每一条边，它是否满足上述条件。

暴力搜索当然可以解决，但速度太慢，我正在努力想出更好的方法。任何帮助都将不胜感激。

- john

---

这里的信息不足以提供您所需的高质量答案。您提前多久知道哪个边缘是特殊的？您是否允许预处理数据？您在处理数据之前会涉及多少内容（例如，加载数据），并且您能否修改如何预处理数据？ - ninjagecko

此外，如果您无法滥用预处理器，可能需要查看所有循环，尽管我无法想出证明这种说法的方法。 - ninjagecko

@ninjagecko 这张图代表了一种化学结构，即顶点是原子，边缘是连接这些原子的化学键。用户正在持续编辑化学结构，并且期望该算法可以在用户执行编辑时实时运行。我们为图形使用简单的邻接表结构，尽管我们也会维护其他一些结构（例如，我们始终知道边缘是否属于一个循环）。如果我理解得正确，预处理不是一个选项，因为图形（以及特殊边缘）始终在变化。 - john

虽然我们也维护了一些其他的结构（例如，我们始终知道一条边是否是循环的一部分），但这个结构或许可以修改以跟踪它是否是偶数循环的一部分？这是什么样的结构？（预处理应该是可行的，因为用户从文件加载化学物质或者生成化学物质都是O(N)操作，但可能并不必要。） - ninjagecko

这些循环是否限于简单循环？两个三角形通过它们的顶部之间的边连接（一种沙漏形状），是否算作长度为8的循环，中间的边被使用两次？ - Chris Okasaki

Answer 1

我认为我们有了一个答案（我必须感谢我的同事提出的想法）。他的想法本质上是通过做一种洪水填充算法来穿过偶数环的空间。这个方法有效是因为如果你有一个由两个较小的环合并形成的大偶数环，那么较小的环必须都是偶数或者都是奇数。同样地，合并一个奇数环和一个偶数环总是形成一个更大的奇数环。

这只是一个实际的选择，因为我可以想象出由交替的偶数和奇数环组成的病态情况。在这种情况下，我们永远找不到相邻的偶数环，所以算法会很慢。但我相信这样的情况在真正的化学中不会出现。至少在当前已知的化学中，30年前我们从未听说过富勒烯。

- john

Answer 2

如果您的图具有较小的节点度数，您可能需要考虑使用不同的图表示方法：

假设有三个原子 u,v,w 和两个化学键 e=(u,v) 和 k=(v,w)。一种典型的表示这些数据的方式是将 u,v,w 存储为节点，并将 e,k 存储为图中的边。

然而，我们也可以将 e 和 k 表示为图中的节点，并建立像 f=(e,k) 这样的边，其中 f 表示从 u 到 w 的 2 步链接，f=(e,k) 或者 f=(u,v,w)。在这样的图上运行任何查找循环的算法都会返回原始图上的所有偶数循环。

当然，这只在原始图具有较小的节点度数时才有效率。当用户执行编辑操作时，您可以轻松地相应地编辑替代表示。

- michai