无法理解 MAX-CUT 问题

Question

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

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

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

编辑：

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

Answer 1

formal definition of MAX-CUT就是求一组顶点S，使S中正好有一个端点的边数最大化。在图形上，这意味着绘制一条简单的闭合曲线，并仅计算奇数次交叉的边数。