рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Математика
- /
- Потоки в сетях
Реферат Курсовая Конспект
Потоки в сетях
Потоки в сетях - раздел Математика, ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ Весам Дуг Можно Дать Иную Интерпретацию, В Результате Возника...
Весам дуг можно дать иную интерпретацию, в результате возникает интересная и важная задача. Пусть в ориентированном взвешенном графе выделены две вершины (b – начальная и e – конечная). Предполагается, что вершина e достижима из b. Содержательный смысл весов дуг это пропускная способность дорог. Нас интересуют перевозки из вершины b в вершину e. Естественным является вопрос: какой максимальный груз можно перевезти из начальной вершины в конечную? В отличие от расстояний вес груза, перевозимого по цепи, не равен сумме весов грузов, перевозимых по отдельным дугам. Поставленную задачу называют задачей о максимальном потоке. Слово «поток» здесь является естественным, поскольку можно говорить о потоке грузов, можно задачу интерпретировать и как анализ потоков жидкости в трубопроводах. Приведем формальное определение. Обозначения Г(v), Г-1(v) имеют тот же смысл, что и в предыдущем параграфе.
ОПРЕДЕЛЕНИЕ 35.Потоком в сетиот вершины b к вершине e называется определенная на дугах графа неотрицательная числовая функция x(u,v), удовлетворяющая условиям:
x(u,v)≤ c(u,v);
при u¹b,e;
.
Первое условие означает, что по каждой дуге можно провезти груза не более ее пропускной способности, второе это недопустимость потери потока в промежуточных пунктах (сколько поступает, столько и отправляется), третье отражает тот факт, что из начальной вершины вывозится столько груза, сколько ввозится в конечную, t - величина потока. Задача состоит в том, чтобы найти поток с максимальной величиной.
С понятием потока тесно связано понятие разреза.
ОПРЕДЕЛЕНИЕ 36.Разрезомв графе Г, разделяющим начальную и конечную вершины, называется семейство дуг, после удаления которых в соответствующем неориентированном графе начальная и конечная вершины принадлежат разным компонентам связности (назовем их b-компонентой и e-компонентой).
Образно говоря, разрез это стена, отделяющая конечную вершину от начальной. Разумеется, при добавлении дуг к разрезу также получаем разрез.
Величиной разреза называется сумма весов дуг в разрезе, ведущих из b-компоненты и e-компоненту. Предыдущее замечание говорит о том, что имеет смысл говорить о минимальном разрезе, разделяющем начальную и конечную вершины, как о разрезе с минимальной величиной.
Теорема 27(Форда-Фалкерсона). При заданных начальной и конечной вершинах сети величина максимального потока равна величине минимального разреза.
Доказательство. Прежде всего, величина любого потока не превосходит величины любого разреза. Действительно, из b в e нельзя перевезти груза больше, чем через стену, отделяющую b от e. Таким образом, если мы найдем поток и разрез с равными величинами, то это непременно максимальный поток и минимальный разрез.
Построение фактически является алгоритмом построения максимального потока и минимального разреза, эффективным при целых весах дуг.
При построении важную роль играет следующая конструкция. Рассмотрим последовательность вершин и дуг, соединяющих b и e, причем направления дуг могут быть разными. Дуги, направленные от b к e, назовем прямыми, в противоположном направлении – обратными. (Отметим, что дуга, которая является прямой в одной цепи, может быть обратной в другой). Такая последовательность называется увеличивающей цепью из b в e, если для прямых дуг x(u,v)<c(u,v), а для обратных x(u,v)>0. Пусть p=min{c(u,v)-x(u,v)} для прямых дуг, q=min{x(u,v)} для обратных дуг цепи, r=min{p,q}>0. Поток из b в e можно увеличить по увеличивающей цепи на величину r, положив x(u,v):=x(u,v)+r на прямых дугах и x(u,v):=x(u,v)-r на обратных. Полученные значения также являются потоком (проверьте это!). После такого преобразования цепь не является увеличивающей, поскольку для некоторой прямой дуги x(u,v)=c(u,v) или (не разделительное) для некоторой обратной – x(u,v)=0.
Построение потока с нужными свойствами заключается в последовательном удалении с помощью описанной конструкции увеличивающих цепей и таким образом в увеличении потока из b в e, пока это возможно. В начале поток принимается нулевым. Поскольку при каждой итерации поток увеличивается как минимум на 1 (веса дуг целые!), а величина потока ограничена сверху (например, суммой весов всех дуг графа), то после конечного числа итераций увеличивающих цепей в графе не будет. Полученный поток увеличить нельзя (если бы это можно было сделать, то соответствующая цепь была бы увеличивающей), т.е. он максимальный.
Разобьем множество вершин V на два класса. В первый (V1) входят такие вершины v, для которых существует увеличивающая цепь из b в v, во второй (V2) – остальные вершины. Оба класса непустые: bÎV1, eÎV2, т.е. это b и e-компоненты. Дуги, направленные из V1 в V2 и наоборот, образуют разрез. При этом если (u,v) дуга, uÎV1,vÎV2, то x=c(u,v). Действительно, в противном случае (т.е. при x(u,v)<c(u,v)), присоединив к увеличивающей цепи из b в u дугу (u,v), получим увеличивающую цепь из b в v, что невозможно по построению. Аналогично, если uÎV2,vÎV1, то x(u,v)=0.
Величина построенного разреза равна сумме весов «прямых» дуг. Докажем, что величина построенного максимального потока равна сумме весов тех же дуг. Каждая единица груза доставляется по какой-нибудь из этих дуг, причем по единственной. Если бы таких дуг было более одной, то эта единица груза доставлялась бы по некоторой дуге, ведущей из V2 в V1, а на этих дугах поток нулевой. Теорема Форда-Фалкерсона доказана.
Идея алгоритма, описанного при доказательстве теоремы, реализуется формированием пометок вершин тем или иным образом. Основной недостаток этого подхода состоит в том, что нет никаких указаний относительно построения увеличивающих цепей, а от их выбора сильно зависит число итераций. Во второй половине 20 века разработано множество более простых алгоритмов построения максимального потока.
– Конец работы –
Эта тема принадлежит разделу:
ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования... Уфимский государственный авиационный технический университет...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Потоки в сетях
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.022 сек.
Новости и инфо для студентов