在無向連通圖中如何查找刪除哪個圖形斷開連接的頂點集？

Question

我知道在undirected connected grapharticulation point是刪除哪個圖形斷開後的頂點。對於Java代碼，我沿着這個鏈接http://algs4.cs.princeton.edu/41undirected/Biconnected.java.html。

現在假設我們有上述graph-

在上圖中沒有articulation points因爲圖形不會成爲刪除任何單個頂點斷開。但是我們可以通過刪除多於1個頂點來使圖形斷開連接，例如，如果刪除4,6個頂點圖形，則 將變爲斷開連接。

如何找到一組頂點，使得刪除這些頂點後，圖形變爲斷開連接。可以說，頂點可以被刪除的限制是3，這意味着我們不能一次移除3個以上的頂點，從而使圖形斷開連接。

方法我thinking-

第1步 - 運行算法來找出一個關節點。

步驟2 - 如果在步驟1之後沒有關節點，我們從圖中刪除一個頂點並運行關節點算法，我們對圖中的所有頂點進行此操作。使用這個我們可以找到2個頂點（第一個是在運行算法之前被移除的頂點，第二個頂點是在算法運行之後被找到的），這些頂點的移除將會使圖形斷開，並且程序將因爲我們找到了一組頂點而停止。

步驟3 - 如果我們無法在步驟2中找到頂點集，我們從圖中移除2個頂點並運行關節點算法。我們在刪除每對圖頂點的 之後運行此算法。使用它我們可以找到一組3個頂點去除哪個圖將被斷開。如果仍然沒有斷開連接，我們不會再運行程序，因爲我們可以刪除的頂點的限制是3.

我認爲對此有更好的方法。

如何在刪除哪些圖形斷開連接後找到最小的一組頂點。

什麼可以是更好的方法來找到一組頂點去除哪些圖斷開連接。

Answer 1

對於任何具有度數（即鄰居數）d的頂點，刪除其鄰居的所有d將斷開圖形（除非這些是圖中唯一的其他頂點）。因此，馬上就會給出您需要刪除的頂點數量的上限，以及您可以刪除以實現該邊界的實際頂點：只需查找最小程度的頂點，並刪除其所有鄰居。

在您的示例圖中，您知道這是最佳解決方案，因爲存在具有度數2的頂點，並且您已經排除了大小爲1的解，因爲您已經發現該圖是雙連通的（即，不包含關節點）。但是，一般情況下，可能比這個上界做得更好：例如，考慮一個包含k個頂點上的一個集團的副本以及另外兩個邊（u1，v1）和（u2，v2）的圖第一集團的u1和u2以及第二集團的v1和v2。這可以通過刪除u1和u2（或僅僅v1和v2）來斷開，即使最小度數k可以任意大。

Answer 2

請參閱http://www.cs.colorado.edu/~hal/Papers/expandersC.ps.gz，瞭解我知道的用於計算最小頂點切割的最佳算法。