使用Kruskal算法尋找圖中的最小切點？

Question

我們已經看到，生成樹和切割是密切相關的。這是另一個連接。讓我們刪除克魯斯卡爾算法添加到生成樹的最後一條邊;這將樹分成兩個部分，從而在圖中定義一個切割（S，S）。我們可以說這個削減？假設我們正在使用的圖是未加權的，並且它的邊是隨機排列的，以便Kruskal算法處理它們。這是一個值得注意的事實：在概率至少爲1/n^2的情況下，（S，S）是圖中的最小切割，其中切割的大小（S，S）是S和S之間的邊的數量。這意味着重複O（n^2）次處理和輸出最小的切割得到G中的最小切割概率：一個O（mn^2 log n）算法用於未加權的最小切割。一些進一步的調整給出了由David Karger發明的O（n^2 log n）最小割算法，它是這個重要問題中已知最快的算法。

• 這難道不是依賴於一個事實，即有n^2種處理通過Kruskal算法圖獨特的方式？我的意思是如果只有克魯斯卡爾算法處理10個節點的圖形的3種獨特方式，重複該過程n^2次將不會產生n^2個獨特的「最後邊緣」。在少於n^2個獨特的最終剪輯（即少於n^2個唯一的「最後邊緣」）的情況下它將如何工作？

• 如果總共少於n^2條邊會怎麼樣？例如，您可以連接10個節點，只有9個邊，這意味着無論您重複算法多少次，都不會有n^2個唯一的「最後邊」。在這種情況下它將如何工作？

• 只是循環遍歷每個邊緣並檢查邊緣是否爲最小切割不是更容易嗎？在n個節點的圖中，唯一邊的最大數目是n + n-1 + n-2 ... + 1個邊，其小於n^2。考慮到n^2小於n^2 log n，爲什麼不循環遍歷所有邊，因爲這更快？

Answer 1

我認爲你可能會誤解算法是如何工作的。該算法通過運行Kruskal算法工作，直到最後一個邊被添加，然後在此之前停止。該算法不會嘗試構建這些「最後邊緣」的集合;相反，重複運行克魯斯卡爾算法的O（n ）隨機迭代，以建立O（n ）可能的切割。在所有這些候選剪輯中取最低的剪輯，然後給出具有高概率的最小剪輯。換句話說，如果有少於O（邊緣）的邊緣，這並不重要。重要的是最後的削減，而不是最後考慮的邊緣。

希望這會有所幫助！