Применение теоремы Форда-Фолкерсона.

Краткое описание

СОДЕРЖАНИЕ

ВВЕДЕНИЕ...3

1.ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ..5

1.1.Постановка потоковых задач..5

1.2.История развития алгоритмов решение задачи о максимальном потоке..8

2.ТЕОРЕМА ФОРДА - ФАЛКЕРСОНА..14

3.АЛГОРИТМ ФОРДА - ФАЛКЕРСОНА..17

ЗАКЛЮЧЕНИЕ..26

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ..27

ВВЕДЕНИЕ

Деятельность  современного общества тесно связана с разного рода сетями — возьмем, к примеру, транспорт, коммуникации, распределение товаров и тому подобное. Поэтому математический анализ таких сетей стал предметом фундаментальной важности.

Алгоритм Форда— Фалкерсона  решает задачу нахождения максимального потока в транспортной сети.

Задачи теории потоков в сетях являются одними из основных в исследовании операций, computer science и инженерном деле. Теория потоков имеет многочисленные приложения в реально возникающих задачах.

Теория потоков в сетях развилась и развивается сегодня в лучших традициях прикладной математики: она родилась среди разнообразных прикладных проблем и продолжает вносить практический вклад в решение многих прикладных задач. Эта теория установила под собой сильную методологическую основу и сформулировала многочисленные стимулирующие вычислительные проблемы. 

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

К теории потоков относятся различные задачи, которые можно классифицировать следующим образом. Задачи транспортного типа – транспортная задача, поиск пути минимальной длины, поиск циклов отрицательного веса (неоптимальных перевозок) и т. д. Задачи определения существования потока – задача о максимальном потоке и, двойственная к ней, задача поиска минимального разреза. А также задача о поиске обобщенного потока – потока с потерями и приобретениями.

Цель курсовой работы – рассмотреть применение теоремы Форжа-Фолкерсона.

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