Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Полный поток в транспортной сети

Читайте также:
  1. Анализ денежных потоков косвенным методом
  2. Анализ денежных потоков прямым методом
  3. Буква Д в слове ДЕНДЕРЕВО означает Два и более потока дохода
  4. В настроении воина полный самоконтроль и абсолютное самообладание соединяются с отрешенностью, то есть с полным самоотречением.
  5. Вертикальные и горизонтальные потоки информации
  6. Внутри потока
  7. Газовые струи в поперечном потоке

Потоки в сетях

Полный поток в транспортной сети

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

Введем основные понятия данной теории.

Транспортной сетью называется орграф 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.

3) Удаляем из орграфа D* все дуги, являющиеся насыщенными при потоке j в транспортной сети D. Полученный орграф снова обозначим через D*.

4) Ищем в D* простую цепь m из v1 в vn. Если такой цепи нет, то j - искомый полный поток в транспортной сети D. В противном случае переходим к шагу 5.

5) Увеличиваем поток j(x) по каждой дуге x из m на одинаковую величину a>0 такую, что, по крайней мере, одна дуга из m окажется насыщенной, а потоки по всем остальным дугам из m не превышают их пропускных способностей. При этом величина потока j также увеличится на a, а сам поток j в транспортной сети D остается допустимым. После этого перейдем к шагу 3.

 

 


Дата добавления: 2015-08-09; просмотров: 193 | Нарушение авторских прав


Читайте в этой же книге: Загальні принципи побудови геологічних карт. | Карти четвертинних відкладів. | Геоморфологічні карти. | Тектонічні карти. | Палеогеографічні карти | Гідрологічні карти | Геоекологічні карти. | Геологічні розрізи та стратиграфічні колонки |
<== предыдущая страница | следующая страница ==>
ЗНАЧЕНИЕ ИНФОРМАЦИОННЫХ ПИСЕМ ПРЕЗИДИУМА ВЫСШЕГО АРБИТРАЖНОГО СУДА РОССИИ ДЛЯ РОССИЙСКОЙ АРБИТРАЖНОЙ ПРАКТИКИ| Методи дослідження і графічного моделювання будови окремих об’єктів земної кори

mybiblioteka.su - 2015-2024 год. (0.007 сек.)