16

多くの状態間の伝達行列を導き出したアルゴリズムの問​​題があります。次のステップはそれを累乗することですが、非常に大きいので、いくらか削減する必要があります。具体的には、多くの対称性が含まれています。以下は、単純な観察によっていくつのノードを排除できるかの例です。

私の質問は、以下で手動で行った方法と同様に、有向グラフの対称性を効率的に排除するアルゴリズムがあるかどうかです。

いずれの場合も、初期ベクトルはすべてのノードで同じ値になります。

最初の例では、b、c、dおよびeすべてが および から値を受け取ることがわかりますa。したがって、それらは常に同じ値を含み、それらをマージできます。

有向グラフA 有向グラフB

aこの例では、グラフが、b、cおよびの観点から同一であることがすぐにわかりdます。また、それぞれのサイドノードについては、それがどの内部ノードに接続されているかは問題ではありません。したがって、グラフを 2 つの状態だけに減らすことができます。

有向グラフC 有向グラフD

更新:一部の人々は、「状態転送マトリックス」の意味がよくわからないほど合理的でした。nここでの考え方は、組み合わせ問題を、再帰ごとにいくつかの状態タイプに分割できるということです。n-1行列は からへの行き方を教えてくれますn。

通常は、状態の 1 つの値だけに関心がありますが、他の状態も計算する必要があるため、いつでも次のレベルに進むことができます。ただし、場合によっては、複数の状態が対称的です。つまり、常に同じ値になります。これらすべてを計算するのは明らかに無駄なので、すべてのノードが「一意」になるまでグラフを縮小します。

以下は、例 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/）は、グラフの自己同型を計算​​するために私が知っている最高のツールです。グラフの自己同形群全体を計算するにはコストがかかりすぎる可能性がありますが、マッケイの論文「Practical GraphIsomorphism」（航海ページからリンク）で説明されているアルゴリズムの一部を再利用できる場合があります。

于 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

対称性の計算は、少し二次的な問題のようです。2番目のグラフでa、b、c、およびdだけを取得すると、対称性を表現する必要があります

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

およびそのすべての順列、またはそのようなもの。それに追加された 2 番目のサブグラフ a'、b'、c'、d' を考えてみましょう。繰り返しますが、対称性がありますが、パラメーター化が異なります。

(数学の人ではなく) コンピューティングの人にとって、問題をそのように表現できますか?

各グラフ ノードには一連の文字が含まれています。各反復で、各ノード内のすべての文字が矢印によって隣接するノードにコピーされます (一部の矢印は複数の反復を必要とし、無名ノードのパイプとして扱うことができます)。

* N 反復後に各セット/ノードに含まれる文字などを決定する効率的な方法を見つけようとしています。* 各ノードの N の後、そのセットは変更されなくなります。* どのノード セットが同じ文字セットを含むようになるか (等価クラス)

?

于 2012-05-20T05:45:59.963 に答える