Ошибка при приближении к максимальному совпадению двух сторон

Question

Двусторонний граф с источником и раковиной приведен ниже. Емкость каждого ребра составляет 1 единица: Source : GeeksforGeeks

Я пытаюсь найти максимальный поток от источника до потолка. Один из подходов будет использовать алгоритм Форда-Фулкерсона для задачи максимального потока, который применим ко всем графикам. Я нашел простой подход, чтобы найти максимальный поток (слишком просто, чтобы быть правильным!), И я не могу найти ошибки в подходе.

подход:

c1 = Подсчитайте число вершин, имеющие ненулевое число ребер, исходящие из него, в списке вершин, имеющие исходящие ребра.

c2 = Рассчитать количество вершин, имеющих не равное нулю число ребер, сходящихся в нем, в списке вершин, имеющих входящие ребра.

Максимальный поток будет минимальным из обоих этих чисел, то есть, мин (с1, с2). [Так как любой путь нуждается в одну вершину из списка исходящих вершин, и другой из списка входящих вершин.]

Любая помощь будет оценена по достоинству.

Answer 1

Рассмотрим граф как

*--* 
/
/
* * 
/
/
*--* 

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

Answer 2

Не имеет точного ответа , но у меня есть итеративный алгоритм, который работает. Для меня вам явно необходимо уравновесить поток, чтобы он распределялся среди левых вершин, которые могут отправлять его в правильные вершины, которые могут его получить. Предположим, что вы моделируете свою ситуацию с матрицей A, содержащей двухсторонние ссылки. Затем вы можете предположить, что если ваша матрица содержит ровно количество потока (от 0 до 1), которое вы хотите передать в ребро, то общий поток, учитывая это решение, равен b = A * a, где a - вектор единиц. Если вы начинаете с максимальной емкости для A, поместив все ребра на один и все остальные на 0, у вас могут быть некоторые элементы b с более чем 1, но вы можете уменьшить их соответствующие элементы A, чтобы они пропускали меньше потока , Затем вы можете вернуть поток и посмотреть, какая максимальная пропускная способность вашей двудольной части, и проверить ее с помощью a = A 'b. Снова у вас могут быть элементы из более 1, означающие, что идеальный поток будет больше, чем возможная мощность от источника к элементу, и уменьшит эти элементы в потоке A. С помощью этого алгоритма пинг-понга и уменьшения исправления постепенно, вы гарантированно сходитесь на оптимальной матрице. Учитывая окончательный b = A a с вектором единиц, ваш максимальный поток будет равен сумме (b). Смотрите октавный код ниже, я использую B как матрицу конвертации и дайте мне знать ваши комментарии.

A=[0 1 0 1;1 0 0 1;1 1 0 0;0 0 1 0]; 
B=A; 
repeat 
    b=B*ones(4,1); 
    B=B.*([.8 .8 .8 1]'*ones(1,4)); 
    a=B'*ones(4,1) 
    B=B.*(ones(4,1)*[.9 .9 1 .9]); 
until converge 
maxflow=sum(b)