ВВЕДЕНИЕ 2
ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОНЯТИЯ СЕТЬ 4
1.1. Понятие сети 4
1.2. История развития алгоритмов решения задачи о максимальном потоке 6
ГЛАВА 2. РЕАЛИЗАЦИЯ АЛГОРИТМОВ МАКСИМАЛЬНОГО ПОИСКА ПОТОКА СЕТИ 12
2.1. Алгоритм размещения пометок для задачи о максимальном потоке 12
2.2. Алгоритм Диница, Малхотры, Эдмондса - Карпа 13
2.3. Алгоритм Форда-Фалкерсона 21
2.4. Задача о многополюсном максимальном потоке 26
ЗАКЛЮЧЕНИЕ 31
ЛИТЕРАТУРА 32
Краткое содержание работы:
ВВЕДЕНИЕ
Задача о максимальном потоке является классической и имеет множество применений. Напомню постановку проблемы. Дан взвешенный ориентированный граф с неотрицательными весами (пропускными способностями). Выделены две вершины: исток S и сток T такие, что любая другая вершина лежит на пути из S в T. Потоком назовем функцию F: V x V с такими свойствами
Ограничение пропускной способности. Поток по ребру не может быть больше его (ребра) пропускной способности.
Антисимметричность. Для каждого ребра (u, v): F(u, v) = -F(v, u).
Сохранение потока. Для каждой вершины (кроме S и T), количество входящего потока (отрицательного) равен количеству исходящего потока (положительного). То есть, алгебраическая сумма потоков для каждой вершины (кроме S и T) равна нулю.
На практике часто возникает проблема определения максимальной проводимости некоторой реальной сети: сети транспортной, сети ЭВМ, других. Иногда нужно определить самый дешёвый поток и т.д. Все эти и многие другие задачи решаются с помощью алгоритмов, которые работают на сетях. Так, алгоритм о максимальном потоке ищет максимально возможную пропускную способность сети, алгоритм минимальной стоимости – самый дешёвый поток. В данном разделе будем рассматривать задачу о максимальном потоке.
Задача заключается в нахождении такого множества потоков по дугам, чтобы величина Q(vs) была максимальной.
Разрез S отделяет vs от vt, если вершины vs, vt принадлежат разным сторонам разреза: vs Vs, vt Vt, V = Vs Vt. Пропускной способностью с(S) разреза S называется сумма пропускных способностей дуг разреза, которые начинаются в Vs и заканчивается в Vt:
с(S) = .
Изучение этих и других подобных им практических задач приводит к теории потоков в сетях.
Целью курсовой работы является рассмотрение способов реализации алгоритмов поиска максимального потока сети.
Задачами курсовой работы является:
-
Курсовая работа состоит из введения, двух глав, заключения и списка использованной литературы.
В нашей компании вы можете заказать консультацию по любой учебной работе от 300 руб. Оформите заказ, а договор и кассовый чек послужат вам гарантией сохранности ваших средств. Кроме того, вы можете изменить план текущей работы на свой, а наши авторы переработают основное содержание под ваши требования
