2つのグラフ間の距離を編集する

Question

2つの文字列の間にLevenshtein距離（または編集距離）がある文字列の場合と同様に、グラフに似たものがありますか？

つまり、グラフG1をグラフG2に変換するためのアトミック演算（ノードとエッジの挿入/削除）の数を特定するスカラー指標です。

Answer 1

注：

レーベンシュタイン距離（または編集距離）は、二つの文字列

の間にある。しかし、グラフには、少なくともNの間で検索する必要があります！あなたが各エッジと頂点のアイデンティティーを見つける位置。 ユニークなインデックスで2つのグラフを簡単に比較することができますが、 マスターの質問は、各頂点とエッジのIDを定義することです。この質問（変換できる2つのグラフの各頂点とエッジの識別情報を見つける）同型問題（NP-Complete）と呼ばれる問題です。 同型グラフを検索することができます。

Answer 2

一般的なグラフの場合は、答えの中で言及されているその他のNP完全問題です。しかし、ツリーグラフにはよく知られている多項式アルゴリズムがあります。彼らの最も有名なのは1989年に出版された "張シャシャ"アルゴリズムです。

Answer 3

私はグラフ編集距離があなたが探していた尺度だと思います。

グラフ編集距離測定グラフの編集操作の最小数を別のグラフを変換するため、および許可グラフ編集操作含む：

• 挿入/は、挿入/エッジ削除
• 単離された頂点を削除
• 変更頂点/エッジのラベル（標識されたグラフ場合）

しかし、2つのグラフ間のグラフの編集距離を計算することはNP困難です。これを計算するための最も効率的なアルゴリズムは、A *ベースのアルゴリズムであり、他の準最適アルゴリズムもある。

Answer 4

あなたは紙でA survey of graph edit distance