Алгоритм Форда и Фалкерсона поиска
Максимального потока в сети
Цель работы
Изучить и практически освоить алгоритм Форда и Фалкерсона поиска максимального потока.
Задание
1. Изучить алгоритм Форда и Фалкерсона.
2. Используя алгоритм Форда и Фалкерсона, найти максимальный поток от вершины s к вершине t.
Теоретическая часть
Задача о максимальном потоке состоит в поиске способа пересылки максимального количества единиц потока из источника в сток при условии отсутствия превышения пропускных способностей ребер исходного графа.
Процедуру работы алгоритма рассмотрим на примере.
Пусть задан ориентированный граф, представленный на рис. 6.1. Пропускная способность указана на каждой ребре, например, в числе каналов. Пусть каждое сообщение от источника в сток занимает по одному каналу на каждом из ребер, составляющих путь.
Рис. 6.1. Схема исходного ориентированного графа
Требуется найти максимальный поток П из источника s в стокt , выраженный в числе каналов.
Используется процедура окрашивания ребер и вершин.
Будем считать, что перед началом работы алгоритма во всех ребрах поток является нулевым.
Итерация 1.
Шаг 1 . Окрашивается вершина s, которой присваивается № 1. Просматриваются неокрашенные ребра, инцидентные вершине s .
Могут быть окрашены ребро s - a и вершина a. Вершине а присваивается № 2.
Далее окрашиваются ребро s - b и вершина b. Вершине b присваивается
№ 3. Окрашиваются ребро s - c и вершина c. Вершинеc присваивается № 4.
Шаг 2 . Поскольку № 2 получила вершина а, то необходимо просмотреть неокрашенные ребра, инцидентные этой вершине. В результате такого просмотра окрашиваются ребра a - t и вершина t. Вершина t является стоком. По пути s - a - t может быть пропущен поток, равный П sat = min { vs - a , va - t } = min { 2, 3 }= 2 .
Шаг 3. Уменьшаем пропускную способность ребер s - a и a - t на две единицы. После первой итерации схема графа показана на рис. 6.2.
Рис. 6.2 . Схема графа после итерации 1
Имеющаяся нумерация вершин и окраска ребер и вершин снимается, кроме ребра s - a, на котором vs - a = 0. Реализуется вторая итерация.
Итерация 2.
Шаг 1. Окрашивается вершина s, которой присваивается №1. Просмотр неокрашенных ребер, инцидентных вершине s, приводит к окрашиванию: ребра s - b и вершины b - №2, ребра s - c и вершины с - №3.
Шаг 2. Просматриваются неокрашенные ребра, инцидентные вершине b. Такое ребро одно b - t и вершина t. По пути s - b - t может быть пропущен поток, равный
П = min { v s - b , v b - t } = min {3,2} = 2.
Шаг 3. Уменьшается пропускная способность ребер s - b и b - t на две единицы.
После итерации 2 схема графа показана на рис. 6.3.
Рис. 6.3. Схема графа после итерации 2
Имеющаяся нумерация вершин и окраска ребер, кроме ребра b - t , снимается и выполняется третья итерация.
Итерация 3.
Шаг 1. Окрашивается вершина s - №1. Просмотр неокрашенных ребер, инцидентных s, приводит к окрашиванию:
ребра s - b и вершины b - №2;
ребра s - c и вершины с - №3.
Шаг 2. Просмотр неокрашенных ребер, инцидентных вершине b, приводит к окрашиванию: ребра b-c и вершины с - №3.
Просмотр неокрашенных ребер, инцидентных вершине с , приводит к окрашиванию ребра c – t и вершины t. По пути s – b - c – t может быть пропущен поток, равный
П = min{v s – b , v b-c, vc – t }= min { 1, 1, 2 } = 1.
Уменьшается пропускная способность ребер s – b , b - c и c – t на единицу.
После итерации 3 схема графа показана на рис. 6.4.
Рис. 6.4. Схема графа после итерации 3
Имеющаяся нумерация вершин и окраска ребер, кроме ребер s – b и b - c , на которых число каналов равно нулю, снимается и выполняется четвертая итерации.
Итерация 4.
Шаг 1. Окрашиваются вершина s - №1, неокрашенное инцидентное ребро s - с и вершина с - №2.
Шаг 2. Просмотр неокрашенных ребер, инцидентных вершине c, приводит к окрашиванию ребра с – t и вершины t. По пути s -с- t может быть пропущен поток
П = min { vs – с , vc – t }= min { 3, 1 } = 1 .
Шаг 3. Уменьшается пропускная способность ребер s – с , c – t на 1.
После итерации 4 схема графа приведена на рис. 6.5.
Рис. 6.5. Схема графа после итерации 4
Дальнейшее увеличение сформированного потока невозможно. Работа алгоритма закончена.
Процесс нахождения максимального потока можно представить в виде таблицы итераций (таблица 6.1).
Таблица итераций 6.1
Варианты заданий
Исходные данные по двадцати вариантам представлены в таблице 6.2. Вариант может выбираться, например, по двум последним цифрам номера зачетной книжки или по номеру в журнале группы.
Содержание отчета
1. Описание процедуры расчета по итерациям и шагам.
2. Таблица итераций и величина максимального потока.
Литература
1.Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. – М.: Мир, 1984.
2.Теория сетей связи / Под ред. В.Н.Рогинского . – М., Связь, 1981.
3.Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. – М. Мир, 1966.
Дата добавления: 2019-03-09; просмотров: 324; | Поделиться с друзьями:
|
Мы поможем в написании ваших работ!
с t
