Как формально доказать эту проблему на Форд Фулкерсон? - PullRequest
0 голосов
/ 27 февраля 2019

Вопрос состоит в том, чтобы доказать, что если мы рассмотрим только передние ребра в нашем остаточном графе, то докажем, что отличие от нашего решения и максимального потока не более 1 / b для некоторой константы b.

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

  A
 /|\ 
S | T
 \|/
  B

ТогдаУ меня есть два утверждения, которые я не знаю, как формализовать.

Во-первых, вы всегда можете увеличить максимальное значение потока, добавив узел и два ребра.Например, добавьте другой узел u прямо из s в u и t, и вы увеличили максимальную емкость.

Во-вторых, если этот добавленный узел u подключен к середине, вы всегда можете обрезать середину и вырезатьот каждого другого ребра, которое исходит от источника и приводит к одному пути P.

В результате вы можете бесконечно увеличивать максимальный поток, сохраняя при этом постоянный поток, выбирая путь P каждый раз.Таким образом, это не может быть ограничено

Я действительно не знаю, как объяснить это, кроме того, чтобы нарисовать их.Мне было интересно, если кто-нибудь может помочь мне формализовать это.

...