вершине 2, а единицу
вершине 2, а единицу потока из вершины 2 попытаемся “протолкнуть” по сети, используя другие дуги. Итак, вершина 4 просмотрена, вершина 2 помечена, вершины 5 и 6 не помечены. Четвертый и пятый шаги очевидны. Передаем единицу потока из вершины 2 в вершину 6 через вершину 5. Вершина-сток достигнута, найдена цепочка 1?3?4?2?5?6, по которой можно передать поток, равный единице. При этом по прямым дугам поток увеличивается на единицу, по обратным - уменьшается. Суммарный поток в сети - 4 единицы.
Четвертая итерация. Вершине 1 присваиваем метку [1,@]. Первый шаг. Помечаем вершину 3 - [1,4]. Второй шаг. Рассматриваем помеченную, но не просмотренную вершину 3. Одна дуга - (3,4). Вершину 4 пометить не можем - пропускная способность дуги исчерпана. Помеченных вершин больше нет, и вершина-сток не достигнута. Увеличивающую поток цепочку построить не можем. Найден максимальный поток в сети. Можно заканчивать работу.
Итак, в чем суть “техники меток” Форда и Фалкерсона? Первое. На каждой итерации
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
