婚禮策劃師

Question

我做的6.006 MIT OpenCorseWare一個問題，這就是問題所在＃6在下面的鏈接：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/exams/MIT6_006F11_final.pdf

問題本身很容易，但我想知道如何，如果我調整了解決問題問題一點點。

考慮：

• 的客人表V
• 查找表T，其中T [U]在V∈V，就是你知道 （如果u知道訴客人的名單，則v知道U）

問題：

• 安排座位，使得在一個表中的任何客人都知道所有其他客人小號在同一張桌子上直接或通過 一些 坐在同一張桌子上的其他客人。
• 查找來實現這一要求

在原來的問題，你可以通過任何數量的客人坐在同一張桌子知道其他客人所需的表的最小數量。但是我想知道如何解決這個問題，如果只能通過坐在桌旁的其他客人瞭解其他客人。

什麼是最好的算法呢？謝謝您的幫助！

Answer 1

這是NP難。從卡爾普原創的21中的NP-hard問題Clique Cover有一個多項式時間減少，其中包括通過細分每個邊並將每對新頂點連接來將作爲輸入的圖轉換爲Clique Cover，從而每個新頂點與每個頂點的距離≤2，並且當且僅當它們在輸入中相鄰時，兩個不同的舊頂點距離≤2。

從這個問題到Clique Cover有一個簡單的減少，所以我可以建議的最好的算法是用Clique Cover的一個指數時間動態程序來減少這個減少。

Answer 2

使用表示客人的頂點創建圖。如果他們彼此瞭解，則在每個頂點之間創建邊（基於表T）。

現在，您只需查找連接組件的數量即可。 連通分量是集合（S）中存在集合中任何兩個頂點之間的路徑的集合（S）。

連接組件的數量等於您需要的表的數量。