2014-06-08 56 views
-4

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

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

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

這是我卡住的地方。

+2

你爲什麼卡住了?你覺得你應該接下來做什麼? – templatetypedef

+0

從我以爲我需要寫一個算法的問題。 – user3282318

+0

你有什麼特別的麻煩?你能概述一下你接下來要做什麼的想法嗎?現在,我們不知道該怎麼幫助你。 – templatetypedef

回答

1

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

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

希望這有助於!