Первый ответ определенно ложь .Поскольку время работы алгоритма Форда-Фулкерсона не является полиномиальным - оно экспоненциально.
Следовательно, чтобы найти все st пути для достижения максимального потока, потребуется экспоненциальное время.
Время выполнения алгоритма Форда-Фулкерсона составляет O(nV), точнее O((n+m)V), где n - количество узлов, m - количество ребер в графе.И V - максимальная емкость, которую имеет граф.
Следовательно, он может выглядеть как алгоритм за полиномиальное время.Однако, если V большое и допустим, что это большое число может быть выражено как 2^k, тогда время выполнения становится O(n. 2^k) - экспоненциальным.
Второй ответ также не верен и в некоторых случаях, но в основном верно , если вы рассматриваете целые / рациональные числа для значений емкости на графике.Мы знаем, что алгоритм занимает экспоненциальное время - с этим проблем нет.Однако если значения емкости графика равны иррационально , то алгоритм Форда-Фулкерсона не гарантирует прекращение.Следовательно, второе утверждение также несколько неверно.Тем не менее, это верно для большинства случаев, так как в большинстве случаев емкости являются целочисленными или рациональными значениями.