Задача о наибольшем потоке в сети. Алгоритм Форда-Фалкерсона

↑

⇐ ПредыдущаяСтр 18 из 28Следующая ⇒

Алгоритм Крускала

Пусть дан связный неориентированный граф G=(V,E) с числовыми неотрицательными весами ребер. Вес ребра е обозначим φ(e) В результате работы алгоритма получим остовное дерево T=(V,H) графа G, такое, что сумма ∑φ(e) является наименьшей.

Отсортируем все ребра исходного графа по возрастанию весов и сформируем из них очередь так, чтобы в "голове" очереди находилось ребро с наименьшим весом, а в "хвосте" — с наибольшим и веса ребер не убывали от "головы" очереди к "хвосту".

Метод состоит в "сшивании" искомого дерева из компонент остовного леса. Первоначально остовный лес представляет собой множество изолированных вершин исходного графа, т.е. его множество ребер пусто. На первом шаге из очереди извлекается ребро наименьшего веса и добавляется к множеству ребер исходного дерева.

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

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

Алгоритм расстановки пометок Форда-Фалкерсона или просто алгоритм пометок Форда-Фалкерсона имеет итеративный характер и заключается в выполнении следующих действий:

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

2 определение величины частичного потока в качестве величины частич­ного потока, протекающего по ориентированному пути С₀, присвоить значение: С₀ = min{c_ij}, где минимум берется по всем значениям пропускных способностей дуг, входящих в множество С₀. Перейти к выполнению дей­ствий шага 3;

3 изменение значений множеств D_max и С изменить значения максималь­ного потока, образующих множество D_max, следующим образом: d'_ij = d_ij + c₀; изменить значения пропускных способностей дуг, образую­щих матрицу смежности С, следующим образом: c'_ij = c_ij - c₀. При этом изменяются только значения дуг, входящих в множество С₀. Перейти к выполнению действий шага 4;

4                 проверка условия окончания алгоритма проверить выполнение условия: в сети G', образуемой матрицей смежности С', конечная вершина v_t, является достижимой из начальной вершины v_s. Если это условие не выполняется, то в сети G' отсутствует ориентированный путь С₀, выходящий из начальной вершины и входящий в конечную вершину сети, и выполнение данного алгоритма может быть закончено. Если же данное условие выполняется, то установить: D_max = D'_mах, С = С', С_о = Ø и перейти к выполнению действий шага 1.

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману