Максимальный разрез графа

Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза. Задача определения максимального разреза для графа известна как задача о максимальном разрезе. Задачу можно сформулировать следующим образом. Следует найти подмножество вершин S, такое, что число рёбер между S и его дополнением было бы настолько велико, насколько это возможно. Существует расширенная версия, задача о взвешенном максимальном разрезе. В этой версии каждому ребру приписано вещественное число, его вес, и целью является максимизация не числа рёбер, а общего веса рёбер между S и его дополнением. Задача о взвешенном максимальном разрезе часто, но не всегда, ограничивается неотрицательными весами, поскольку отрицательные веса могут изменить природу задачи.