Пример решения задачи о максимальном потоке и минимальном разрезе
Рассмотрим конкретную задачу о нахождении максимального потока в сети.
Дана сеть G(V,E) (рис.1) с источником s и стоком t. Пропускные способности дуг указаны. Найти максимальный поток из s в t.
Рис.1
Решение.
Подготовительный этап.
М(s)=(s, +∞); все дуговые потоки нулевые − 
для любой дуги 
.
Вершина s помечена и не просмотрена, остальные вершины не помечены.
Этап расстановки пометок
Рассматриваем вершину s:
М(1)=( 
,10); М(2)=( ,8)
Вершина s помечена и просмотрена, вершины 1, 2 помечены и непросмотрены.
Рассматриваем вершину 1:
М(3)=(1 
, 5)
Вершина 1 помечена и просмотрена.
Рассматриваем вершину 2:
М(4)=(2 , 8)
Вершина 2 помечена и просмотрена.
Рассматриваем вершину 3:
М(t)=(3 , 5)
Помечена вершина t, переходим на следующий этап.
Этап изменения потока
=5
Путь, по которому мы пришли из вершины s в вершину t:
( ,1 ,3 , t)
Величина потока r = 5.
Рис.2
В прямоугольниках (рис.2) указаны дуговые потоки после этого этапа, все остальные дуговые потоки равны нулю.
Этап расстановки пометок
Рассматриваем вершину s:
М(1)=( ,5); М(2)=( ,8)
Вершина s помечена и просмотрена, вершины 1, 2 помечены и непросмотрены.
Рассматриваем вершину 1:
Вершину 3 из вершины 1 пометить нельзя.
Вершина 1 помечена и просмотрена.
Рассматриваем вершину 2:
М(4)=(2 , 8)
Вершина 2 помечена и просмотрена.
Рассматриваем вершину 4:
М(t)=(4 , 8)
Вершина 4 помечена и просмотрена. Пометили вершину t.
Этап изменения потока
=8
Путь, по которому мы пришли из вершины s в вершину t:
( ,2 ,4 , t)
Величина потока r = r+8=13.
Рис.3
Дуговые потоки после этого этапа указаны на рис.3, все остальные дуговые потоки равны нулю.
Этап расстановки пометок
Рассматриваем вершину s:
М(1)=( ,5)
Вершину 2 из вершины s пометить нельзя.
Вершина s помечена и просмотрена, вершина 1 помечена и непросмотрена.
Рассматриваем вершину 1.
М(2)=( 
,5)
Вершины 3 и 4 из вершины 1 пометить нельзя.
Вершина 1 помечена и просмотрена, вершина 2 помечена и непросмотрена.
Рассматриваем вершину 2.
М(4)=(2 
, 2)
Вершина 2 помечена и просмотрена, вершина 4 помечена и непросмотрена.
Рассматриваем вершину 4.
М(t)=(4 , 2)
Вершину 3 из вершины 1 пометить нельзя.
Вершина 4 помечена и просмотрена. Пометили вершину t.
Этап изменения потока
=2
Путь, по которому мы пришли из вершины s в вершину t:
( , 1 
, 2 ,4 , t)
Величина потока r = r+2=15.
Рис.4
Дуговые потоки после этого этапа указаны на рис.4, все остальные дуговые потоки равны нулю.
Этап расстановки пометок
Рассматриваем вершину s:
М(1)=( ,3)
Вершину 2 из вершины s пометить нельзя.
Вершина s помечена и просмотрена, вершина 1 помечена и непросмотрена.
Рассматриваем вершину 1.
М(2)=( , 3)
Вершины 3 и 4 из вершины 1 пометить нельзя.
Вершина 1 помечена и просмотрена, вершина 2 помечена и непросмотрена.
Рассматриваем вершину 2.
Из вершины 2 других вершин пометить не удается.
На этом этапе других вершин пометить не удалось, следовательно максимальный поток найден r 
=15, а минимальный разрез имеет следующий вид:
= 
Задача о кратчайшем пути.
Пусть задана сеть G = 
с множеством вершин N, где 
, и множеством дуг U, т.е. задан ориентированный граф с n + 1 вершиной, в котором выделены две вершины – вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги (i; j) задано число 
, называемое длиной дуги. Длиной пути называется сумма длин дуг этого пути (если длины дуг не заданы, то длина пути определяется как число дуг пути, т.е. 
). Задача о кратчайшем пути состоит в поиске минимального (кратчайшего) по длине пути из вершины с номером 0 до вершины с номером n.
В дальнейшем будем предполагать:1) сеть не имеет контуров; 2) из вершины с номером 0 можно попасть (по некоторому пути) в любую другую вершину сети, а из любой вершины сети можно попасть (по некоторому пути) в вершину с номером n; 3) нулевая вершина не имеет входящих дуг, а вершина n не имеет выходящих дуг.
Сеть G не имеет контуров, поэтому всегда можно пронумеровать вершины таким образом, что для любой дуги (i, j) имеет место соотношение: i<j. Такая нумерация вершин сети называется правильной.
Если сеть G имеет правильную нумерацию (вершин), то кратчайший путь можно найти алгоритмом 1. В процессе работы этого алгоритма каждая вершина получает метку − вершина i получает метку M(i) =(j, 
), где первая часть метки указывает номер вершины, из которой помечена вершина i, а величина указывает длину кратчайшего пути из нулевой вершины в данную вершину.
Алгоритм 1.
Шаг 0: помечаем нулевую вершину − M(0) = (0, 
), где = 0.
Шаг k, где 
: помечаем вершину с номером k меткой M(k) =(j, 
), где 
(т.е. минимум в соотношении 
достигается на вершине j ).
Длина кратчайшего пути равна 
. Используя первую часть метки вершины, двигаемся в обратном направлении от вершины с номером n до вершины с номером 0 и тем самым определяем путь, по которому мы пришли из вершины 0 в вершину n. В результате мы получаем последовательность вершин: 
. (Такой способ определения пути называется методом обратного хода.) Это и есть кратчайший путь.
Рис. 1
На рисунке 1 приведен пример применения алгоритма 1 для определения кратчайшего пути: числа у дуг равны длинам дуг, метки вершин помещены в круглые скобки, кратчайший путь выделен жирными линиями.
Правильная нумерация вершин произвольной сети, не имеющей контуров, определяется алгоритмом 2. В процессе работы этого алгоритма каждая вершина получает метку − её номер при правильной нумерации вершин. Перед началом работы алгоритма все вершины не помечены.
Алгоритм 2.
1.Полагаем, что i = 0. Находим в сети G вершину, не имеющую входящих дуг, и присваиваем ей метку i.
2. Если i = n, то правильная нумерация вершин найдена, заменяем исходную нумерацию вершин правильной − конец работы алгоритма.
В противном случае полагаем i = i + 1.
3. Находим в сети G любую вершину, которая не имеет входящих дуг, выходящих из помеченных вершин, и присваиваем ей метку i. Возвращаемся на шаг 2.
Рис. 2.
На рисунке 2 приведен пример применения алгоритма 2 для отыскания правильной нумерации вершин сети: метки вершин − номера правильной нумерации помещены в круглые скобки.
Следующий алгоритм дает возможность определить кратчайший путь в общем случае − при произвольной нумерации вершин. В процессе работы этого алгоритма каждая вершина получает метку − вершина i получает метку M(i) =(j, ), где первая часть метки указывает номер вершины, из которой помечена вершина i, а величина указывает длину некоторого пути из нулевой вершины в данную вершину. После завершения работы алгоритма величина будет равна длине кратчайшего пути из нулевой вершины в данную вершину.
Алгоритм 3 (алгоритм Дейкстры).
Шаг 0. Полагаем, что множество вершин Q − это пустое множество. Помечаем нулевую вершину: M(0) = (0, ), где = 0, т.е. M(0) = (0,0). Заносим нулевую вершину в множество Q. Все остальные вершины получают метку − M(i) =(0, 
), т.е. = (это означает, что вершина i помечена из вершины 0 и, предположительно, находится от нее на бесконечном расстоянии).
Шаг 1. Для каждой вершины k 
Q вычисляем величину 
(минимум берется по всем вершинам i таким, что i 
Q и в сети имеется дуга (i,k), и этот минимум достигается на вершине j). Среди всех таких вершин k выбираем ту, которая имеет минимальную величину 
, помечаем ее − M(k) =(j, ) и заносим в множество Q.
Подобную процедуру повторяем до тех пор, пока не будет помечена вершина n.
Длина кратчайшего пути равна . Используя первую часть метки вершины, находим сам кратчайший путь методом обратного хода.
Конец работы алгоритма.
Рис.3.
Применим алгоритм Дейкстры к графу на рис. 3, числа в кружочках равны длинам дуг.
Шаг 0.
M(0) = (0,0),
M(i) =(0, ) для i = 1,2,…,n
Q = {0}
Шаг 1.
; 
;
M(3) =(0, 3)
Q = {0, 3}
; 
;
M(2) =(3, 8);
Q = {0, 3, 2}
; 
;
Q = {0, 3, 2, 4}
; 
;
Q = {0, 3, 2, 4, 1}
;
Q = {0, 3, 2, 4, 1, 5}
Рис.4
На рисунке 4 приведен пример применения алгоритма 1 для определения кратчайшего пути: числа у дуг равны длинам дуг, метки вершин помещены в круглые скобки, кратчайший путь выделен жирными линиями.
Варианты индивидуальных заданий
Каждый студент должен произвольно задать сеть с характеристиками, выбранными соответственно номеру в журнале.
Состав отчета работы
1. Краткие теоретические сведения.
2. Индивидуально построенную сеть с вариантом входных данных.
3. Полные расчеты на сети для задач поиска максимального потока и кратчайшего пути.
4. Выводы из лабораторной работы.
Исходные данные:
| Интервалы весов | Группа 1 | Группа 2 | ||||
| G1 | G2 | G1 | G2 | |||
| (i,j) | (i,j) | (i,j) | (i,j) | |||
| 1−7 | (7;12) | (6;13) | (7;11) | (7;12) | ||
| 8−15 | (7;13) | (7;9) | (6;10) | (7;13) | ||
| 10−18 | (7;11) | (7;10) | (6;11) | (7;11) | ||
| 1−7 | (6;10) | (6;9) | (6;12) | (6;10) | ||
| 8−15 | (6;11) | (6;12) | (6;13) | (6;11) | ||
| 10−18 | (6;12) | (6;13) | (7;9) | (6;12) | ||
| 1−7 | (6;13) | (7;9) | (7;10) | (6;13) | ||
| 8−15 | (7;9) | (7;10) | (6;9) | (7;9) | ||
| 10−18 | (7;10) | (6;9) | (6;12) | (7;10) | ||
| 1−7 | (6;9) | (7;12) | (6;13) | (6;9) | ||
| 8−15 | (6;10) | (7;13) | (7;9) | (7;12) | ||
| 10−18 | (7;13) | (7;11) | (7;10) | (7;13) | ||
| 1−7 | (7;11) | (6;10) | (7;13) | (7;11) | ||
| 8−15 | (6;10) | (6;11) | (7;11) | (6;10) | ||
| 10−18 | (6;11) | (6;12) | (6;10) | (6;11) | ||
| 1−7 | (6;12) | (6;13) | (6;11) | (6;12) | ||
| 8−15 | (6;13) | (7;9) | (6;12) | (7;9) | ||
| 10−18 | (7;9) | (7;11) | (6;13) | (6;9) | ||
| 1−7 | (7;10) | (6;10) | (7;9) | (7;10) | ||
| 1−7 | (6;9) | (6;11) | (7;10) | (6;9) | ||
| 8−15 | (6;12) | (6;14) | (6;9) | (6;12) | ||
| 10−18 | (6;13) | (6;13) | (7;12) | (6;13) | ||
| 1−7 | (7;9) | (7;9) | (6;2) | (7;9) | ||
| 8−15 | (7;10) | (7;10) | (6;4) | (7;10) | ||
| 10−18 | (6;9) | (7;11) | (6;1) | (6;9) |
Первый столбец − параметры графа G 
, второй − графа G 
. В паре (i,j) первое число − число вершин, второе число − число дуг.
G − сеть для задачи о максимальном потоке, G − для задачи о кратчайшем пути. Интервалы весов указывают границы изменения пропускных способностей и длин дуг.