Soptq

子圖同構（Subgraph isomorphism problem）問題的描述如下：給定兩個圖 $G_1$ 和 $G_2$，判斷 $G_1$ 是否與 $G_2$ 的一個子圖同構。首先假如我們得到了 $G_1$，$G_2$ 和對應的解（即 $G_2$ 的子圖 $G_s$ 使得 $G_s$ 與 $G_1$ 同構），我們只需要遍歷解中的點和每一個與這個點相連接的邊，檢查是否與 $G_1$ 對應即可驗證解的正確性。所以這個問題首先顯然是一個 NP 問題。

為了證明這個問題同時也是一個 NP 難問題，我們將 分團問題 規約到 子圖同構問題上來。具體地，假設我們現在有一個有解的分團問題 $<G,k>$，即 $G$ 中存在 $k$ 個點可以構成團（即這 $k$ 個點相互連接，即構成一個 $k$- 完全圖）。那麼我們構造一個 $G_1$ 為 $k$- 完全圖，構造 $G_2 = G$。顯然上述兩個圖的構造是可以在多項式時間內完成的。

考慮若有一個算法 $A_s$ 可以在多項式時間內解決子圖同構問題的話，那麼我們對於一個分團問題，我們只需要按照上述構造，在多項式時間內通過分團問題的 $k$ 和 $G$ 構造出 $G_1$ 和 $G_2$，然後將 $G_1$，$G_2$ 拿給子圖同構問題的算法 $A_s$ 解，即可在多項式時間內得知 $G_1$ 是否是 $G_2$ 子圖的一個同構，即 $k$- 完全圖是否包含在 $G$ 中，即在多項時間內解出了分團問題。

由於我們已知分團問題是 NP 完全的，所以上述的算法 $A_s$ 不存在，所以子圖同構問題為 NP 難問題。綜上所述，子圖同構問題是 NP 完全的。