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

K13>А в чем проблема нзначить сток и исток?
K13>Все равно ведь если требуется разрез графа, существуют вершины которые обязательно должны принадлежать разным частям?

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