Изучение и нахождение ограниченного поперечного сечения, определяющего пропускную способность системы в целом. Нахождение алгоритма величины максимального потока в транспортной сети с помощью теоремы Форда-Фалкерсона. Обзор определенной на множестве.
Московский Государственный Институт Делового Администрирования Работу выполнила: Болотина ЮлияВ постановке задаче, которую я рассматриваю, да и вообще в задачах на данную тему фундаментальную роль играет изучение поперечных сечений сети (то есть множеств дуг, которые соединяют вершины двух не пересекающихся множеств вершин) и нахождение ограниченного поперечного сечения, которое является самым узким местом.Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c( ), называемое пропускной способностью дуги, и существует: 1) ровно одна вершина , в которую не заходит ни одна дуга, называемая источником или началом сети; 2) ровно одна вершина , из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.Пусть D - транспортная сеть, - допустимый поток в этой сети, - множество вершин таких, что длина минимального пути из в в орграфе приращений равна нулю. Если , так как в противном случае, используя: Имеем , а следовательно, в силу существует путь нулевой длины из в , что противоречит условию . Используя теорему Форда-Фалкерсона получаем, что величина максимального потока в транспортной сети равна пропускной способности минимального разреза.Для каждой вершины данной сети нужно приписать пометку, которая имеет следующий вид: или где , а - натуральное число или бесконечность. Он получит пометку Источник помечен, но не просмотрен. Чтобы источник S был помечен и просмотрен, надо поместить все вершины, смежные с S. Вершина получит пометку , где: Теперь все вершины смежные с S, помечены, но не просмотрены. Если для вершины выполняется следующее условие, где: Если же для вершины выполняется условие: Далее просматриваем следующую вершину, и так до тех пор, пока не пометим сток t или же пока нельзя будет больше пометить ни одной вершины, сток при этом останется не помеченным.Функция , определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если: - для любой дуги величина , называемая потоком по дуге , удовлетворяет условию; для любой промежуточной вершины v выполняется равенство: Т. е. сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v. Для любого допустимого потока в транспортной сети D выполняется равенство: По определению допустимого потока имеем: Заметим, что для каждой дуги , величина входит в левую часть равенства лишь один раз и при этом со знаком плюс. С другой стороны, для каждой дуги величина входит в левую часть равенства один раз со знаком плюс и один раз со знаком минус, что в сумме дает нулевой вклад в левую часть равенства (2). Величиной потока в транспортной сети D называется величина , равная сумме потоков по всем дугам, заходящим в , или, что то же самое - величина, равная сумме потоков по всем дугам, исходящим из : Пусть - допустимый поток в транспортной сети D.Введем для заданной транспортной сети D и допустимого потока в этой сети орграф приращений , имеющий те же вершины, что и сеть D.Важным следствием теоремы Форда-Фалкерсона является Алгоритм построения максимального потока в транспортной сети. По сети D и потоку строим орграф приращений . Если длина этой цепи равна бесконечности, то поток максимален, и работа алгоритма закончена.Просмотрим вершину S, для этого пометим вершины V, V, V. Просмотрим вершину V, ставим метки. Просмотрим вершину V1, вершины V4 и V2 получают метки и Просмотрим V3, V2 уже просмотрена, . Просмотрим V2, V4 уже помечена, Изменение потока: Вносим изменения потока. Просмотрим V3, V2 уже помечена, Просмотрим V2, V4 уже помечена, Просмотрим V4.Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами.
План
Содержание
Введение
1. Теоретическая часть
2. Теорема Форда-Фалкерсона
3. Алгоритм решения
4. Поток в транспортной сети
5. Орграф приращений
6. Алгоритм построения максимального потока в транспортной сети
7. Практическая часть
Заключение
Список используемой литературы
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
