子图同构
我们有图 G_1=(V_1,E_1), G_2=(V_2,E_2)。
Question：图 G_1 与 G_2 的子图同构吗？
（即，是否存在 G_2、V ⊆ V_2 的顶点子集和 G_2、E ⊆ E_2 边的子集，使得 |V|=|V_1| 和 |E|=|E_1| ，并且是否存在一对一G_1 的顶点在 G_2 的顶点 V 的子集处的一次匹配，f:V_1 -> V 使得 {u,v} ∈ E_1 { f(u),f(v) } ∈ E)
- 证明该问题的子图同构属于NP问题。
- 证明该问题是 NP 完全的，将问题 Clique 简化为该问题。 （提示：认为图G_1是完整的）
我已经尝试过以下方法：
- 非确定性图灵机首先“猜测”G_2 的节点 V 的子集和边 E 的子集，然后验证 |V|=|V_1|和 |E|=|E_1|并且存在一一对应关系 f: V_1 -> V 使得 {u,v} ∈ E_1 { f(u), f(v) } ∈ E 。
由于存在 O(|V_2|^2) 个不同的顶点对，因此检查需要多项式时间。所以问题属于NP问题。
- 设 (G,k) 是团问题的任意实例，其中 k 是团的顶点数。
我们可以在多项式时间内构造一个子图同构问题的实例，如下所示：
G_2 是一个有 n 个顶点的图。
G_1 是 k 个顶点的完整图，对于某些 k
因此，当且仅当问题 Clique 的初始实例有解时，子图同构问题的实例就有解。
因此，子图同构问题是NP完全的。
你能告诉我这是否正确或者我是否可以改进一些东西？
None
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
