蘊涵圖分配

蘊含圖是一個有向圖，其中每個節點都分配了true或false，並且任何邊都暗示着if u is true then v is true。蘊涵圖分配

我知道一個簡單的O(n^2)算法來找出在一般蘊涵圖的分配和O(n)算法某些特殊情況下（如從2-SAT問題產生的蘊涵圖）。

所以我想知道是否有O(n)算法找到任何蘊涵圖的任務？

2014-09-20 Corei13

您沒有指定對作業有什麼要求。 – piotrekg2 2014-09-20 19:50:36

你能舉出一個不等於2-SAT問題的蘊涵圖的簡單例子嗎？（我認爲所有的蘊含圖等價於2-SAT，並且都可以通過Tarjan的強連通分量算法在O（n）中求解） – 2014-09-20 20:02:42

@ piotrekg2，每條邊指定一個需求。從節點u到節點v的邊表示如果u被分配爲真，則v也必須爲真。 – Corei13 2014-09-20 20:40:35

由於該方法適用於所有蘊含圖，而不僅僅是通過2-SAT實例轉換生成的圖，因此可以使用Tarjan strongly connected components方法找到滿足蘊含圖的賦值。該方法由少量的圖形轉換步驟組成，所有這些步驟都需要與輸入大小成線性關係的時間。因此整個算法需要O（n）運行時。

2014-09-21 00:33:27

回答