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

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

Дана сеть G(V,E) (рис.1) с источником s и стоком t. Пропускные способности дуг указаны. Найти максимальный поток из s в t.

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

Рис.1

Решение.

Подготовительный этап.

М(s)=(s, +∞); все дуговые потоки нулевые − Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru для любой дуги Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru .

Вершина s помечена и не просмотрена, остальные вершины не помечены.

Этап расстановки пометок

Рассматриваем вершину s:

М(1)=( Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,10); М(2)=( Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,8)

Вершина s помечена и просмотрена, вершины 1, 2 помечены и непросмотрены.

Рассматриваем вершину 1:

М(3)=(1 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , 5)

Вершина 1 помечена и просмотрена.

Рассматриваем вершину 2:

М(4)=(2 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , 8)

Вершина 2 помечена и просмотрена.

Рассматриваем вершину 3:

М(t)=(3 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , 5)

Помечена вершина t, переходим на следующий этап.

Этап изменения потока

Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru =5

Путь, по которому мы пришли из вершины s в вершину t:

( Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,1 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,3 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , t)

Величина потока r = 5.

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

Рис.2

В прямоугольниках (рис.2) указаны дуговые потоки после этого этапа, все остальные дуговые потоки равны нулю.

Этап расстановки пометок

Рассматриваем вершину s:

М(1)=( Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,5); М(2)=( Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,8)

Вершина s помечена и просмотрена, вершины 1, 2 помечены и непросмотрены.

Рассматриваем вершину 1:

Вершину 3 из вершины 1 пометить нельзя.

Вершина 1 помечена и просмотрена.

Рассматриваем вершину 2:

М(4)=(2 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , 8)

Вершина 2 помечена и просмотрена.

Рассматриваем вершину 4:

М(t)=(4 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , 8)

Вершина 4 помечена и просмотрена. Пометили вершину t.

Этап изменения потока

Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru =8

Путь, по которому мы пришли из вершины s в вершину t:

( Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,2 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,4 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , t)

Величина потока r = r+8=13.

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

Рис.3

Дуговые потоки после этого этапа указаны на рис.3, все остальные дуговые потоки равны нулю.

Этап расстановки пометок

Рассматриваем вершину s:

М(1)=( Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,5)

Вершину 2 из вершины s пометить нельзя.

Вершина s помечена и просмотрена, вершина 1 помечена и непросмотрена.

Рассматриваем вершину 1.

М(2)=( Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,5)

Вершины 3 и 4 из вершины 1 пометить нельзя.

Вершина 1 помечена и просмотрена, вершина 2 помечена и непросмотрена.

Рассматриваем вершину 2.

М(4)=(2 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , 2)

Вершина 2 помечена и просмотрена, вершина 4 помечена и непросмотрена.

Рассматриваем вершину 4.

М(t)=(4 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , 2)

Вершину 3 из вершины 1 пометить нельзя.

Вершина 4 помечена и просмотрена. Пометили вершину t.

Этап изменения потока

Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru =2

Путь, по которому мы пришли из вершины s в вершину t:

( Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , 1 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , 2 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,4 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , t)

Величина потока r = r+2=15.

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

Рис.4

Дуговые потоки после этого этапа указаны на рис.4, все остальные дуговые потоки равны нулю.

Этап расстановки пометок

Рассматриваем вершину s:

М(1)=( Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ,3)

Вершину 2 из вершины s пометить нельзя.

Вершина s помечена и просмотрена, вершина 1 помечена и непросмотрена.

Рассматриваем вершину 1.

М(2)=( Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , 3)

Вершины 3 и 4 из вершины 1 пометить нельзя.

Вершина 1 помечена и просмотрена, вершина 2 помечена и непросмотрена.

Рассматриваем вершину 2.

Из вершины 2 других вершин пометить не удается.

На этом этапе других вершин пометить не удалось, следовательно максимальный поток найден r Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru =15, а минимальный разрез имеет следующий вид:

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

Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru = Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru

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

Пусть задана сеть G = Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru с множеством вершин N, где Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , и множеством дуг U, т.е. задан ориентированный граф с n + 1 вершиной, в котором выделены две вершины – вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги (i; j) задано число Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , называемое длиной дуги. Длиной пути называется сумма длин дуг этого пути (если длины дуг не заданы, то длина пути определяется как число дуг пути, т.е. Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ). Задача о кратчайшем пути состоит в поиске минимального (кратчайшего) по длине пути из вершины с номером 0 до вершины с номером n.

В дальнейшем будем предполагать:1) сеть не имеет контуров; 2) из вершины с номером 0 можно попасть (по некоторому пути) в любую другую вершину сети, а из любой вершины сети можно попасть (по некоторому пути) в вершину с номером n; 3) нулевая вершина не имеет входящих дуг, а вершина n не имеет выходящих дуг.

