同じノードを含む2つのグラフ間の編集距離を計算するアルゴリズムはありますか？

Question

まず、2つのグラフ間の編集距離を計算するための多くの作業があったことを知っています。しかし、GEDアルゴリズムの大部分は一般的な場合に適用される。ここで私の場合を考慮

、二つのグラフG（V1、E1）とG（V2、E2）があります。 Vkをは、k個の頂点（kは定数）、及びVkの満たす両方Vk⊆V1とVk⊆V2を含むノードのセットです。私はこれらの2つのグラフの間の編集距離を計算する際に、それらのグラフの間の対応関係を維持したいと思います。

このような状況ではアルゴリズムがありますか？誰も私のためのアドバイスを持っていない場合は、？おかげでたくさん

PS

は、viはVkの中のノードであると仮定する。私が心配しているのは、G1がG2に変換されたときにviが変わらないことです。つまり、viに操作がないことを意味します（例えば、G1からG2へのviの置換、G1におけるviの削除、G2のviの挿入） G1からG2に変換されます。

Answer 1

ユースケースがなく、数学的な形式がないため、特定の問題を解決するアルゴリズムはありません。どのように私はこれを解決するのでしょうか：

1）あなたはVkを変えずにEk（1）Ek（2）を指定するコメントでVkのノード間のエッジをEk（i）とします。その場合、Vk1/2からエッジを無視してエッジ追加/修復/置換、GED（Vk1、Vk2）を計算する2）Vi-VkiとVkiの間のエッジを無視してGED（V1-Vk1、V2-Vk2）を計算する。 、E（V2-VK2 < - > VK2） - V1・VK1はVkの内のすべてのノードを除去した後グラフV1及びVK

3）にリンクされたすべてのエッジがある場合GED（> VK1 E（V1-VK1 <）を計算）、すなわち、「V1-Vk1とVk1を結ぶエッジ」を「V2-Vk2とVk2を結ぶエッジ」に置き換えるGEDを計算する。

4）3 GEDを一緒に追加します。