МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО
ОБРАЗОВАНИЯ
«Омский государственный технический университет»
Кафедра «Прикладная математика и фундаментальная информатика»
010500.62 «Математическое обеспечение и
администрирование информационных систем»
по профилю «Информационные системы и базы данных»
Курсовой проект
на
тему Алгоритм Форда-Фалкерсона
по
дисциплине Программирование
Студент Помыткин Михаил группы БД-211
Пояснительная записка
Шифр проекта КП – 206899 – 56 – 15 – 00.00.000.ПЗ
Руководитель проекта
Купш А.Г.
____________________
(Подпись, дата)
Нормоконтроль Разработал студент
______________________ _____________________ (Подпись, дата)
Омск 2012
РЕФЕРАТ
Пояснительная записка к курсовой работе: 18с., 5 рис., 0 табл., 3 разделов, 2 приложения.
АЛГОРИТМ, ГРАФ, РЕБРО, ВЕРШИНА, МАКСИМАЛЬНЫЙ ПОТОК, ПАРАЛЛЕЛЬНЫЙ, ПСЕВДОКОД, БЛОКСХЕМА, РЕАЛИЗАЦИЯ
Объект исследования: алгоритм Форда-Фалкерсона
Цель работы: закрепление знаний и умений, полученных в процессе теоретического обучения.
Метод работы: закрепление теоретических знаний с помощью разработки программы, реализующий данный алгоритм.
Содержание
Введение 3
1 Графы 5
1.1Основные характеристики графов 5
1.2 Пути и маршруты 5
2. Алгоритм Форда-Фалкерсона 6
2.1 Краткое описание алгоритма 6
2.2 Анализ сложности алгоритма 9
2.3 Псевдокод 9
3 Распараллеленный вариант алгоритма 9
3.1 Библиотека omp.h 9
3.2 Краткое описание распараллеливания алгоритма 10
Заключение 11
Список использованных источников 12
Приложение А 13
Текст основного файла 13
Приложение Б 14
Введение
Объектом исследования курсовой работы стала реализация алгоритма Форда-Фалкерсона.
Целями работы являлись:
ознакомление с алгоритмом Форда-Фалкерсона, его историей;
реализация алгоритма, для построения нахождения максимального потока сети;
анализ трудоёмкости алгоритма;
тестирование алгоритма.
В теории графов транспортная сеть — ориентированный граф, в котором каждое ребро имеет неотрицательную пропускную способность и поток . Выделяются две вершины: источник и сток такие, что любая другая вершина сети лежит на пути из источника в сток. Транспортная сеть может быть использована для моделирования, например, дорожного трафика. Целочисленная транспортная сеть — транспортная сеть, все пропускные способности ребер которой — целые числа.
Поток — функция со следующими свойствами для любых вершин:
Ограничение пропускной способности;
Поток не может превысить пропускную способность;
Поток из вершины в другую должен быть противоположным в другом направлении;
Сохранение потока. для всех , кроме источника и стока.
Первый отчет «Максимальный поток в сети» датируется 19 ноября 1954 года. Авторы отчета – Форд и Фалкерсон, доказали теорему о максимальном потоке и минимальном разрезе для неориентированных графов: значение максимального потока в сети равно минимальной пропускной способности разреза. (Разрезом в сети называется разбиение множества ее вершин на два непересекающихся класса, таких что источник и сток лежат в разных классах. Пропускной способностью разреза называется сумма пропускных способностей ребер, концы которых лежат в разных классах.) В 1955 году в работе Робахера было упомянуто, что впервые эту теорему доказал Фалкерсон.
Граф можно задавать несколькими путями, однако самый просто способ задания – задание графа матрицей смежности. Тем не менее, этот способ подходит исключительно для таких сетей, которые имеют начальную пропускную способностью равную длине ребра.
Алгоритм широко применяется в сфере перевозок, для того чтобы найти оптимальные маршруты перевозки грузов. Также широкое применение он находит в компьютерных технологиях, коммуникационных сетях, электрических сетях.
Суть распараллеливания алгоритма заключается в уменьшении времени работы с большими объемами входных данных. Стоит заметить, что сложность и трудоемкость алгоритма напрямую зависит от способа реализации. Пример описанных в проекте, работает при помощи алгоритма обхода графа в ширину. Этот алгоритм нужен для того, чтобы искать пути в заданном графе из источника в сток.