7

我有一个未加权的无向连通图。通常，它是一种具有许多并排循环的化合物。这个问题在这个领域很常见，就像标题所说的那样。好的算法是霍顿的算法。但是，我似乎没有一步一步地找到有关该算法的任何确切信息。

显然我的问题是，在图中找到最小循环的算法，但不幸的是，该站点的链接被禁用。我只找到了 Figueras 算法的 python 代码，但 Figuearas 并非在所有情况下都有效。有时它不会找到所有的环。问题与此类似，Find all chordless cycles in an undirected graph，我尝试过，但不适用于像我这样的更复杂的图。我找到了 4-5 个所需信息的来源，但根本没有完全解释算法。

我似乎没有找到任何 SSSR 算法，尽管它似乎是一个常见问题，主要是在化学领域。

4

1 回答 1

8

Horton 的算法非常简单。我会为你的用例描述它。

  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实际上不是步骤 1 中生成的循环之一。

淘汰过程如下：

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

所以这组循环是依赖的（不要保留最后一行）。

于 2015-08-18T14:16:23.490 回答