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

Решение.

Полагаем:

1 итерация: текущая вершина с постоянной меткой , далее расставляем метки у вершин, достижимых из s

В скобках указана та вершина, через которую модифицируется метка рассматриваемой вершины (на первой итерации везде стоит вершина s). Звездочкой отмечена наименьшая метка из чисел 4, 10, 11. При этом данная метка будет постоянной (в нашем случае 4).

2 итерация: текущая вершина с постоянной меткой , далее меняем метки у вершин с временными метками (меняются лишь метки тех вершин, которые достижимы из вершины y)

Метка а, стоящая в скобке в строчке для , означает, что путь из s в b, проходящий через вершину а, короче пути, состоящего из одной дуги . Аналогично в двух других случаях (2 и 4 строка).

3 итерация: текущая вершина с постоянной меткой ,

4 итерация: текущая вершина с постоянной меткой ,

Имеем 2 одинаковые метки с минимальным значением, поэтому выбираем любую из них (в данном случае )

5 итерация: текущая вершина с постоянной меткой ,

6 итерация: текущая вершина с постоянной меткой ,

 

Вершина t имеет постоянную метку, следовательно 12 – длина кратчайшего пути от s до t. Сам путь находим по меткам, расставленным в скобках. А именно, вершине t предшествует e, что видно из 2 строки 5 итерации. Из 1 строки 4 итерации видим, что e предшествует b. Из 1 строки 2 итерации видим, что b предшествует a. Из 1 строки 1 итерации следует, что a предшествует s. Таким образом, имеем путь s-a-b-e-t. Видим, что его длина 12 (см. рисунок графа).

 

Задача 2. Найти максимальный поток в заданной транспортной сети, используя алгоритм Форда-Фалкерсона. Проверить ответ по теореме Форда-Фалкерсона (найти минимальный разрез графа сети).

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

1°. Положить f =D f =0, c = пропускным способностям заданной транспортной сети.

2°. Переприсвоить: f = f +D f. Вычислить остаточные пропускные способности D c, от­ве­ча­ющие пропускным спо­соб­ностям c и потоку D f.

3°. Для транспортной сети спропускными способностями D c найти путь l из s в t, об­ла­да­ющий максимальной про­пуск­ной способностью. Пусть j — пропускная спо­соб­ность это­го пути. Если j =0 (путь отсутствует), то перейти к пункту 4°; в про­тив­ном случае переопределить добавочный поток D f, полагая

После этого перейти к пункту 2°.

4°. Закончить работу алгоритма. Поток f — ответ задачи.

Пусть функ­ция c описывает пропускные способности исходной сети и f — стан­дарт­ный пред­ста­ви­тель исходного потока. Тогда остаточные пропускные способности D c оп­ре­деляются следующим образом:

D c (u, v)= c (u, v)- f (u, v)+ f (v, u).

 

Пример решения задачи

Задан граф транспортной сети

 

t

s

t

s

Составляем матрицу пропускных способностей:

 

				t
s

 

Находим путь из s в t как можно большей пропускной способности. Путь максимальной пропускной способности можно найти с помощью алгоритма волны, а для небольшой сети – визуально по графу.

 

Примечание1

Если найден путь не максимальной пропускной способности, алгоритм всё равно даст результат, но число шагов может увеличиться.

 

Примечание2

При решении задачи можно использовать как язык матриц, так и язык графов. Ниже приводятся оба способа записи решения.

Путь 1. . Пропускная способность: 10. Составляем матрицу остаточных пропускных способностей/добавочного потока

 

				t
s	0/10
				5/10

 

При отображении данной информации на графе будем использовать формат

A/B/C, где A = c(u,v) – остаточная пропускная способность дуги, B = c(v,u) – остаточная пропускная способность противоположной дуги, C= f(u,v) – добавочный поток через данную дугу. Для дуг, через которые добавочный поток не идёт, третья компонента отсутствует. Остаточные пропускные способности дуг, входящих из s и дуг, исходящих из t вычислять не нужно, на графе они присутствуют для большей наглядности.

 

 

t

s

0/10/10

