2 つの文字列の間にレーベンシュタイン距離 (または編集距離) がある文字列のように、グラフにも同様のものがあるのでしょうか?
つまり、グラフG1をグラフに変換するためのアトミック操作 (ノードとエッジの挿入/削除) の数を識別するスカラー メジャーですG2。
質問する
10445 次
4 に答える
21
グラフの編集距離は、あなたが探していた尺度だと思います。
グラフ編集距離は、1 つのグラフを別のグラフに変換するためのグラフ編集操作の最小数を測定します。許可されるグラフ編集操作には、次のものが含まれます。
- 孤立した頂点の挿入/削除
- エッジの挿入/削除
- 頂点/エッジのラベルを変更します (ラベル付きグラフの場合)
ただし、2 つのグラフ間のグラフ編集距離の計算は NP 困難です。これを計算するための最も効率的なアルゴリズムは A* ベースのアルゴリズムであり、他にも次善のアルゴリズムがあります。
于 2013-06-10T11:17:42.893 に答える
9
論文を見てくださいグラフ編集距離の調査
于 2013-09-14T14:00:14.367 に答える
3
ノート：
レーベンシュタイン距離 (または編集距離) は 2 つの文字列の間です
ただし、グラフでは、少なくとも N! の間で検索する必要があります。各エッジと頂点のアイデンティティを見つける位置。2 つのグラフを一意のインデックスで簡単に比較できますが、主な質問は、各頂点とエッジのアイデンティティを定義することです。この質問 (2 つのグラフで変換できる各頂点とエッジのアイデンティティを見つける) は非常に難しく、同形と呼ばれていました。問題 (NP 完全)。同型グラフについて検索できます。
于 2013-05-06T14:47:56.507 に答える