从图中消除对称性

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的论文"Practical Graph Isomorphism"(链接自nauty页面)中描述的一些算法.