algorithm - 找到一个公共子图

Question

我试图找到给定两个图的公共子图。如果我有 2 个图 G1=(v1,e1) 和 G2=(v2,e2) 我必须找到公共子图 G=(V,E)，例如 G1 和 G2 的任何另一个公共子图不能包含更多E arris的红衣主教。

鉴于图 1 是

A - B

A - C

乙 - 丁

D - E

图2是

A - B

A - E

乙 - 丁

比算法应该返回

A - B

乙 - 丁

你能帮我用一个算法告诉我要参加哪些步骤吗？谢谢！

Answer 1

您没有正式描述您的问题，但从您的示例¹来看，您似乎正在寻找最大的公共边缘子集。

要实现它 - 您只需要 E1 和 E2 的交集。

证明：

(->)假设(a,b)在E1 [intersection] E2. 根据集合交集的定义——它对 E1 和 E2 都是通用的——因此对 G1 和 G2 也是如此。

(<-)假设(a,b)G1 和 G2 共有 - 然后(a,b)在E1和 (a,b)在E2- 根据交集的定义，(a,b)在E1 [intersection] E2

---

(1) 我得出的结论是，因为(A,C)不是“常见的”，但(A,B)在子图中 - 这意味着这不是对找到可以创建所需子图的顶点子集的限制（因为那时A应该从结果中排除）。