Алгоритм знаходження максимального потоку

Розглянемо граф з пропускними спроможностями дуг ,з джерелом і стоком , . Потоки в дугах позначимо .

1. Розстановка поміток

Помітка будь-якої вершини складається з двох частин і може бути двох видів: або , де “+” означає, що потік допускає збільшення вздовж дуги , а “-“ – зменшення потоку вздовж дуги .

- максимальна величина додаткового потоку, який може протікати від до вздовж побудованого ланцюга потоку.

Вершина може знаходитись в одному з трьох станів:

1) вершині приписана помітка, і вершина проглянута (тобто, проаналізовані усі суміжні з нею вершини);

2) помітка приписана, але вершина не проглянута;

3) вершина не має помітки.

Крок 1

Присвоїти вершині помітку .

Крок 2

Взяти деяку непроглянуту вершину з поміткою; Нехай її помітка буде :

а) кожній непоміченій вершині , для якої , присвоїти помітку , де ;

б) кожній непоміченій вершині , для якої , присвоїти помітку , де .

Тепер вершина і помічена, і проглянута, а вершини, помітки яким просвоєні, являються не проглянутими.

Крок 3

Повторювати крок 2 доти, поки або вершина буде помічена, і тоді перейти до кроку 4, або буде не поміченою і ніяких інших поміток не можна буде розставити. У цьому випадку алгоритм закінчує роботу з максимальним вектором потоку.

2. Збільшення потоку

Крок 4

Покласти і перейти до кроку 5.

Крок 5

а) якщо помітка в вершині має вигляд , то змінити потік вздовж дуги з на ;

б) якщо помітка в вершині має вигляд , то змінити потік вздовж дуги з на .

Крок 6

Якщо , то стерти усі помітки і повернутися до кроку 1, знову розставляючи помітки, але використовуючи вже покращений потік, знайдений на кроці 5.

Якщо , то повернутися до кроку 5, вважаючи .

Питання для самоперевірки та вправи

1. Дайте поняття мережі, транспортної мережі. Наведіть приклади.

2. Що називається розрізом мережі, мінімальним розрізом ? Як обчислюється пропускна спроможність розрізу ?

3. Сформулюйте теорему Форда-Фалкерсона. Де застосовується ця теорема ?

4. Опишіть алгоритм знаходження максимального потоку.

Лекція №26 Знаходження максимального потоку в транспортній мережі. Задача відшукання найкоротшого та критичного шляху між двома заданими вершинами

Знайдемо максимальний потік від вершини до вершини в мережі, зображеній на малюнку 26.1.

Рис. 26.1 – Транспортна мережа

Розв’язок:

За початковий візьмемо потік з нульовими значеннями на усіх дугах .

Крок 1.

Припишемо вершині помітку .

Крок 2.

а) множина непомічених вершин виду . Вершині приписується помітка: .

Вершині - .

б) множина непомічених вершин виду .

Отже, тепер помічена і проглянута, вершини і помічені, але не проглянуті, а усі інші вершини не помічені. Повторюємо крок 2, починаючи з вершини (вершини проглядаються у порядку збільшення їх індексів).

Множина непомічених вершин:

а) .

Помітка для : .

б) .

Розглянемо вершину . Множина непомічених вершин для неї і :

Для вершини поміткою буде:

.

Для вершини : .

Беручи вершину ніяких поміток поставити не можемо, оскільки суміжні з вершини вже помічені.

Розглянемо вершину і одержимо наступні помітки:

Для : .

Для : .

Для : .

Переходимо до кроків 4 і 5.

. Оскільки помітка - потік вздовж дуги збільшуємо на , отже . Потік .

Рис. 26.2 – Потоки після першої ітерації

Стираємо усі помітки і повертаємося до кроку 1 для другого проходу і одержуємо нові помітки:

Рис. 26.3 - Потоки і помітки після другої ітерації

Рис. 26.4 - Потоки і помітки після третьої ітерації.

Рис. 26.5 - Потоки і помітки після четвертої ітерації

Рис. 26.6 - Потоки і помітки після п’ятої ітерації

Рис. 26.7 - Потоки і помітки після шостої ітерації

Потік, який відповідає дугам , є максимальним і його значення дорівнює .

Задача відшукання найкоротшого та критичного шляху між двома заданими вершинами і .

Нехай - помітка вершини .

Присвоєння початкових значень.

Крок 1 Покласти і вважати цю помітку постійною. Покласти для усіх і вважати ці помітки тимчасовими. Покласти .

Обновлення поміток.

Крок 2 Для всіх , помітки яких тимчасові, змінити помітки у відповідності з виразом .

Перетворення поміток у постійну.

Крок 3 Серед усіх вершин з тимчасовими помітками знайти таку, для якої .

Крок 4 Вважати помітку вершини постійною і покласти .

Крок 5 Якщо , то - довжина найкоротшого шляху. Якщо , то перейти до кроку 2.

Наприклад: Знайти найкоротший шлях від вершини до вершини для графа , зображеного на малюнку 11.8.

Рис. 26.8 – граф

Матриця ваги графа представлена таблицею26.1

Таблиця 26.1 –Матриця ваги графа

		10					3	6	12
	10		18				2		13
		18		25		20			7
			25		5	16	4
				5		10		23
			20	16	10		14		9
	3	2		4		14			24
	6				23				5
	12	13	7			9	24	5

Розв’язок:

Крок 1 -помітка постійна. для будь - якого , .

Перша ітерація:

Крок 2 . Помітки тимчасові і дорівнюють нескінченості. Обновлюємо помітку вершини :

. Отже, .

Аналогічно знаходимо:

.

Крок 3 Знаходимо , тобто , де це помітки вершин .

Крок 4 Вершина одержує постійну помітку .

Крок 5 Не всі вершини мають постійну помітку, тому переходимо до кроку 2.

Друга ітерація:

Крок 2 . .

.

Крок 3 Знаходимо - це вершина .

Крок 4 Вершина одержує постійну помітку .

Крок 5 Переходимо до кроку 2.

Обчислення по кожній ітерації зручно зводити в таблицю 11.2.

Третя ітерація:

Четверта ітерація:

На четвертій ітерації алгоритм закінчує роботу, оскільки відповідає стоку і довжина найкоротшого шляху дорівнює .

Таблиця 11.2 – Ітерації знаходження найкоротшого шляху в графі

	0
	0	10					3^*	6	12
	0	5^*		7		17	3^*	6	12
	0	5^*	23	7		17	3^*	6^*	12
	0	5^*	23	7^*	29	17	3^*	6^*	11

Для того, щоб знайти критичний шлях в алгоритмі знаходження найкоротшого шляху, треба внести зміни в кроці 2 і 3.

Крок 2 .

Крок 3 .

Цей алгоритм використовується, наприклад, для виявлення максимального часу переходу від одного виду роботи до іншого. В цьому випадку матриця ваги буде представляти собою час переходу від -ї до -ї роботи.