![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Построения полного потока в сетиСтр 1 из 2Следующая ⇒
Потоки в сетях Полный поток в транспортной сети Теория транспортных сетей возникла при решении задач, связанных с организацией перевозки грузов. Тем не менее понятие потока на транспортной сети, алгоритм нахождения потока наибольшей величины и критерий существования потока, насыщающего выходные дуги сети, оказались полезными для многих других прикладных и теоретических вопросов комбинаторного характера. Введем основные понятия данной теории. Транспортной сетью называется орграф D = (V, X) с множеством вершин V = {v1, …, vn}, для которого выполняются условия: 1) существует одна и только одна вершина v1, называемая источником, такая, что Г-1 (v1) = Æ (т.е. ни одна дуга не заходит в v1), 2) существует одна и только одна вершина vn, называемая стоком, такая, что Г(vn) = Æ (т.е. из vn не исходит ни одной дуги), 3) каждой дуге xÎ X поставлено в соответствие целое число c (x) ³ 0, называемое пропускной способностью дуги. Функция j(x), определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если 1) для любой дуги xÎ X величина j(x), называемая потоком по дуге x, удовлетворяет условию 0 £ j(x) £ c(x), 2) для любой промежуточной вершины v сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v. Величиной потока j в транспортной сети D называется величина, равная сумме потоков по всем дугам, заходящим в сток, или, что то же самое сумме потоков по всем дугам, исходящим из источника. Дуга xÎ X называется насыщенной, если поток по ней равен ее пропускной способности. Поток j называется полным, если любой путь в сети из источника в сток содержит, по крайней мере, одну насыщенную дугу.
А л г о р и т м построения полного потока в сети Данные: транспортная сеть D, заданная матрицей пропускных способностей дуг. Результат: полный поток в сети. 1. Полагаем для любой дуги xÎ Х j(x) = 0 (начинаем с нулевого потока). 2. Полагаем D* = D. 1. Удаляем из орграфа D* все дуги, являющиеся насыщенными при потоке j в транспортной сети D. Полученный орграф снова обозначим через D*. 2. Ищем в D* простую цепь m из v1 в vn. Если такой цепи нет, то j - искомый полный поток в транспортной сети D. В противном случае переходим к шагу 5. 3. Увеличиваем поток j(x) по каждой дуге x из m на одинаковую величину a> 0 такую, что, по крайней мере, одна дуга из m окажется насыщенной, а потоки по всем остальным дугам из m не превышают их пропускных способностей. При этом величина потока j также увеличится на a, а сам поток j в транспортной сети D остается допустимым. После этого перейдем к шагу 3.
|