图算法检测偶数周期

我有一个无向图。该图中的一条边是特殊的。我想查找包含第一条边的偶数循环的所有其他边。图算法检测偶数周期

我不需要列举所有的周期，这本质上是NP我认为。我只需要知道每个边缘是否满足上述条件。

一个蛮力搜索当然是有效的，但速度太慢了，我正在努力想出更好的东西。任何帮助赞赏。

2012-08-26 john

这里没有足够的信息来提供你正在寻找的质量的答案。提前多久知道哪个边缘特殊？你允许预处理数据吗？您事先接触了多少数据（例如，加载它），您是否可以修改预处理数据的方式？ – ninjagecko

此外，如果不能滥用预处理，您可能需要查看所有循环**，尽管我无法以这种或那种方式考虑该断言的证明。 – ninjagecko

@ninjagecko该图表示化学结构，即顶点是原子，边是这些原子之间的化学键。用户不断编辑化学结构，并且该算法预计随着用户执行编辑而实时运行。尽管我们也保留了一些其他结构（例如我们始终知道边是否是周期的一部分），但我们使用图的简单邻接表结构。如果我理解你的话，预处理不是一种选择，因为图形（和特殊边缘）总是在变化。 – john

我想我们有一个答案（我必须相信我的同事的想法）。基本上他的想法是在偶数周期的空间内完成洪水填充算法。这是有效的，因为如果您通过合并两个较小的周期形成较大的偶数周期，那么较小的周期必须均为偶数或双方都是奇数。类似地，合并奇数和偶数循环总是形成更大的奇数循环。

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

来源

2012-08-30 08:47:43 john

-1

如果你的图有一个小节点度，你可以考虑使用不同的图形表示：

让三个原子u,v,w和两个化学键e=(u,v)和k=(v,w)。表示此类数据的典型方法是将u,v,w作为节点存储，e,k作为图的边。

然而，一个可能代表e和k如在图中的节点，具有像f=(e,k)边缘其中f表示从u到w，f=(e,k)或f=(u,v,w)一个两步骤链路。运行任何算法以查找这样的图上的周期将返回原始图上的所有偶数周期。

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

来源

2013-03-14 23:53:38 michai

图算法检测偶数周期

回答

相关问题