Пример решения задачи о максимальном потоке и минимальном разрезе

Рассмотрим конкретную задачу о нахождении максимального потока в сети.

Дана сеть 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 − для задачи о кратчайшем пути. Интервалы весов указывают границы изменения пропускных способностей и длин дуг.