在圖中找到所有的crtical節點集

Question

給定一個圖，我想找到可移除可能斷開網絡的節點集S1，S2，...。每個這些集可能包含一個或多個節點。 這些集合中的任何一個都不是彼此的子集，即我們不考慮S3 = S1 U S2，儘管它也斷開了網絡。

我們不想找到：

1. 只有一個關鍵節點設置，但所有
2. 單集斷開網絡最大程度的節點。

上任何這些的任何建議：

1. 硬度的問題
2. 某些方向/紙參照溶液
3. 我可以具有任何證據，得到

Answer 1

你正在試圖找到的是graph partitioning。
這是一個NP Hard的問題。
請參閱this瞭解更多關於圖分區的知識。如果你是google的話，有Nearly-Linear Time Algorithms for Graph Partitioning可用。

Answer 2

其移除斷開圖形的頂點集稱爲分隔符。見例如A. Berry，J-P Bordat，O. Cogis：Generating all the Minimal Separators of a Graph。