Задача о максимальном потоке.

Потоком сети наз.ф-цию m, которая каждому ребру данного графа ставит в соответствие неотриц. число m: E®R⁺È {0}.

Для " еÎ E m(e) определяет поток ребра. Проблема максимального потока состоит в том, чтб. для задан­ной сети найти поток, кот. Имеет максимальные из числа возможных цен.

Цена потока – полный поток, приходящийся на сток.

Исходные и конечные пункты нах-ся на разных берегах реки. Мн-во мостов образуют разделяющее сечение, или срезы.

Срез или раздел. сечение – мн-во ребер сети, кот. после удаления из сети образуют граф с двумя компонентами, одна из кот. сод-жит источник, вторая – сток.

Пропускная способность среза складывается из пропускных способностей ребер данного среза.

Емкость среза – сумма весов его ребер.

Возможно несколько срезов для данной сети.

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

Т.о. отыскание максимального потока сводится к отысканию минимального сечения, или минимального среза.

Минимальное сечение – разделяющее сечение с наименьшей пропускной способностью.

Теорема. В сети цена любого максимального потока равна емкости любого минимального среза.

Задача о кратчайшем пути.

Пример (классический пример – задача коммивояжера).

Найти кратчайший путь, проходящий через заданные пункты и возвращающийся в исходный пункт (все расстояния известны).

Торговец, живущий в городе А, намерен посетить города В, С и D, расстояния между кот. известны.

AB=11; AC=13; AD=17; BC=6; BD=9; CD=10.

Требуется указать кратчайший маршрут (циклический) из А через три других города.

ABDCA d=43

ACDBA d=43

ABCDA d=44

ACBDA d=45

ADCBA d=44

ADBCA d=45

ABDCA (ACDBA)

Гамильтонов цикл имеет всегда кратчайший путь.

V₁®V₆ d(V₁V₄V₈V₆)=25

Любой подпуть кратчайшего пути из верш. V₁ в верш. V_n явл. кратчайшим путем. Это свойство названо принципом оптимальности. Оно лежит в основе общего метода решения оптимизационных задач метода динамического программирования.

Алгоритм Дейкстры.

В 1950 г. – Дейкстра предложил алгоритм решения зад. о кратчайшем пути.

Перед началом работы алгоритма все вершины считаются не маркированными, а в процессе работы алгоритма каждой вершине присваивается некоторое число.

1. m(s)=0

m(x)=¥, " x¹ s

2. Пусть x – последняя маркированная вершина. Для нее рассмотрим все смешные с ней вершины. (x, y) – y – смешн. верш.

Для каждой смешной с x верш. находится М=m(ч)+ m(x, y). Если m(y)> M, то m(y)=M

3. Если m(y)=¥, для всех немаркированных вершин, то заканчиваем работу, т.е. нет пути, ведущего из s в t. В прот. Случае маркируется та вершина, для кот. m(y) наименьшая.