У меня следующие два вопроса.
Первый ответ определенно неверный. Потому что время работы алгоритма Форда-Фалкерсона не полиномиальное, а экспоненциальное.
Следовательно, чтобы найти все пути s-t для достижения максимального потока, потребуется экспоненциальное время.
Время работы алгоритма Форда-Фалкерсона равно O(nV), точнее O((n+m)V), где n — количество узлов, m — количество ребер в графе. А V — это максимальная емкость графа.
Следовательно, это может выглядеть как алгоритм с полиномиальным временем. Однако, если V велико и допустим, что это большое число может быть выражено как 2^k, тогда время выполнения становится O(n. 2^k), что является экспоненциальным.
Второй ответ также неверен в некоторых случаях, но в основном верен, если вы рассматриваете целые/рациональные числа для значений пропускной способности на графике. Мы знаем, что алгоритм требует экспоненциального времени — с этим проблем нет. Однако если значения пропускной способности графа иррациональны, то алгоритм Форда-Фалкерсона не гарантирует завершение работы. Следовательно, второе утверждение также несколько неверно. Однако это верно для большинства случаев, поскольку в большинстве случаев емкости являются либо целыми, либо рациональными значениями.
Первое утверждение верно. Второе утверждение неверно.
G_f обозначает остаточную сеть G, c_f — пропускную способность в G_f. Насколько я знаю, это метод Форда-Фулкерсона:
1) Define: f(u,v) = 0, for all (u,v) in E.
2) while there exits a path p from s to t, in G_f:
3) c_f(p) = min{c_f(e) : for all e in p}
4) for (u,v) in p:
5) if (u,v) in E:
6) f(u,v) += c_f(p)
7) else:
8) f(u,v) -= c_f(p)
К концу процесса f является максимальным потоком. (Вы можете прочитать доказательство в «Введение в алгоритм», автор CLRS)
Время работы этого алгоритма равно O(X(V+E)), где X — количество итераций цикла while.
Теперь мы можем найти p в строке (2) с помощью поиска BFS. Такой метод гарантирует, что мы повторяем цикл while O (VE) раз. Эта реализация также известна как алгоритм Эдмондса-Карпа. Таким образом, общее время работы составляет: O(VE*(E+V)).
Это должно ответить на ваш первый вопрос: мы всегда можем найти максимальный поток, увеличивая пути s-t за полиномиальное время.
О вашем втором вопросе: рассмотрите граф G, где все емкости имеют значение 1. Ясно, что максимальное значение потока меньше, чем |E|.
Поскольку каждая итерация цикла while увеличивает текущее значение потока f на положительное целое число (фактически на единицу. Если вам нужно доказательство, обратитесь к CLRS), мы имеем, что цикл while выполняет не более |E| раз. Таким образом, у нас есть время работы O (E * (E + V), независимо от того, как мы выбираем увеличивающие пути. Этот график противоречит второму утверждению.
