Алгоритм максимального потока, увеличивающий путь

Question

1) Истина или ложь: мы всегда можем найти последовательность потока, увеличивающего st-пути в алгоритме Форда-Фулкерсона, так что мы достигаем максимального потока за полиномиальное число итераций.

2) Истина или ложь: мы всегда можем найти последовательность потока, увеличивающего st-пути в алгоритме Форда-Фулкерсона, так что мы достигаем максимального потока только после экспоненциального числа итераций.

Answer 1

Первый ответ определенно ложный. Поскольку время работы алгоритма Форда-Фулкерсона не является полиномиальным - оно экспоненциально.

Следовательно, чтобы найти все st пути для достижения максимального потока, потребуется экспоненциальное время.

Время работы алгоритма Форда-Фулкерсона составляет O(nV), точнее O((n+m)V), где n количество узлов, m количество ребер в графе. А также V максимальная вместимость графика

Следовательно, это может выглядеть как алгоритм полиномиального времени. Однако если V большой, и давайте предположим, что это большое число может быть выражено как 2^kтогда время работы становится O(n. 2^k) - который является экспоненциальным.

Второй ответ также неверен в некоторых случаях, но в основном верно, если вы рассматриваете целые / рациональные числа для значений емкости на графике. Мы знаем, что алгоритм занимает экспоненциальное время - с этим проблем нет. Однако, если значения емкости графа иррациональны, то алгоритм Форда-Фулкерсона не гарантирует завершение. Следовательно, второе утверждение также несколько неверно. Тем не менее, это верно для большинства случаев, так как в большинстве случаев емкости являются целочисленными или рациональными значениями.

Answer 2

Первое утверждение верно. Второе утверждение неверно.

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)).

Это должно ответить на ваш первый вопрос - мы всегда можем найти максимальный поток, увеличивая пути st за полиномиальное время.

По поводу вашего второго вопроса: рассмотрим график G, где все емкости имеют значение 1. Очевидно, что максимальное значение расхода меньше, чем |E|.

Поскольку каждая итерация цикла while увеличивает текущее значение потока f на положительное целое число (фактически на единицу. Если вам нужно подтверждение, перейдите в CLRS), мы имеем, что цикл while повторяется не более чем |E| раз. Таким образом, у нас есть время работы O(E*(E+V), независимо от того, как мы выбираем дополняющие пути. Этот график противоречит второму утверждению.