algorithm - 找到一个公共(public)子图

Question

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

鉴于图1是

A - B

A - C

B - D

D-E

图2是

A - B

A - E

B-D

算法应该返回

A - B

B-D

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

Answer 1

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

要实现它 - 您只需要 intersection E1 和 E2。

证明:

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

(<-) 假设 (a,b) 对 G1 和 G2 是通用的 - 那么 (a,b) 在 E1 和 (a,b) 在 E2 - 根据交集的定义，(a,b) 在E1 [交叉口] E2

---

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