Оптимально уменьшая максимальный поток

Question

Учитывая параметр k , я пытаюсь удалить k ребер из ориентированного графа таким образом, чтобы максимальный поток был максимально уменьшен.График имеет источник s и приемник t , а емкость каждого ребра равна единице.Граф может содержать или не содержать циклы.

Мое предлагаемое решение состояло бы в том, чтобы сначала выполнить топологическую сортировку графа, используя алгоритм, который «прощает» циклы - возможно, игнорируя ребра, которые возвращают нас кисточник.Тогда (при условии k > = 1):

i = 0
for each vertex u order by topological(u)
   for each edge (u, v) order by topological(v) descending
       if topological(v) > topological(u) then
            delete (u, v)
            if ++i = k then return
       else
            // edge doesn't contribute to max flow, ignore

Будет ли это работать, или я совершенно не в курсе?

Answer 1

Я думаю, что вы совершенно не в курсе. Ваш алгоритм может вообще не уменьшать поток, хотя можно уменьшить максимальный поток как минимум на k (или сделать его равным 0).

Вам известна теорема о минимальном сечении максимального потока?