Введение
Исследование предметной области 6
1.1 Граф 6
1.2 Сеть и поток 8
1.3 Остаточный граф 9
1.4 Увеличивающий путь 11
1.5 Разрыв сети 12
1.6 Задача о максимальном потоке 13
1.7 Теорема Форда-Фалкерсона 15
2 Программная реализация алгоритмов 19
2.1 Алгоритм Форда-Фалкерсона 19
2.2 Алгоритм Эдмондса-Карпа 25
2.3 Алгоритм Диница 28
3 Тестирование программы и анализ результатов 31
3.1 Описание программных средств 31
3.2 Сравнительный анализ результатов 32
Заключение 38
Список используемой литературы 39
Приложение А Алгоритм Форда-Фалкерсона 41
Приложение Б Алгоритм Эдмондса-Карпа 42
Приложение В Алгоритм Диница
В повседневной жизни нас окружает множество различных типов сетей, включая электрические, телефонные, кабельные, автомобильные, железнодорожные, производственные и компьютерные. Сеть состоит из узлов и соединяющих их звеньев, по которым движется определенный объект. Процесс происходит в условиях определенных ограничений на каждом участке. Для достижения наиболее эффективного использования подобных сетей, необходимо решить задачу нахождения максимального потока, что позволит с максимально возможной нагрузкой эксплуатировать сеть и следовательно, получать максимально возможный результат.
Задача нахождения максимального потока в транспортной сети не теряет своей актуальности в современном мире. При проектировании сети в реальном пространстве, необходимо проведение анализа свойств будущего объекта.
В качестве объекта исследования выступает задача о поиске максимального потока. Предметом исследования являются алгоритмы для нахождения максимального потока.
Целью данной работы является разработка и программная реализация алгоритмов решения задачи о максимальном потоке на языке Python и дополнительной библиотеки pydot. А также проведение сравнительного анализа на основе полученных результатов.
Для достижения поставленной цели необходимо решить ряд задач:
1. Изучить область объекта исследования;
2. Исследовать основные алгоритмы для решения задачи о максимальном потоке;
3. Реализовать исследованные алгоритмы на языке Python;
4. Провести анализ результатов;
5. Сделать вывод о проведенной работе.
В процессе выполнения задания были исследованы методы поиска максимального потока в транспортных сетях.
После изучения необходимых источников литературы, были реализованы алгоритмы для решения задачи о поиске максимального потока. Во время этого процесса были пополнены знания о возможностях языка программирования Python и его дополнительной библиотеке pydot.
В ходе работы был выполнен ряд поставленных в начале работы задач:
1. Изучена область объекта исследования;
2. Разобрана теорема о максимальном потоке и минимальном разрезе
3. Исследованы алгоритмы поиска максимального потока;
4. Выполнена реализация программы;
5. Проведен сравнительный анализ полученных результатов;
6. Сформирован вывод о проведенной работе.
Для проведения сравнительного анализа полученных результатов, был выполнен поиск максимального потока на основе различных входящих данных графа, представленных в виде матриц смежности.
Рассматриваемые матрицы отличались по количеству ребер и вершин. Это потребовалось для достижения необходимого результата и формирования понимания о недостатках одних и преимуществ других алгоритмов в различных ситуациях. Граф сети был представлен в виде матрицы смежности, в ячейках которой были указаны пропускные способности каждого из ребер.
В исследуемых алгоритмах, для обхода узлов сети были использованы алгоритм поиска в глубину и алгоритм поиска в ширину.
Все поставленные задачи были выполнены. Созданная программа позволяет определить максимальный поток в сети на основе входящих данных.
