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f0, c  пропускным способностям заданной транспортной сети.

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

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



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

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

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

c(u, v)c(u, v)f(u, v) f(v, u).

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

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

---

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

				t
s	10	0	30	0
	0	8	0	15
	0	0	0	7
	10	12	0	5

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

Примечание1

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

Примечание2

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

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

				t
s	0/10	0	30	0
	0	8	0	5/10
	0	0	0	7
	10	12	0	5

---

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

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



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

				t
s	0	0	23/7	0
	0	8	0	5
	0	0	7	0/7
	10	5/7	0	5

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



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

				t
s	0	0	18/5	0
	0	8	0	5
	0	0	7	0
	10	5	0	0/5

---

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



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

				t
s	0	0	18/5	0
	0	8	5	0/5
	0	0	7	0
	5/5	5	0	5

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



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

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

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

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



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

---

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



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

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

1 итерация:

Шаг 1: ,

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

2 итерация:

Шаг 1:

---

Смотрите также файлы

• Лабораторная работа 2 по дисциплине (учебному курсу) Физика 1 (наименование дисциплины (учебного курса) Вариант 2 (при наличии).docx

• Луна. Движение Луны. Солнечные и лунные затмения.docx

• Спецификация теста по дисциплине Методика преподавания казахского языка.docx

• Теоретические аспекты исследования конфликтов в современной организации.docx

• Краткая история метрологии.docx