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

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

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

Подход :

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

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

Максимальный поток будет минимальным из обоих этих чисел, т. Е. Min (c1, c2). [Поскольку для любого пути требуется одна вершина из списка исходящих вершин, а другая - из списка входящих вершин.]

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


graph algorithm max-flow bipartite
person gautamk    schedule 24.01.2016    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

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

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

person David Eisenstat    schedule 24.01.2016
comment
Большое спасибо. Я искал именно это. - person gautamk; 26.01.2016
comment
Это был мой первый вопрос в Stack Overflow. Не знал об этом. Спасибо. - person gautamk; 26.01.2016

arrow_upward
0
arrow_downward

У меня нет точного ответа, но у меня есть итеративный алгоритм, который работает. По-моему, вам явно необходимо уравновесить поток, чтобы он распределялся между левыми вершинами, которые могли отправлять его в правые вершины, которые могут его принимать. Предположим, вы моделируете свою ситуацию с помощью матрицы 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)
person hjohanns    schedule 24.01.2016