algorithm - 无法理解 MAX-CUT 问题

Question

我无法理解 MAX-CUT 问题背后的总体思路。考虑下图。

MAX-CUT 要求我们找到最大化它接触的边数的切割。我可以简单地画这个。

我不明白问题是什么？对于任何图表，找到穿过所有边的线对我来说都是微不足道的。我误解了这个问题吗？

编辑：

作为对 David 的回应，这是我的 MAX-CUT 版本的图片，我们在结束顶点处结束

标签： algorithmnpnp-hard

Answer 1

MAX-CUT的正式定义是找到一组顶点S，以最大化在 中只有一个端点的边数S。从图形上看，这意味着绘制一条简单的闭合曲线并仅计算与奇数次相交的边的数量。