Алгоритма: Проверьте, если максимальный поток является уникальным

Question

Вопрос к следующему упражнению:

Пусть N = (V, E, C, S, T) представлять собой сеть потока таким образом, что (V, Е) является ациклический, и пусть m = | E |. Опишите алгоритм времени многочлена - , который проверяет, обладает ли N уникальным максимальным потоком, решая проблемы с максимальным потоком ≤ m + 1. Объяснить правильность и время работы алгоритма

Мое предложение было бы следующее:

run FF (Ford Fulkerson) once and save the value of the flow v(f) and the flow over all egdes f(e_i) 
for each edge e_i with f(e_i)>0: 
    set capacity (in this iteration) of this edge c(e_i)=f(e_i)-1 and run FF. 
    If the value of the flow is the same as in the original graph, then there exists another way to push the max flow through the network and we're done - the max flow isn't unique --> return "not unique" 
    Otherwise we continue 

we're done with looping without finding another max flow of same value, that means max flow is unique -> return "unique" 

Любая обратная связь? Упустил ли я некоторые случаи, когда это не работает?

Answer 1

Ваш вопрос оставляет несколько деталей открытым, например, это целочисленный потоковый граф (возможно, да, хотя Ford-Fulkerson, если он сходится, может работать и в других сетях), и как именно вы определяете, потоки различны (достаточно ли, чтобы функция, сопоставляющая ребра с потоками, была различной или должна была различать множество ребер, что-то другое, что является более сильным требованием).

---

Если сеть не обязательно является целым потоком, то нет, это не обязательно будет работать. Рассмотрим следующий график, где на каждом ребре число в круглых скобках представляет собой фактический поток, а число слева от круглых скобок представляет собой емкость (например, емкость каждого из (a, c) и (в, г) составляет 1,1, а поток каждого является 1.):

на этом графике, поток не является уникальным. Можно пропускать в общей сложности 1 путем плавания от 0,5 до (a, b) и (b, d). Однако ваш алгоритм не найдет этого, уменьшив емкость каждого из ребер до 1 ниже его текущего потока.

Если сеть целая, не гарантируется найти другой набор участвующих ребер, чем текущий. Вы можете увидеть его через следующий график:

---

Наконец, хотя, если сеть представляет собой сеть целого поток, а значение другого потока просто другая функция ребер для потоков , то ваш алгоритм правильный.

1. Достаточность Если ваш алгоритм находит другой поток с таким же общим результатом, то очевидно, что новый поток является законной, и, кроме того, обязательно, по крайней мере, один из краев текут разное количество, чем это сделал ранее.

2. Необходимость Предположим, что существует другой поток, чем исходный (с тем же общим значением), по крайней мере с одним из краев, различающимся по количеству. Скажем, что для каждого края поток в альтернативном решении не меньше потока в исходном решении. Поскольку потоки отличаются друг от друга, должно быть, по крайней мере, одно ребро, где поток в альтернативном решении увеличивается.Без другого края, уменьшающего поток, хотя есть либо нарушение сохранения потока, либо исходное решение было субоптимальным. Следовательно, существует некоторое ребро e, где поток в альтернативном решении ниже, чем в исходном решении. Поскольку это целая сеть потока, поток должен быть как минимум на 1 ниже на e. Однако, по определению, уменьшая емкость e, по крайней мере, на 1 ниже, чем текущий поток, не сделает альтернативный поток незаконным. Следовательно, необходимо найти альтернативный поток, если емкость уменьшена для e.

Answer 2

• не целое, рациональные потоки может быть «масштабируется» в целом
• изменения края емкость является рискованной, поскольку некоторые ребра могут иметь решающее значение и включены в каждом максимальном потоке

там это лучшее решение для выполнения, вам не нужно проверять каждый край. создать остаточную сеть (https://en.wikipedia.org/wiki/Flow_network). запустите DFS на остаточном сетевом графике, если вы найдете круг, это означает, что есть еще один максимальный поток, в котором поток по крайней мере на одном ребре отличается.