Clique窮舉搜索算法

Question

考慮給定圖g和正整數k的集團問題，確定該圖是否包含大小爲k的集團，即k個頂點的完整子圖。爲這個問題設計一個詳盡的搜索algorthim。

這個問題的提示是遵循集團和窮舉搜索算法的定義。

我知道1.S必須分配一個k大小的子集。 2.針對集合S的每對頂點在G中搜索邊緣。如果失敗返回到步驟1以獲得另一個k大小的子集。第3步停止並返回成功。

這是我卡住的地方。

Answer 1

作爲一個關於如何證明你的算法是正確的暗示：

• 如果你發現在一步一個k大小的子集（1），其中所有的節點都連接，你能肯定地說，該圖有一個K集團？
• 如果圖中有一個k-clique，你可以肯定地說你會在某一點在步驟（1）中找到它嗎？

希望這有助於！