0

これはよく研究された問題でなければなりませんが、私はそれを研究するのに苦労しています。

ここから始めましたが、研究して実装するアルゴリズムを探しています。 http://en.wikipedia.org/wiki/Graph_isomorphism_problem

たとえば、これらの DAG (Directe Acyclic Graphs) が 2 つある場合、そのうちの 1 つをマークまたは削除する必要があります。これは、最初の DAG の回転/反射にすぎないためです。同じ自己同形グループに属しているということは、それらを回転/反射して、まったく同じ隣接行列を持つことができるということですか?

ここに画像の説明を入力

4

1 に答える 1

1

この問題を計算するには、naty または saucy アルゴリズムを使用できます。

このリンクは役に立つかもしれません。:)

Nauty:
http://cs.anu.edu.au/~bdm/nauty/
http://cs.anu.edu.au/~bdm/nauty/

Saucy:
http://vlsicad.eecs.umich.edu/BK/SAUCY/

生意気なページには、利用可能な既製のツールのリストもあります（特にLinuxベースのOSのコマンドライン用）。

于 2015-03-31T19:04:51.147 に答える