Глава 22. Потоки в сетях. Если это подходящее ребро, которое мы использовали для построения цикла, оно пе­рестает быть подходящим (его приведенная стоимость остается той же

Если это подходящее ребро, которое мы использовали для построения цикла, оно пе­рестает быть подходящим (его приведенная стоимость остается той же, однако из полного оно становится пустым или из пустого превращается в полное). Во всех других случаях оно становится частично заполненным. Присоединив его к дереву и удалив полное или пустое ребро из цикла, мы выполняем инвариантное условие, согласно которому ника­кое недревесное ребро не может быть частично заполненным, а само дерево есть допу­стимым остовным деревом. Мы также рассмотрим механику соответствующих вычисле­ний в этом разделе несколько позже.

По сути дела, допустимые остовные деревья позволяют нам вычислить потенциал вер­шин, которые дают приведенные стоимости, которые, в свою очередь, дают допустимые ребра, которые, опять-таки, дают циклы отрицательной стоимости. Наращивание циклов отрицательной стоимости снижает стоимость потока и влечет к изменениям в структуре дерева. Изменения в структуре дерева обусловливают изменения потенциалов вершин, изменения потенциалов вершин приводят к изменению приведенных стоимостей ребер, а изменения приведенных стоимостей влекут за собой изменения во множестве подходя­щих ребер. Выполнив все эти изменения, мы можем выбрать другое подходящее ребро и начать процесс снова. Это общая реализация алгоритма вычеркивания циклов для ре­шения задачи о потоке минимальной стоимости называется сетевым симплексным алгорит­мом:

Постройте подходящее остовное дерево и поддерживайте потенциалы вершины таки­ми, чтобы все вершины остовного дерева имели нулевую приведенную стоимость. До­бавьте подходящее ребро в дерево, нарастите поток в цикле, который оно образует с древесными ребрами, и вычеркните из дерева ребро, которое оказалось заполненным или опорожненным, после чего продолжайте этот процесс до тех пор, пока не ока­жется ни одного подходящего ребра.

Эта реализация является обобщенной, поскольку начальный выбор остовного дерева, метод поддержания потенциалов вершин и метод выбора подходящих ребер не опреде­лены. Стратегия выбора подходящих ребер определяет число итераций и выбирается с учетом затрат на реализацию различных стратегий такого выбора и на пересчет потенци­алов вершин.

Свойство 22.28. Если общий сетевой симплексный алгоритм завершает работу, это оз­начает, что он вычисляет поток минимальной стоимости.

Доказательство: Если указанный алгоритм прекращает работу, то он делает это пото­му, что в остаточной сети больше нет циклов отрицательной стоимости, а по свойству 22.23 это означает, что полученный максимальный поток обладает минимальной сто­имостью. ■

Ситуация, когда алгоритм может не завершить свою работу, обусловлена возможнос­тью того, что процесс наращивания потока в некотором цикле может заполнять или опо­рожнять сразу несколько циклов, из-за чего в дереве могут оставаться ребра, через ко­торые невозможно проталкивание какого-либо потока. Если мы не можем протолкнуть поток, то не можем выполнить приведение цен, зато можем попасть в бесконечный цикл добавления и удаления ребер с целью получения фиксированной последовательности ос­товных деревьев. Было найдено несколько способов избежать подобного рода ситуаций,