Возникли проблемы с пониманием проблемы MAX-CUT

Question

У меня проблемы с пониманием общей идеи проблемы MAX-CUT.Рассмотрите график ниже.

MAX-CUT просит нас найти срез, который максимизирует количество ребер, к которым он прикасается.Я могу нарисовать это тривиально.

Я не понимаю, в чем проблема?Для любого графика для меня тривиально найти линию, которая пересекает все ребра.Я неправильно понимаю проблему?

РЕДАКТИРОВАТЬ:

В ответ на Дэвида, вот изображение моей версии MAX-CUT, где мы заканчиваем на конечной вершине

Answer 1

Формальное определение MAX-CUT состоит в том, чтобы найти набор вершин S, чтобы максимизировать количество ребер с ровно одной конечной точкой в ​​S. Графически это означает рисование простой замкнутой кривой и подсчет только количества ребер, пересеченных нечетное количество раз.