0

Ulmann および VF2 アルゴリズムを使用するのはいつですか? グラフ理論でこれらのアルゴリズムを使用する目的は何ですか?

メイン Graph 内のサブグラフを記述するために使用されますか?

4

1 に答える 1

0

これらのアルゴリズムは、 graph-isomorphismとsubgraph-isomorphismの両方に役立ちます。

グラフG=(V,E)と別のグラフG'=(V',E')があるとします。

G = G' の場合(これは、 G'内のGのすべての頂点とエッジの間に相関関係があることを意味します)、グラフ同形問題が存在します。

G > G' の場合(これは、 G'内のGのサブグラフのすべての頂点とエッジの間に相関関係があることを意味します)、サブグラフ同型問題が存在します。

VF2 はUllmann よりも高速であることが知られています。

ここにそれらを描いた学術論文があります：

  • ウルマン

  • [VF2]:http://59.108.48.5/intro/leizou/teaching/2012-autumn/papers/part2/VF2%20A%20(sub)Graph%20Isomorphism%20Algorithm%20For%20Matching%20Large%20Graphs.pdf

于 2014-01-31T18:20:13.030 に答える