Требуется, расставляя пометки в графе с заданным потоком с помощью алгоритма, описанного в теореме Форда-Фалкерсона, найти максимальный поток между вершиной с номером 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) - величина, на которую может быть уменьшен поток в этой дуге.

В процессе решения задачи дуги сети делятся на...