clique-problem

4熱度

2回答

「證明它是NP完全的以確定給定的輸入G和k是否G既有k大小集合又有大小爲k的獨立集合請注意，這是1個問題，而不是2;答案是肯定的當且僅當 G有這兩個子集。「在我的算法課程中，我們遇到了這個問題，一大羣學生無法弄清楚。這是我們迄今爲止的... 我們知道集團和獨立集合問題都是NP-Complete。我們也知道，NP中給出了一些「證書」，這個問題的驗證。這個問題在某種程度上減少了上述問題（它包含獨立