2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 увеличение максимального потока
Сообщение27.03.2011, 18:44 
Привет.

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

 
 
 
 
Сообщение27.03.2011, 20:52 
Может оказаться, что одним ребром не обойтись.

Самый простой способ -- найдите любой простой маршрут из истока в сток и увеличьте пропускную способность всех ребер на нужное Вам значение $\Delta F$.

Или постройте методом Форда-Фалкерсона остаточную сеть, затем возьмите в ней любой маршрут из истока в сток и увеличьте остаточную пропускную способность составляющих его ребер до величины $\Delta F$.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group