- •Теория графов. Основные понятия и определения
- •Остовные деревья минимального веса. Алгоритмы Прима и Крускала
- •Нахождение кратчайших путей между двумя заданными вершинами. Алгоритм Дейкстры
- •Задача нахождения кратчайших цепей между всеми парами узлов в сети. Алгоритм Флойда
- •Сеть. Потоки на сетях. Задача нахождения потока максимальной мощности. Алгоритм Форда-Фалкерсона
- •Нахождение потока заданной мощности минимальной стоимости. Алгоритм Басакера-Гоуэна
Задача нахождения кратчайших цепей между всеми парами узлов в сети. Алгоритм Флойда
Рассмотрим сеть, в каждой дуге которой (U,V) поставлено в соответствие действительное число L(U,V), называемое длиной дуги. В зависимости от конкретного приложения это число может быть мерой физического расстояния, времени, стоимости или иного параметра.
Длиной цепи называется сумма длин, взятая по всем дугам этой цепи.
1
2
3
4
5
L0= здесь пишем расстояния из i в j
S0=здесь пишем вершины (справочная)
Алгоритм Флойда
Планируем, что вершины графа G – числа(1,2,…n). Обозначим через L0 - матрица, элементы которой Lij- длина дуги или бесконечность, если дуга не существует.
Введем матрицу S0 - матрица n*n, где элементы Sij=j.
1. Пусть матрицы Lp Sp найдены. Выделим элементы p-той строки и р-того столбца. Назовем их базовой строкой и базовым столбцом соответственно.
2. Построим матрицы Lp+1 Sp+1 по следующим правилам:
а) элементы базовой строки и столбца переписываем без изменений.
б) если элемент Lij>Lip+1+Lp+1j, то Lijp+1=Lp+i1p+Lp+1jp, при этом Sijp+1=Sipp. Если <=, тогда Lijp+1= Lijp и Sijp+1=Sipp.
3. Алгоритм заканчивает свою работу, когда построены матрицы Ln и Sn.Элементы Lijn равны длине кратчайшей цепи из узла i в узел i. И элементы Sijn есть узел, стоящий после узла i в этой цепи.
Замечание 1. Если i-тый элемент базового столбца равен бесконечности, то для ээтой строки шаг 2 выполнять не нужно.
Замечание 2. Если j-тый элемент равен бесконечности, то шаг 2 выполнять не нужно.
Сеть. Потоки на сетях. Задача нахождения потока максимальной мощности. Алгоритм Форда-Фалкерсона
Сеть – конечный граф без циклов и петель, ориентированный в одном общем направлении от вершины S (исток графа) к вершине T (сток графа).
Будем представлять, что по ребрам (i,j) из S в T направляется некоторое вещество (груз, информация и прочее).
Максимальное количество вещества Сij, которое может пропустить ребро (i,j) называется его прорускной способностью. Еесли вершины не соединены, то пропускная способность =0. Поток по ребру (i,j) – количество вещества Fij, проходящего через ребро (i,j) в единицу времени.
Если из i в j направляется поток Fij, то величина обратного потока равна -Fij.
Если С=1, то дуга называется насыщенной.
b
S
t
a
Свойства потоков по ребрам:
1. Поток по каждому ребру не превышает его пропускной способности.
2. Количество вещества, притекающего в вершину равно количеству вещества, вытекающего из нее.
Общее количество вещества, исходящего из истока S совпадает с общим количеством вещества, поступающего в сток T.
Пусть Х некоторое подмножество вершин удовлетворяющих условию S принадл Х, Т не принадл Х. Пара (Х, Х*), где Х* = v/X – разрез, отделяющий S под Т.
Пропускной способностью разреза С(Х,Х*) называется сумма пропускных способностей дуг, составляющих этот разрез.
Дуги, которые идут от S к T(прямые) составляют разрез. Дуги от T к S(обратные) в разрез не входят.
Х=(S,a)
X*=(t,b)
C(X,X*)=С(S,B)+C(A,B)+C(A,T)
Постановка задачи
Задана сеть с фиксированными пропускными способностями дуг. Найти среди всех потоков поток максимальной мощности.
Теорема Форда-Фалкерсона
Мощность максимального потока, пропущенного в сети, равна минимальной пропускной способности разреза.
d
Шаг 0. В процессе работы алгоритма каждая вершина относиться к одному из 3-х множеств: не помеченные вершины, помеченные не просмотренные, просмотренные (окрашенные).
Шаг 1. Пометим вершину S меткой (S+; бесконечность), остальные не помечены.
Шаг 2. Пусть V некоторая помеченная, но не просмотренная вершина. Рассмотрим все соседние с ней не помеченные вершины. Для каждой из таких вершин U возможны следующие ситуации:
а) существует прямая дуга (V,U), f(V,U)<c(V,U), тогда U вершина получает пометку U(V+;С(V,U)-f(V,U))
б) существует обратная дуга (U,V), f(u,v) > 0. Тогда U получает пометку U(V-;f(u,v))
в) существует прямая дуга (V,U) или существует обратная и поток равен 0, тогда вершина U не помечается.
Когда все соседние с V вершины проанализированы, V переходит в множество просмотренных вершин.
Шаг 3. Повторяем шаг 2 до тех пор пока не возникнет одна из следующих ситуаций:
а) все вершины графа разбиты на 2 подмножества(просмотренные и непомеченные(включая Т). Тогда в сети построен макс поток мощности V и мин разрез Х,Х*,
б) если вершина Т получила пометку, то в сети существует увеличивающий путь из S вT, который можно определить идя из Т обратно к S. Для найденного пути определяют величину е(эпсилон) увеличения мощности потока. На прямых дугах пути ST изменяем F на +е на обратных на –е. Мощность равна V предыдущая +е.