из работы [9]. Рядом


из работы [9]. Рядом с пропускными способностями дуг указаны потоки, построенные на этих дугах. На рисунке поток через сеть равен 10 и найдена увеличивающаяся цепочка, выделенная “жирными” линиями. Обратите внимание на ориентацию дуг, входящих в цепочку. По данной цепочке можно пропустить поток, равный 1, пропускная способность дуги (5, 6). Изменяем суммарный поток, его значение становится равным 11. Поток увеличен, необходимо продолжить поиск увеличивающихся цепочек; если окажется, что построить их нельзя, то результирующий поток максимален. Заметим, что для данного примера это значение потока окончательное. Обратите внимание на то, как изменен поток на дугах сети в зависимости от их ориентации. 3.9.2. Метод построения максимального потока в сети Рассмотрим метод на примере. Пусть дана сеть G=(V,E), узлом-источником является вершина 1, узлом-стоком - вершина 6. Построим максимальный поток (F) между этими вершинами. Начальное значение F нулевое. Очевидно, что структурой данных
Индекс
Элементарные функции    Линейные уравнения    Нелинейные уравнения    Случайные числа


Hosted by uCoz