Вопрос состоит в том, чтобы доказать, что если мы рассмотрим только передние ребра в нашем остаточном графе, то докажем, что отличие от нашего решения и максимального потока не более 1 / b для некоторой константы b.
Решение, которое я выбрал, состоит в том, что если у вас есть следующий график, и каждое ребро имеет равную емкость, то вы можете разрезать середину, а затем вы вдвое уменьшите максимальный поток.
A
/|\
S | T
\|/
B
ТогдаУ меня есть два утверждения, которые я не знаю, как формализовать.
Во-первых, вы всегда можете увеличить максимальное значение потока, добавив узел и два ребра.Например, добавьте другой узел u прямо из s в u и t, и вы увеличили максимальную емкость.
Во-вторых, если этот добавленный узел u подключен к середине, вы всегда можете обрезать середину и вырезатьот каждого другого ребра, которое исходит от источника и приводит к одному пути P.
В результате вы можете бесконечно увеличивать максимальный поток, сохраняя при этом постоянный поток, выбирая путь P каждый раз.Таким образом, это не может быть ограничено
Я действительно не знаю, как объяснить это, кроме того, чтобы нарисовать их.Мне было интересно, если кто-нибудь может помочь мне формализовать это.