圖切割，切割至少一半的邊緣

Question

任何人都可以幫助我找到一個貪婪的算法，找到至少一半的邊緣圖中的切割？

我認爲正確的方法與使用DFS分離頂點有關，但我不確定。

Answer 1

Mitzenmacher/Upfal（2005），第129頁中的定理6.3給出了一種算法，該算法在預期中切割一半邊緣;像上面評論中引用的維基百科文章所說，我想這可以去隨機化。