消除图形的对称性

我有一个算法问题，我在很多状态之间导出了一个传递矩阵。下一步是对它进行取幂，但它非常大，所以我需要对它进行一些减少。具体来说它包含很多对称性。下面是一些关于通过简单观察可以消除多少节点的示例。 我的问题是，是否有一种算法可以有效地消除有向图中的对称性，类似于我在下面手动完成它的方式。 在所有情况下，初始向量对于所有节点具有相同的值。 在第一个例子中，我们看到

b

，

c

，

d

和

e

都从

a

和彼此之一接收值。因此，它们将始终包含相同的值，我们可以合并它们。 在这个例子中，我们很快发现，从

a

，

b

，

c

和

d

的角度来看，图表是相同的。同样对于它们各自的侧节点，它附着在哪个内节点上也无关紧要。因此，我们可以将图形缩小到仅两个状态。 更新：有些人很合理，不太确定“国家转移矩阵”是什么意思。这里的想法是，你可以在你的重现中将组合问题分解为多个状态类型。然后矩阵告诉你如何从

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)]

任何建议或对论文的参考都表示赞赏。