用于检测偶数周期的图算法

Question

我有一个无向图.该图中的一个边缘是特殊的.我想找到包含第一条边的均匀循环的所有其他边.

我不需要列举所有周期,我认为这本身就是NP.我只需知道每个边缘是否满足上述条件.

蛮力搜索当然有效,但速度太慢,我正在努力想出更好的东西.任何帮助赞赏.

Answer 1

我想我们已经找到答案了（这个想法必须归功于我的同事）。本质上，他的想法是通过偶数循环的空间进行洪水填充算法。这是有效的，因为如果您有一个通过合并两个较小循环而形成的大偶数循环，那么较小的循环必须都是偶数或都是奇数。类似地，合并奇数循环和偶数循环总是形成更大的奇数循环。

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