Я не могу понять, как найти циркуляционный поток в сети с нижними границами (не требованиями). Я нашел следующие документы с описанием проблемы и стратегиями решения:
- https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf
- http://homes.cs.washington.edu/~anderson/iucee/Slides_421_06/Lecture24_25_26.pdf
- http://web.engr.illinois.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf
Рассмотрим сеть со следующими ребрами (l - нижняя граница, c - пропускная способность):
1 -> 2 : l = 1 c = 3
2 -> 3 : l = 2 c = 4
3 -> 1 : l = 1 c = 2
Насколько я понимаю, для решения проблемы мы должны сделать следующие шаги:
- преобразовать эту проблему в "проблему обращения с требованиями". Это можно сделать с помощью следующей формулы dv' = dv - (Lin - Lout), где 'dv' - исходный спрос на вершину (в нашем случае он равен нулю), 'Lin' - сумма нижних границ входных ребер вершины, а ' Lout' - сумма нижних границ выходных ребер вершины.
- обновить емкости ребер как c' = c - l
- добавить исходную вершину S с ребрами к каждой вершине с dv ‹ 0 с мощностями '-dv'
- добавить вершину стока T с ребрами из каждой вершины с dv > 0 с мощностями 'dv'
- найти max-flow в новой сети любым из алгоритмов, например алгоритмом Эдмондса-Карпа.
- если величина максимального потока равна сумме всех запросов на вершины с выходами на Т, то в сети есть циркуляция.
После выполнения этих действий новая сеть будет:
S -> 2 : c = 1
2 -> 3 : c = 2
3 -> T : c = 1
1 -> 2 : c = 2
3 -> 1 : c = 1
Требования к вершинам:
d1 = 0
d2 = -1
d3 = 1
Мы видим, что максимальный поток равен 1 и равен сумме ребер до T, которая также равна 1. И он покрывает ребра A->2->3->T.
Вопрос в том, как получить циркуляционный поток в исходной сети с исходными границами?
Циркуляционный поток в исходной сети существует — нам нужно просто присвоить всем ребрам поток, равный 2.
