图形切割，至少切割一半的边缘

Question

有人能帮我找到一个贪婪算法吗？它能在至少有一半边的图中找到一个割？

我认为正确的方法与使用DFS分离顶点有关，但我不确定。

Answer 1

Mitzenmacher/Upfal（2005）中的定理6.3，第129页给出了一种算法，该算法根据预期切割一半的边；就像上面评论中引用的维基百科文章所说的那样，我想这可以去随机化。