首先，我知道已经有很多工作来计算两个图之间的编辑距离。但大多数GED算法都适用于一般情况。
现在考虑我的情况，有两个图G(V1,E1)和G(V2,E2)。 Vk是包含k个顶点的节点集合(k为常数)，Vk同时满足Vk⊆V1和Vk ⊆V2。我想在计算这两个图之间的编辑距离时保持它们之间的对应关系。
我想知道是否有针对这种情况的算法？如果没有，有人可以给我一些建议吗？非常感谢
附注
假设vi是Vk中的一个节点。我担心的是，当G1转换为G2时，vi保持不变，这意味着在操作序列中没有对vi进行任何操作(例如将G1中的vi替换为G2中的u，删除G1中的vi，在G2中插入vi)将 G1 转换为 G2。
最佳答案
没有算法可以解决您的特定问题，因为没有用例，也没有数学形式。我将如何解决这个问题:
1) 在注释中，您指定 Vk 不变，但指定 Ek(1) Ek(2)，其中 Ek(i) 是 Vi 的 Vk 中节点之间的边。在这种情况下，计算边添加/rem/替换，GED(Vk1, Vk2) 忽略 Vk1/2 之外的边
2) 计算 GED(V1-Vk1, V2-Vk2)，忽略 Vi-Vki 和 Vki 之间的边。其中V1-Vk1是删除Vk中的所有节点以及与Vk链接的所有边之后的图V1
3) 计算GED(E(V1-Vk1 <-> Vk1), E(V2-Vk2 <-> Vk2))，即计算将“连接V1-Vk1和Vk1的边”替换为“的GED”连接 V2-Vk2 和 Vk2 的边。
4) 将 3 个 GED 加在一起。
关于algorithm - 是否有任何算法可以计算包含相同节点的两个图之间的编辑距离？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40148063/