Каждой дуге графа приписывается число, называемое пропускной способностью дуги. Это число равно грузоподъемности транспорта, циркулирующего по дуге. Количество груза, перевозимого по дуге, называется потоком через дугу. Дуга считается насыщенной, когда величина потока через нее равна пропускной способности, т. е. когда транспорт используется полностью, ненасыщенной, когда величина потока меньше пропускной способности. Величина потока может иметь только положительное значение и не может превышать величины пропускной способности. К этим двум ограничениям, накладываемым на поток, добавим еще одно: суммарный поток, входящий в любую из промежуточных вершин, должен равняться выходящему из этой вершины потоку. Физически это означает, что мы не допускаем образования запасов грузов в промежуточных точках.

Требуется составить такой план перевозок, при котором количество перевезенного за один рейс груза будет наибольшим.

Начнем с того, что выберем какой-либо произвольный план перевозок ролекс, удовлетворяющий перечисленным выше ограничениям потока. Самый простой путь выбора такого плана будет следующий: выделим любую цепочку последовательных маршрутов, образующих путь из начала графа Н в его конец. В этой цепочке дуг выберем дугу с наименьшей пропускной способностью (дуга НА с пропускной способностью С(Н,А)=1) и пропустим через выбранный путь поток, равный этой наименьшей пропускной способности, т. е. единице в данном случае. Вторые цифры на дугах НА, АБ и БК поэтому равны единице, вторые же цифры на остальных дугах равны пока нулю. Совершенно очевидно, что выбранное решение – не наилучшее. Будем его постепенно улучшать. Систематическое улучшение плана перевозок весьма удобно выполнять, пользуясь так называемым способом расстановки пометок.