我有一个无向图。该图中的一条边是特殊的。我想找到属于包含第一条边的偶数循环的所有其他边。
我不需要列举所有的周期，我认为这本质上是 NP。我只需要知道，对于每条边，它是否满足上述条件。
蛮力搜索当然可以，但是太慢了，我正在努力想出更好的方法。任何帮助表示赞赏。
问问题
1272 次
2 回答
1
我想我们有一个答案（我必须把这个想法归功于我的同事）。本质上，他的想法是通过偶数周期的空间进行洪水填充算法。这是有效的，因为如果您通过合并两个较小的循环形成一个大的偶数循环，那么较小的循环必须都是偶数或都是奇数。类似地，合并一个奇数和偶数循环总是形成一个更大的奇数循环。
这是一个实用的选择，只是因为我可以想象由偶数和奇数交替循环组成的病理病例。在这种情况下，我们永远不会找到两个相邻的偶数循环，因此算法会很慢。但我相信这种情况不会出现在真正的化学中。至少在目前已知的化学领域，30 年前我们从未听说过富勒烯。
于 2012-08-30T08:47:43.267 回答
-1
如果您的图的节点度数较小，您可以考虑使用不同的图表示：
设三个原子u,v,w和两个化学键e=(u,v)和k=(v,w)。表示此类数据的典型方式是在图中存储u,v,w为节点和e,k边。
但是，可以将e和表示k为图中的节点，具有像f=(e,k)wheref表示从u到w或的 2 步链接f=(e,k)的边f=(u,v,w)。运行任何算法以在此类图上查找循环将返回原始图上的所有偶数循环。
当然，这只有在原始图的节点度数较小时才有效。当用户执行编辑时，您可以轻松地相应地编辑替代表示。
于 2013-03-14T23:53:38.003 回答