Здравствуйте, K13, Вы писали:

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

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

Задача из области трекинга объектов в последовательности изображений на основе трекинга особых точек. Дан набор особых точек, и некоторым образом подобранные меры зависимостей между ними(на основе их взаимного расположения, устойчивости конфигурации с течением времени и т. д.). Нужно разделить эти точки, как принадлежащие разным объектам(объекты могут сливаться, перекрываться). При этом, понятное дело, не известно какие из точек принадлежат различным объектам, для этого нужно как раз их и разделить. Потом посчитать пропускную способность разреза и если она больше некоторого значения, то это неправильный разрез(то есть обект один).