Условие задачи
Требуется, расставляя пометки в графе с заданным потоком с помощью алгоритма, описанного в теореме Форда-Фалкерсона, найти максимальный поток между вершиной с номером 1 и вершиной с максимальным номером, если улучшенный поток окажется максимальным, то нужно указать то минимальное сечение, которому равен наш поток (если же улучшенный поток не окажется максимальным, то нужно снова его улучшать до тех пор, пока не окажется он максимальным).
Ответ
Первоначально поток в сети нулевой, т.е. величина потока в каждом ребре равен нулю. Источником является вершина s=1, а стоком t=6.
Строим увеличивающую цепь, соединяющую источник s со стоком t. В общем случае в эту цепь могут входить как прямые, так и обратные дуги.
Для построения такой цепи и последующего решения задачи, для каждой дуги (x,y) сети находят две величины: i(x,y)=c(x,y)-f(x,y), r(x,y)=f(x,y). Здесь i(x,y) - величина, на которую может быть увеличен поток в дуге (x,y), а r(x,y) - величина, на которую может быть уменьшен поток в этой дуге.
В процессе решения задачи дуги сети делятся на...