5/10/10

Путь 2. . Пропускная способность: 7. Матрица остаточных пропускных способностей/добавочного потока:

 

				t
s			23/7
				0/7
		5/7

 

Соответствующий граф:

 

t

s

0/10

23/7/7

5/10

5/7/7

0/7/7

Путь 3. . Пропускная способность: 5. Матрица остаточных пропускных способностей/добавочного потока:

 

				t
s			18/5
				0/5

 

Соответствующий граф:

 

t

s

0/10

18/12/5

5/10

5/7

0/5/5

Путь 4. . Пропускная способность: 5. Матрица остаточных пропускных способностей/добавочного потока:

 

				t
s			18/5
				0/5
	5/5

 

Соответствующий граф:

 

 

t

s

0/10

13/17/5

0/15/5

5/5/5

5/7

0/5

 

 

Путь 5. Отсутствует. Алгоритм завершён.

Максимальный поток:

Находим проверочный разрез (минимальное сечение). Все дуги, входящие в проверочный разрез, должны быть насыщенными (иметь остаточную пропускную способность 0). В нашем случае это дуги Искомый разрез (он может быть не единственным) составляют дуги

Графическое изображение проверочного разреза:

 

t

s

Пропускная способность данного разреза равна 15+5+7=27=П, что соответствует теореме Форда-Фалкерсона.

 

Задача 3. По матрице инцидентности построить остовное дерево графа. Составить список ветвей и хорд графа. Построить граф.

В начале выбираем некоторую вершину графа, например . Тогда получаем разбиение множества вершин графа: . Кроме этого формируем множество ветвей остова. На первом шаге . Далее выбираем очередное ребро остова так, что одна его вершина , а другая Присоединяем к множеству вершину , а к множеству ребро . Проверка на окончание: если , где - множество вершин исходного графа, то алгоритм заканчивает свою работу. Дерево есть искомое остовное дерево.

Рассмотрим работу алгоритма на примере. Пусть матрица инцидентности имеет вид, показанный на рисунке.

1 итерация:

Шаг 1: ,

Шаг 2: , поэтому переходим на начало 1 шага

2 итерация:

Шаг 1: ,

Шаг 2: , поэтому переходим на начало 1 шага

 

3 итерация:

Шаг 1: ,

Шаг 2: , поэтому переходим на начало 1 шага

Далее ребра не могут быть выбраны, так как их вершины принадлежат множеству . Поэтому на следующей итерации выбираем ребро .

4 итерация:

Шаг 1: ,

Шаг 2: , поэтому переходим на начало 1 шага

5 итерация:

Шаг1: ,

Шаг 2: , поэтому переходим на начало 1 шага

6 итерация:

Шаг 1: ,

Шаг 2: , поэтому переходим на начало 1 шага

7 итерация:

Шаг 1: ,

Шаг 2: , конец работы алгоритма.

В результате получаем множество ветвей остова:

Соответственно множество хорд: .

Строим граф (см. матрицу инцидентности). Жирным выделен остов.

 

Задача 4.

Решим задачу4 для автомата, заданного своей диаграммой состояний:

Изобразим таблицу данного автомата (Таблица 1а).

Таблица 1а.

По данному неинициальному автомату Мили строим эквивалентный ему автомат Мура следующим образом:

Автомат содержит состояний, каждое из которых мы будем помечать двумя символами. Состояния автомата обозначим так:

, , , , , , , , , , , .

Функция отметок на состояниях , , , не определена, а её значения на состояниях , , …, задаются с помощью функции выходов автомата : , где , .

То есть , …, .

Функция переходов на состояниях, содержащих в изображении символ , определяется так: , , .

В остальных случаях первый символ имени нового состояния совпадает со считываемым символом входного автомата, а второй символ нового состояния определяется с помощью функции переходов автомата : , где , .

Получим: , , т.к. , и т.д.

Запишем таблицу состояний полученного автомата Мура.

Проверим работу исходного автомата над словом , запустив его из 2 состояния:

Построенный автомат Мура запускаем из состояния

Как видим, результаты обоих автоматов совпали.