русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2013-12-23; просмотров: 2657; Нарушение авторских прав


Определение. Функция j (x), определенная на множестве X дуг транспортной сети D, и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если:

1) для любой дуги x Î X величина j(x), называемая потоком по дуге х, удовлетворяет условию 0 j(x) c(x);

2) для любой промежуточной вершины v выполняется равенство

т.е. сумма потоков по дугам, заходящими в v, равна сумме потоков по дугам, исходящими из v.

Определение. Величиной потокаj в транспортной сети D называется величина j, равная сумме потоков по всем дугам, заходящим в vn, или, что то же самое, величина, равная сумме потоков по всем дугам, исходящим из v1, т.е.

 

Пусть j - допустимый поток в транспортной сети D.

Определение. Дуга x Î X называется насыщенной, если поток по ней равен ее пропускной способности, т.е. если j(x) = c(x). Поток j называется полным, если любой путь в D из v1 в vn содержит, по крайней мере, одну насыщенную дугу.

Определение. Поток j называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D.

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

Алгоритм построения полного потока в транспортной сети D:

Шаг 1. Полагаем "x Î X j(x) = 0 (т.е. начинаем с нулевого потока). Кроме того, полагаем D` = D.

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

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



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

Пример 90.

Построить полный поток в транспортной сети, изображенной на рисунке 43.

 

Решение.

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

1. h 1 = v1v2v4v6, a1 = min{7, 3, 7} = 3 (рис. 45).

2. h 2 = v1v2v3v4v6, a2 = min{7-3, 2, 2, 7-3} = 2 (рис. 46).

3. h 3 = v1v3v5v6, a3 = min{8, 2, 9} = 2 (рис. 47).

4. h 4 = v1v2v5v6, a4 = min{7-5, 6, 9-2} = 2 (рис. 48).

Заметим, что в полученной транспортной сети не существует пути из источника в сток, по которому возможно пройти. Следовательно, построенный поток в транспортной сети является полным и j = 3+2+2+2=9.

 

 



<== предыдущая лекция | следующая лекция ==>
Равносильность формул логики предикатов | Алгоритм построения максимального потока в транспортной сети


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.