Как вы находите максимальный поток на орграфе, где возможности могут быть отрицательными?
Ford-Fulkerson и Edmonds-Karp et. и др. начните с нулевого потока и увеличивайте его до тех пор, пока он не может быть увеличен. В случае положительных способностей; однако начальный нулевой поток гарантированно будет как законным потоком, так и потоком, который удовлетворяет ограничениям емкости.
При отрицательных мощностях распределение потоков по всем нулям не удовлетворит ограничения по пропускной способности, поэтому их нельзя увеличить до максимального потока.
Я читал, что люди в Интернете предполагают, что максимальный поток с отрицательной емкостью можно решить как две проблемы с максимальным потоком, но я не смог понять, как это сделать...
0 ответов
Скажем, у вас есть ограничение емкости на ребре от u до v от -3, что это значит?
Ну, по определению, это означает, что вы не можете перенести более -3 единиц потока от u к v; значение потока от u до v может быть, например, -5, -4 или -3. Если мы, как обычно, утверждаем, что поток-x из u в v совпадает с потоком x из v в u, то мы видим, что эти примеры потоков -5, -4 или -3 будут преобразованы в потоки 5 или 4 или 3 от v до u и, кроме того, чтобы поток от v до u не мог быть меньше 3.
Таким образом, мы видим, что максимальная емкость -x от u до v эквивалентна минимальному ограничению емкости x от v до u, и поэтому проблема обработки отрицательных ограничений емкости в вычислении максимального потока сводится к проблеме обработки как максимального, так и минимального положительного только мощности.
Можно обработать минимальную и максимальную пропускную способность, сначала найдя выполнимый поток на графике, поток, который удовлетворяет правилам потока и ограничениям пропускной способности, но это не обязательно максимальный поток - это можно сделать путем нахождения "циркуляции" на специально сконструированном график, полученный из исходного графа, а затем превращение допустимого потока в максимальный поток путем решения задачи максимального потока. Этот метод подробно обсуждается по следующей ссылке: слайды с максимальным расходом