有哪些算法可用于寻找最小环集？

Question

有哪些算法可用于寻找最小环集？

7

我有一个未加权的无向连通图。一般来说，它是由许多环并排组成的化合物。这个问题在该领域很常见，称为标题所说的那样。好的算法是Horton算法。然而，我似乎找不到关于该算法的详细信息，也没有逐步说明。

明确地说，我的问题就是这个：查找图中最小环的算法，但不幸的是该网站链接已被禁用。我只找到了Figueras算法的Python代码，但在某些情况下，Figueras不能找到所有的环。这个问题类似于这个：查找无向图中所有无弦圈，我尝试过了，但对于像我这样更复杂的图形无效。我找到了4-5个必要信息源，但是该算法并没有完全解释清楚。

我似乎找不到SSSR算法，尽管它似乎是一个常见的问题，主要出现在化学领域。

- Marin Georgiev

你有谷歌过吗？看看这个调查 - 在第一篇结果中甚至有一篇开放的博士论文... - BeyelerStudios

您可能还需要重新评估您的用例。由于SSSR并不是唯一的，它通常并不是您想要的。请参见此处的讨论：http://www.ics.uci.edu/~dock/manuals/oechem/cplusprog/node127.html - dbn

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

霍顿算法非常简单。我将针对您的用例描述它。

1. 对于每个顶点 v，计算以 v 为根的广度优先搜索树。对于边 wx，满足 v、w、x 是两两不同的，并且 w 和 x 的最近公共祖先是 v，则添加一个由从 v 到 w 的路径、边 wx 和从 x 返回到 v 的路径组成的环。

2. 按大小递增的顺序对这些循环进行排序并逐个考虑它们。如果当前循环可以表示为之前考虑的循环的“异或”，则它不是基础部分。

步骤 2 中的测试是此算法中最复杂的部分。基本上，您需要编写接受的循环和候选循环作为 0-1 关联矩阵，其行由周期索引，列由边索引，然后在该矩阵上运行高斯消元，以查看它是否产生所有零行（如果是，则放弃候选循环）。

稍加努力，可以节省重复消除已接受循环的成本，但这是一种优化。

例如，如果我们有一个图形：

a---b
|  /|
| / |
|/  |
c---d

那么我们就有了一个类似下面的矩阵：

      ab  ac  bc  bd  cd
abca   1   1   1   0   0
bcdb   0   0   1   1   1
abdca  1   1   0   1   1

在这里我稍微作弊了，因为abdca实际上不是第一步生成的循环之一。

消除过程如下：

ab  ac  bc  bd  cd
 1   1   1   0   0
 0   0   1   1   1
 1   1   0   1   1

row[2] ^= row[0];

ab  ac  bc  bd  cd
 1   1   1   0   0
 0   0   1   1   1
 0   0   1   1   1

row[2] ^= row[1];

ab  ac  bc  bd  cd
 1   1   1   0   0
 0   0   1   1   1
 0   0   0   0   0

因此，这组循环依赖于（不保留最后一行）。