16

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

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

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

在第一个示例中，我们看到b、和都从彼此接收值。因此它们将始终包含相同的值，我们可以合并它们。cdea

有向图 A 有向图 B

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

有向图 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)]

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

4

3 回答 3

6

Brendan McKay 的 nauty ( http://cs.anu.edu.au/~bdm/nauty/ ) 是我所知道的用于计算图的自同构的最佳工具。计算图的整个自同构组可能过于昂贵，但您也许可以重用 McKay 的论文“Practical Graph Isomorphism”（从 nauty 页面链接）中描述的一些算法。

于 2011-02-17T20:09:27.370 回答
0

如果其他人有兴趣，我将根据 userOVER9000 的建议添加一个额外的答案。下面是通过该工具nauty在示例 2上使用的示例。dreadnaut

$ ./dreadnaut 
Dreadnaut version 2.4 (64 bits).
> n=8 d g                                     -- Starting a new 8-node digraph
 0 : 1 3 4;                                   -- Entering edge data
 1 : 0 2 5;
 2 : 3 1 6;
 3 : 0 2 7;
 4 : 0;
 5 : 1;
 6 : 2;
 7 : 3;
> cx                                          -- Calling nauty
(1 3)(5 7)
level 2:  6 orbits; 5 fixed; index 2
(0 1)(2 3)(4 5)(6 7)
level 1:  2 orbits; 4 fixed; index 4
2 orbits; grpsize=8; 2 gens; 6 nodes; maxlev=3
tctotal=8; canupdates=1; cpu time = 0.00 seconds
> o                                           -- Output "orbits"
 0:3; 4:7;

请注意，它建议加入示例 2 中的0:3节点和.a:d4:7e:h

该nauty算法没有很好的文档记录，但作者将其描述为指数最坏情况，n^2平均。

于 2011-02-18T16:48:49.967 回答
0

计算对称性似乎是一个二阶问题。在第二张图中只取 a、b、c 和 d，必须表达对称性

a(b,c,d) = b(a,d,c)

以及它的所有排列，或者一些这样的排列。考虑添加到它的第二个子图 a', b', c', d'。同样，我们有对称性，但参数化不同。

对于计算人员（而不是数学人员），我们可以这样表达问题吗？

每个图形节点都包含一组字母。在每次迭代中，每个节点中的所有字母都通过箭头复制到其邻居（有些箭头需要多次迭代，可以视为匿名节点的管道）。

我们试图找到有效的方法来确定诸如 * N 次迭代后每个集合/节点包含哪些字母。* 对于每个节点，N 之后其集合不再更改。* 哪些节点集最终包含相同的字母集（等价类）

?

于 2012-05-20T05:45:59.963 回答