无法理解MAX-CUT问题

Question

我无法理解MAX-CUT问题背后的一般想法。请看下面的图表。

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

我不知道问题是什么？对于任何图形，我找到跨越所有边缘的线是微不足道的。我误解了这个问题吗？

编辑：

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

Answer 1

formal definition of MAX-CUT是找到一组顶点S，以最大化S中恰好有一个端点的边数。从图形上看，这意味着绘制一条简单的闭合曲线，并仅计算经过奇数次的边数。