minimum-cut

1熱度

1回答

我剛剛完成coursera中算法專業課程中的第一個模塊。有一個考試問題，我不明白。我已通過考試，所以我沒有必要重新考試。出於好奇，我想了解圍繞這個問題的原則。問題被張貼這樣：假定一個隨機算法成功（例如，正確地計算的曲線圖的最小切）的概率爲p（0 < p < 1）。設ε 爲小正數（小於1）。運行該算法需要多少次獨立時間才能確保至少有1-ε的概率，至少有一次試驗成功？給出的選項是：日

0熱度

1回答

使用Kruskal算法尋找圖的最小切割值

我是一名初學者，我試圖用Java中的Kruskal算法找到圖的最小切割。我已經到了我可以讀取輸入的位置，並創建vertexCount^2數量的邊緣隨機權重的MST。我所要做的就是從我的MST中找出需要多少次切割來分離S和V-S。這將允許我選擇vertexCount^2個選項中的最小值。我想我理解正確，我應該忽略MST的最後一個邊緣來獲得S和V-S。但是我很難弄清楚有多少邊連接S和V-S。所以

4熱度

1回答

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

我們已經看到，生成樹和切割是密切相關的。這是另一個連接。讓我們刪除克魯斯卡爾算法添加到生成樹的最後一條邊;這將樹分成兩個部分，從而在圖中定義一個切割（S，S）。我們可以說這個削減？假設我們正在使用的圖是未加權的，並且它的邊是隨機排列的，以便Kruskal算法處理它們。這是一個值得注意的事實：在概率至少爲1/n^2的情況下，（S，S）是圖中的最小切割，其中切割的大小（S，S）是S和S之間的邊的數量。

1熱度

2回答

查找流網絡的最小割

我試圖找到下面網絡的最小割我使用下面的算法：潤福特Fulkerson算法，並考慮最終殘差圖。找到殘差圖中可以從源訪問的一組頂點。從可到達頂點到不可到達頂點的所有邊都是最小切割邊。打印所有這些邊緣。在第一步驟中，我的算法找到3條路徑： - s->b->h->t **value: 1** - s->d->e->t **value: 1** - s->c->h->i->m->d->g->t

4熱度

1回答

隨機最小切，Karger算法

我正在實施Karger算法。據我所知，最後兩個節點之間的邊數並不總是最小割。我無法理解的是如何真正從這種算法中獲得最小的優勢。我一直在尋找很多可能性的東西，但對我來說這一切看起來都很亂... 從我讀過的內容中，我想我需要在圖上多次運行Karger算法。這會讓我很有可能擊中最低分。我認爲？... 有人可以請簡單解釋一下嗎？我如何找到運行此算法的次數？我剛纔所說的正確嗎？