Сеть G не имеет контуров, поэтому всегда можно пронумеровать вершины таким образом, что для любой дуги (i, j) имеет место соотношение: i<j. Такая нумерация вершин сети называется правильной.

Если сеть G имеет правильную нумерацию (вершин), то кратчайший путь можно найти алгоритмом 1. В процессе работы этого алгоритма каждая вершина получает метку − вершина i получает метку M(i) =(j, Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ), где первая часть метки указывает номер вершины, из которой помечена вершина i, а величина Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru указывает длину кратчайшего пути из нулевой вершины в данную вершину.

Алгоритм 1.

Шаг 0: помечаем нулевую вершину − M(0) = (0, Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ), где Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru = 0.

Шаг k, где Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru : помечаем вершину с номером k меткой M(k) =(j, Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ), где Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru (т.е. минимум в соотношении Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru достигается на вершине j ).

Длина кратчайшего пути равна Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru . Используя первую часть метки вершины, двигаемся в обратном направлении от вершины с номером n до вершины с номером 0 и тем самым определяем путь, по которому мы пришли из вершины 0 в вершину n. В результате мы получаем последовательность вершин: Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru . (Такой способ определения пути называется методом обратного хода.) Это и есть кратчайший путь.

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

Рис. 1

На рисунке 1 приведен пример применения алгоритма 1 для определения кратчайшего пути: числа у дуг равны длинам дуг, метки вершин помещены в круглые скобки, кратчайший путь выделен жирными линиями.

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

Алгоритм 2.

1.Полагаем, что i = 0. Находим в сети G вершину, не имеющую входящих дуг, и присваиваем ей метку i.

2. Если i = n, то правильная нумерация вершин найдена, заменяем исходную нумерацию вершин правильной − конец работы алгоритма.

В противном случае полагаем i = i + 1.

3. Находим в сети G любую вершину, которая не имеет входящих дуг, выходящих из помеченных вершин, и присваиваем ей метку i. Возвращаемся на шаг 2.

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

Рис. 2.

На рисунке 2 приведен пример применения алгоритма 2 для отыскания правильной нумерации вершин сети: метки вершин − номера правильной нумерации помещены в круглые скобки.

Следующий алгоритм дает возможность определить кратчайший путь в общем случае − при произвольной нумерации вершин. В процессе работы этого алгоритма каждая вершина получает метку − вершина i получает метку M(i) =(j, Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ), где первая часть метки указывает номер вершины, из которой помечена вершина i, а величина Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru указывает длину некоторого пути из нулевой вершины в данную вершину. После завершения работы алгоритма величина Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru будет равна длине кратчайшего пути из нулевой вершины в данную вершину.

Алгоритм 3 (алгоритм Дейкстры).

Шаг 0. Полагаем, что множество вершин Q − это пустое множество. Помечаем нулевую вершину: M(0) = (0, Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ), где Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru = 0, т.е. M(0) = (0,0). Заносим нулевую вершину в множество Q. Все остальные вершины получают метку − M(i) =(0, Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ), т.е. Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru = Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru (это означает, что вершина i помечена из вершины 0 и, предположительно, находится от нее на бесконечном расстоянии).

Шаг 1. Для каждой вершины k Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru Q вычисляем величину Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru (минимум берется по всем вершинам i таким, что i Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru Q и в сети имеется дуга (i,k), и этот минимум достигается на вершине j). Среди всех таких вершин k выбираем ту, которая имеет минимальную величину Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , помечаем ее − M(k) =(j, Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ) и заносим в множество Q.

Подобную процедуру повторяем до тех пор, пока не будет помечена вершина n.

Длина кратчайшего пути равна Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru . Используя первую часть метки вершины, находим сам кратчайший путь методом обратного хода.

Конец работы алгоритма.

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

Рис.3.

Применим алгоритм Дейкстры к графу на рис. 3, числа в кружочках равны длинам дуг.

Шаг 0.

M(0) = (0,0),

M(i) =(0, Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ) для i = 1,2,…,n

Q = {0}

Шаг 1.

Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ; Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ;

M(3) =(0, 3)

Q = {0, 3}

Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ; Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ;

M(2) =(3, 8);

Q = {0, 3, 2}

Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ; Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ;

Q = {0, 3, 2, 4}

Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ; Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ;

Q = {0, 3, 2, 4, 1}

Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru ;

Q = {0, 3, 2, 4, 1, 5}

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

Рис.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 Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru , второй − графа G Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru . В паре (i,j) первое число − число вершин, второе число − число дуг.

G Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru − сеть для задачи о максимальном потоке, G Пример решения задачи о максимальном потоке и минимальном разрезе - student2.ru − для задачи о кратчайшем пути. Интервалы весов указывают границы изменения пропускных способностей и длин дуг.

Наши рекомендации