子图同构
我们有图 G_1=(V_1,E_1), G_2=(V_2,E_2)。
问题：图 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 是完整的）
我尝试了以下方法：
- 非确定性图灵机首先“猜测”节点 V 的子集和 G_2 的边 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 <= n。令 G=G_2。问题子图同构有一个解决方案，当且仅当存在 G_2 的具有 k 个顶点的完整子图，即，如果图 G 具有具有 k 个顶点的完整子图。
因此，如果问题 Clique 的初始实例有解，则子图同构问题的实例有解。
因此，子图同构问题是 NP 完全的。
你能告诉我它是否正确，或者我是否可以改进一些东西？