- •Белгородская государственная
- •Введение
- •1. Определение графа
- •2. Представление графов в памяти эвм
- •3. Некоторые понятия и определения теории графов
- •4. Операции над графами
- •5. Связность
- •5.1. Построение покрывающих деревьев
- •5.2. Поиск на графах
- •Поиск в глубину
- •Поиск в ширину
- •5.3. Сильная связность
- •5.4. Транзитивное замыкание орграфа
- •Алгоритм следует из выражения 5.1
- •6. Расстояние
- •6.1. Поиск кратчайших путей между отдельными вершинами графа
- •6.2. Поиск кратчайших путей между каждой парой вершин графа
- •7. Потоки
- •7.1. Условия существования потока
- •7.2. Поиск увеличивающей цепи
- •7.3. Поиск максимального потока
- •7.4. Поиск потока минимальной стоимости
- •7.5. Задача почтальона для орграфа
- •Список литературы
7.1. Условия существования потока
Пусть задан граф G=(V,E), каждой дуге (x,y)Eприписано два числаf(x,y) иc(x,y) – число единиц потока, проходящих по дуге (x,y), и пропускная способность дуги (x,y) соответственно. Пусть в графеGтакже выделено две вершиныsV– источник иtV– сток. Если при этом выполняются следующие условия:
1) (x,y)E; 0f(x,y)c(x,y) (7.1)
2) xV, xs, xt; f(x,y)- f(y,x) = 0 (7.2)
yV yV
3) f(s,y) - f(y,s) = v (7.3)
yV yV
4) f(y,t) - f(t,y) = v (7.4)
yV yV
то говорят, что в графе G задан поток величины v (из источника в сток передается v единиц потока).
Первое условие для каждой дуги (x,y) ограничивает число единиц потока, проходящих по дуге (x,y), пропускной способностью этой дуги.
Второе условие запрещает утечки потока в промежуточных вершинах (в вершинах, отличных от источника и стока), то есть для каждой промежуточной вершины число приходящих единиц потока в эту вершину должно быть равно числу единиц потока, выходящих из неё.
Третье и четвертое условие задает баланс единиц потока, выходящих из источника и приходящих в сток: сколько единиц потока вышло из источника, столько же единиц потока должно прийти в сток.
Пример графа с заданным потоком величины 7 представлен на рис.7.1.
7.2. Поиск увеличивающей цепи
Пусть задан граф G=(V,E), в котором существует некоторый поток из вершины s в вершину t. Требуется ответить на вопрос: можно ли увеличить поток из s в t?
Цепь, по которой могут быть посланы дополнительные единицы потока, называется увеличивающей цепью.
Алгоритм 5. Алгоритм поиска увеличивающей цепи
Шаг 1. Разбить множество дуг графа G=(V,E) на группы:
Группа N – дуги графа, в которых поток не может изменяться (дуги с нулевой пропускной способностью или дуги, в которых по каким-либо причинам, например, техническим, число проходящих единиц потока должно быть постоянным).
Группа I – дуги, в которых поток может увеличиваться, то есть дуги (x,y), в которых число проходящих единиц потока f(x,y) меньше пропускной способности c(x,y).
Группа R – дуги, в которых поток может уменьшаться, то есть дуги (x,y), в которых число проходящих единиц потока f(x,y) больше нуля.
Шаг 2. Дуги множества N из дальнейшего рассмотрения исключить. Окрасить вершину s.
Шаг 3. Окрашивать дуги и вершины в соответствии с приводимыми ниже правилами до тех пор, пока либо не будет окрашена вершина t, либо окраска новых вершин и дуг станет невозможной.
Правила окрашивания вершины y и дуг (x,y),(y,x) при уже окрашенной вершине x:
если (x,y)I, то окрашивается вершина y и дуга (x,y);
если (y,x)R, то окрашивается вершина y и дуга (y,x);
в противном случае окрашивание вершины y и дуги (x,y) не производится.
Если дуга окрашивается по первому правилу, то она называется прямой дугой. Если дуга окрашивается по второму правилу, то она называется обратной дугой.
Шаг 4. Если вершина t окрашена, то выбрать окрашенные дуги, образующие цепь, соединяющую вершины s и t. Такая цепь является увеличивающей. В противном случае увеличивающей цепи в графе нет.
Для графа, изображенного на рис.7.1, выполнение первого шага алгоритма даст следующее разбиение дуг графа на группы N,I,R: N={(5,2)}, I={(1,2), (2,3), (3,5), (4,6)}, R={(1,2), (1,3), (2,4), (3,5), (4,3), (4,6), (5,6)}. После выполнения третьего шага алгоритма будут окрашены следующие дуги (1,2), (2,3), (3,5), (4,3), (4,6), см. рис. 7.2. После выполнения четвертого шага алгоритма получим увеличивающую цепь =(V,E), V={1,2,3,4,6}, E={(1,2), (2,3), (4,3), (4,6)}.
После того, как увеличивающая цепь =(V,E) найдена, производится увеличение потока вдоль найденной цепи по правилам:
Находится величина
t = min {(a,b)}
(a,b)E
Смысл чисел (a,b) зависит от того, какой дугой – прямой или обратной – является дуга (a,b). Для прямых дуг (a,b) – максимальная величина, на которую может быть увеличен поток по дуге (a,b), то есть (a,b)=c(a,b)-f(a,b). Для обратных дуг (a,b) – максимальная величина, на которую может быть уменьшен поток по дуге (a,b), то есть (a,b)=f(a,b).
2. В каждой прямой дуге (a,b)E число проходящих единиц потока f(a,b) увеличивается на t единиц. В каждой обратной дуге (a,b)E число проходящих единиц потока f(a,b) уменьшается на t единиц. В результате таких действий суммарный поток в графе увеличивается на t единиц.
Увеличим поток в графе, изображенном на рис.7.1, вдоль увеличивающей цепи =(V,E), см. рис.7.2.
t=min{c(1,2)-f(1,2), c(2,3)-f(2,3), f(4,3), c(4,6)-f(4,6)}=
min{8-4,3-0,2,3-1}=2.
f(1,2) = f(1,2)+t = 4+2 = 6, f(2,3) = f(2,3)+t = 0+2 = 2,
f(4,3) = f(4,3)-t = 2-2 = 0, f(4,6) = f(4,6)+t = 2+2 = 4.
Увеличенный таким образом поток показан на рис. 7.3. В обратной дуге (4,3) поток уменьшается на две единицы, эти две единицы возвращаются по прямой дуге (4,6) в сток, а соответствующая нехватка потока в вершине 3 компенсируется за счет двух единиц, поступающих по прямым дугам (1,2) и (2,3). Таким образом, суммарный поток из источника в сток увеличился на 2 единицы.