題目

image.png

知識(shí)點(diǎn)

NP-complete、獨(dú)立集問題

解題思路

要證明一個(gè)問題是NP-完全問題，可以將已知的某個(gè)NP-完全問題歸約到該問題。比如對(duì)于本題，我們可以用獨(dú)立集的問題（一個(gè)已知的NP-完全問題）來歸約得出公共子圖問題也是NP-完全問題。首先，假設(shè)我們要求G1=（V，E）中大小為b的獨(dú)立集的問題（NP-完全問題），令G2=（V， ?），因?yàn)镚2沒有邊，即G2中的各個(gè)點(diǎn)都是相互獨(dú)立的，所以G1和G2存在節(jié)點(diǎn)個(gè)數(shù)為b的公共子圖當(dāng)且僅當(dāng)G1存在著大小為b的獨(dú)立集。故而要最大公共子圖問題可以由最大獨(dú)立集問題歸約得來，即也是NP-完全的。

image.png