AM>Как раз нет, нужно найти такой разрез графа, чтобы его пропускная способность была самая минимальная из всех возможных разрезов на две части. При этом, изночально не известны вершины, принадлежащие этим частям. Алгоритмы это делующие я нашел, к примеру здесь, но хотелось бы найти и реализацию.

Тогда режем граф на два множества одно из которых пустое
Какова исходная задача? для чего режем граф?
пропускная способность не имеет смысла без указания источника и стока.

У меня было подобное при генерации бесшовных текстур и разбиения на "фон/объект" но в этих случаях произвольное разбиение было недопустимо.
Вот и хочется понять, откуда может возникнуть необходимость разрезать граф "как попало, лишь бы разрезать".