algorithm - 从图形中消除对称性

Question

我有一个算法问题，我在其中导出了很多状态之间的转移矩阵。下一步是对它求幂，但它非常大，所以我需要对它做一些缩减。具体来说，它包含很多对称性。下面是一些关于通过简单观察可以消除多少节点的示例。

我的问题是是否有一种算法可以有效地消除有向图中的对称性，类似于我在下面手动完成的方式。

在所有情况下，所有节点的初始向量都具有相同的值。

---

在第一个例子中我们看到 b , c , d和 e都从 a 接收值和彼此之一。因此它们将始终包含相同的值，我们可以合并它们。

---

在此示例中，我们很快发现，从 a 的角度来看，该图是相同的, b , c和 d .同样对于它们各自的侧节点，它附加到哪个内部节点并不重要。因此，我们可以将图形减少到只有两个状态。

---

更新:有些人很合理，不太清楚“状态转移矩阵”是什么意思。这里的想法是，您可以将一个组合问题拆分为多个状态类型，每个 n在你的复发中。然后矩阵告诉你如何从n-1得到至 n .

通常你只对你的一个状态的值感兴趣，但你也需要计算其他状态，这样你总能进入下一个级别。然而，在某些情况下，多个状态是对称的，这意味着它们将始终具有相同的值。显然，将这​​些都计算出来是相当浪费的，所以我们希望缩小图，直到所有节点都“唯一”。

下面是示例 1 中简化图的传输矩阵示例。

[S_a(n)]   [1  1  1] [S_a(n-1)]
[S_f(n)] = [1  0  0]*[S_f(n-1)]
[S_B(n)]   [4  0  1] [S_B(n-1)]

---

如有任何建议或对论文的引用，我们将不胜感激。

Answer 1

Brendan McKay 的 nauty ( http://cs.anu.edu.au/~bdm/nauty/ ) 是我所知道的计算图自同构的最佳工具。计算图的整个自同构群可能成本太高，但您可以重用 McKay 的论文“实用图同构”(从 nauty 页面链接)中描述的一些算法。