Найдет ли алгоритм Форда-Фалкерсона максимальный поток сети потоков единичной пропускной способности (все ребра имеют единичную пропускную способность) с n
вершинами и m
ребрами за O(mn)
времени?
Временная сложность метода Форда-Фалкерсона в потоковой сети с ребрами единичной пропускной способности
Ответы (1)
O(M*f)
— известная оценка времени работы Форда-Фалкерсона на графах с целочисленными пропускными способностями, где M
— количество ребер, а f
— значение максимального потока, просто потому, что легко найти возрастающие пути в O(M)
каждый, и каждый такой путь увеличивает поток не менее чем на 1.
Если в вашем графе нет повторяющихся ребер (то есть нет пары ребер с одинаковыми начальной и конечной вершинами) и каждое ребро имеет единичную пропускную способность, то максимальный поток f
не превышает количество вершин N
( только потому, что от источника исходит не более N-1
ребер), и, следовательно, сложность действительно O(N*M)
.
Однако, если в вашем графе разрешено иметь повторяющиеся ребра (но все же каждое ребро имеет емкость 1), то f
может быть больше, чем N
, и вплоть до M
, а временная сложность может стать O(M*M)
, и это нетрудно сделать. с примером, где такая сложность имеет место.