我有一个算法问题，在这个问题中，我导出了许多状态之间的转移矩阵。下一步是指数化它，但是它非常大，所以我需要对它做一些缩减。特别是它包含了很多对称性。下面是一些简单观测可以消除多少节点的示例。
我的问题是是否有一种算法可以有效地消除有向图中的对称性，就像我在下面手动完成的那样。
在所有情况下，初始向量对于所有节点都具有相同的值。
在第一个示例中，我们看到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)]
如有任何建议或论文参考，我们将不胜感激。
最佳答案
brendan mckay的nauty（http://cs.anu.edu.au/~bdm/nauty/）是计算图的自同构的最好工具。计算图的整个自同构组可能太昂贵，但是您可以重用McKay论文“实用图同构”（链接自Nauty页）中描述的一些算法。
关于algorithm - 从图中消除对称性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5033846/