算法來修剪網絡中的節點，實現最大數量的隔離（python networkx）

Question

我有網絡（大的&小），我需要修剪，直到只剩下隔離。我想最大限度地提高分離菌的數量。有沒有一個算法來做到這一點？如果它更復雜？ （例如，在底部有可連接的節點以及）

考慮這個簡單的例子：

import networkx as nx 
G = nx.DiGraph() 
G.add_edges_from([(1,2), (2,3), (2,4), (3,5), (3,6), (4,7), (4,8), 
(1,2+9), (2+9,3+9), (2+9,4+9), (3+9,5+9), (3+9,6+9), (4+9,7+9), (4+9,8+9) ]) 

這裏，最優解刪除節點1,3,4,11和12

Answer 1

這聽起來像你要計算的Maximum Independent Set（這是NP難爲一般圖）。 （維基百科也提到名稱頂點包裝）。

Networkx有一個approximation algorithm。

也許一個近似是不夠的爲你（我認爲沒有預建替代）。

根據上面的維基百科鏈接，在igraph有一個確切的算法可用。

另外請記住，這個近似算法適用於一般圖，所以它可能是非常有可能的，有更好的方法來處理樹。

編輯：（沒有檢查）This SO-answer presents an algorithm for trees（和問題是可能的重複）。