Проверьте, есть ли один минимальный разрез в данном сетевом потоке.

Я ищу алгоритмы, которые проверяют, есть ли минимальный разрез в данном сетевом потоке.

Я знаю, что это возможно, поскольку мы можем искать все разрезы и проверять, есть ли у нас только один минимальный разрез, но я хочу найти более эффективный алгоритм, который работает полиномиально.

Я думал об использовании алгоритма максимального потока, чтобы помочь мне, но мне это не удалось.


graph algorithm graph-algorithm network-flow
person Asaf Kahlon    schedule 05.07.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Я предполагаю, что вы имеете в виду взвешенный случай, если нет - невзвешенный можно довольно легко уменьшить до взвешенного, придав вес 1 всем ребрам.

Один из подходов состоит в том, чтобы найти один минимальный разрез, пусть это будет расщепление U1,U2, а затем для каждой пары вершин u1 из U1 и u2 из U2, таких, что (u1,u2) находится в E - проверьте, слегка увеличив вес w(u1,u1) - есть еще минимальный разрез с таким же значением.
В конце концов, тогда и только тогда, когда вы нашли одно ребро, такое, что минимальное значение разреза остается - существует более одного минимального разреза.

Псевдокод высокого уровня:

value,U1,U2 = min-cut(G) //value is the minimum cut value, U1,U2 are the cuts
for each u1 in U1 and u2 in U2 such that (u1,u2) is in E:
   temp <- w(u1,u2)
   w(u1,u2) <- w(u1,u2) + epsilon
   new_value,_,_ = min-cut(G)
   if (new_value == value): //2+ cuts with same value
        return true
   //roll back the changed weight
   w(u1,u2) <- temp
return false //no cuts with same value found

Сложность равна O(E*min-cut), где min-cut — это сложность используемого алгоритма min-cut.

person amit    schedule 05.07.2014