Поток в транспортной сети - Нахождение максимального потока в графе
Функция, определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если:
*для любой дуги величина, называемая потоком по дуге, удовлетворяет условию ;
*для любой промежуточной вершины v выполняется равенство
Т. е. сумма потоков по дугам, заходящим в v, равна сумме потоков по дугам, исходящим из v.
Для любого допустимого потока в транспортной сети D выполняется равенство:
По определению допустимого потока имеем:
Заметим, что для каждой дуги где, величина входит в левую часть равенства лишь один раз и при этом со знаком плюс.
Аналогично для каждой дуги, величина входит в левую часть равенства (2) лишь один раз и при этом со знаком минус. С другой стороны, для каждой дуги величина входит в левую часть равенства (2) один раз со знаком плюс (при ) и один раз со знаком минус (при ), что в сумме дает нулевой вклад в левую часть равенства (2). Учитывая сказанное, заключаем, что из равенства (2) следует справедливость равенства (1).
Величиной потока в транспортной сети D называется величина, равная сумме потоков по всем дугам, заходящим в, или, что то же самое - величина, равная сумме потоков по всем дугам, исходящим из
Пусть - допустимый поток в транспортной сети D. Дуга называется насыщенной, если поток по ней равен ее пропускной способности, т. е. если. Поток называется полным, если любой путь в D из содержит, по крайней мере, одну насыщенную дугу.
Поток называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D.
Очевидно, что максимальный поток обязательно является полным (т. к. в противном случае в D существует некоторая простая цепь из V1 в Vn, не содержащая насыщенных дуг, а следовательно, можно увеличить на единицу потоки по всем дугам из и тем самым увеличить на единицу, что противоречит условию максимальности потока). Обратная же, вообще говоря, неверно. Существуют полные потоки, не являющиеся максимальными. Тем на менее полный поток можно рассматривать как некоторое приближение к максимальному потоку.
Похожие статьи
-
Основные понятия теории графов - Нахождение максимального потока в графе
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин "граф" впервые ввел в 1936 году венгерский математик Денеш Кениг....
-
В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих...
-
Введение - Моделирование крупномасштабной транспортной сети предфрактальными графами
Транспорт - важный стратегический комплекс, в значительной степени определяющий мощь экономики страны и обеспечивающий нужды общества в перемещении людей...
-
Введение - Нахождение максимального потока в графе
Актуальность задачи о максимальном потоке постоянно возрастает вместе со строительством трубопроводов, новых дорог, роста пользователей Интернета и любых...
-
В основе модели крупномасштабной транспортной сети лежит принцип иерархической организации территорий (в нисходящем направлении). Рассмотрим карту сети...
-
Определим понятие предфрактального графа индуктивно. Обозначим через - конечный связный n-вершинный граф с множеством вершин и множеством ребер, который...
-
Выводы, Литература - Моделирование крупномасштабной транспортной сети предфрактальными графами
В качестве модели карты дорог предлагается использовать предфрактальные графы, которые естественным образом отражают структуру связей при рассмотрении...
-
При анализе больших объемов данных зачастую их можно представить в виде графа. Основными атрибутами графа являются вершины и ребра, поэтому изучение...
-
Оценка времени поездки на основе моделирования транспортных потоков
Оценка времени поездки на основе моделирования транспортных потоков С. Н.Козорезова Постоянное увеличение количества транспортных заторов на...
-
Моделирование транспортной сети большой размерности с помощью предфрактальных графов позволяет строить эффективные алгоритмы благодаря свойству...
-
Целью расчета установившихся режимов (электрического расчета) ЭС является определение параметров режима ветвей и узлов: потоков активной и реактивной...
-
Разработка алгоритма нахождения входного потока заявок в имитационной модели контрольно-пропускной системы на основе статистических данных В наши дни...
-
Q(x) - соответствует площади боковой поверхности данного тела от точки А до точки х. Q(x)>х€[a, x]. Q (x+?x)>х€[a, x+?x], тогда ?Q=Q...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Экономические и финансовые сети На протяжении долгих лет глобализация ведет к увеличению зависимости различных организаций друг от друга. Правительства,...
-
В данной главе мы приводим детальное описание метода обратного распространения - способа обучения многослойных НС. Подробно описана НС для распознавания...
-
Приведенные затраты - Расчет электрической сети микрорайона в г. Иркутск
Выбор рационального варианта сети производится на основании технико-экономических расчетов и сопоставления конкурентоспособных вариантов по минимуму...
-
Выбор числа и мощности трансформаторов - Районная электрическая сеть
При проектировании электрических сетей на подстанциях всех категорий рекомендуется применять не более двух трехфазных трансформаторов. При определении...
-
Для того, чтобы узнать, на сколько максимум может увеличится ВРП Краснодарского края, не хватает оптимального значения капитала. Для этого построим...
-
Построим функцию роста валового регионального продукта: Таблица 11-Данные для функции роста ВРП Год (t) Y (миллион рублей) 1 372930 2 483951 3 648211 4...
-
Нахождение квази-клик за заданный период - Использование квази-клик для анализа графа рынка России
К полученному графу рынка мы можем применить алгоритм поиска максимальной квази-клики в графе. Поэтому, для целей практического применения, возникла...
-
Поскольку процесс инвестирования, как правило, имеет большую продолжительность в практике анализа эффективности капитальных вложений, обычно приходится...
-
Вводим дополнительные ограничения в модель: А) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и...
-
Свойство 1. Вероятность достоверного события равна единице. Действительно, если событие достоверно, то каждый элементарный исход испытания...
-
Використання концепції ефективного автомобіля для моделювання динаміки транспортних потоків у транспортній мережі міста Постановка проблеми. Однією з...
-
Провести проверку сети, приведенной на рис. 1.4, с исходными расчетными данными из табл. 1.12 по потере напряжения в нормальном и послеаварийном режимах....
-
Экономические задачи, сводящиеся к транспортным моделям - Экономико-математические методы
Алгоритмы и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с...
-
Метод максимального правдоподобия - Основы научных исследований
Разработан Р. Фишером. Пусть Х 1 ,х 2 ...х N - выборка из генеральной совокупности случайной величины Х с функцией плотности вероятности Р(х, и),...
-
О клике. Определим формально задачу поиска максимальной клики, согласно статьи On the maximum quasi-clique problem [17]. Пусть G=(V, E) - простой...
-
Применение нейронных сетей в финансовой сфере - Прогнозирующие системы
Характерный пример успешного применения нейронных вычислений в финансовой сфере - управление кредитными рисками. Как известно, до выдачи кредита банки...
-
Модель сети с обратным распространением - Прогнозирующие системы
Способом обратного распространения (back propogation) называется способ обучения многослойных НС. В таких НС связи между собой имеют только соседние...
-
В теории чисел большую роль играет числовая функция, называемая функцией Эйлера. Определение 3.1. Функцией Эйлера называется функция, определенная на...
-
Рассмотрим основные элементы выбранные мной для силовой части контроллера - компенсатора. К ним можно отнести тиристоры и тиристорные оптопары. Тиристор...
-
Электрический расчет - Районная электрическая сеть
Электрический расчет предлагается проводить для случая, когда известна максимальная нагрузка на шинах НН. Расчет режимов выполняется методом...
-
Основные понятия сетевых и графовых моделей Объектом исследования является сеть, состоящая из узлов и линий связи. Предполагается, что в сети имеется два...
-
Теперь исходя из нашей модели мы можем просчитать оптимальное кол-во трудящихся, которое потребуется для роста экономики: (39) Рассчитаем данные по годам...
-
Контроллер представляет собой микропроцессорную систему управления. Контроллер выполняет следующие функции: Контроль тока и напряжения в 3х фазной сети,...
-
О квази-клике. - Использование квази-клик для анализа графа рынка России
Квази-клика - представляет собой релаксацию строгого условия полноты клики, то есть допускается отсутствие некоторых ребер в искомом подграфе. На данный...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Выбор сечений проводов, Выбор сечений проводов для варианта I - Районная электрическая сеть
Выбор сечений проводов для варианта I Экономический выбор сечений проводов воздушных линий электропередачи проводится по экономической плотности тока J...
Поток в транспортной сети - Нахождение максимального потока в графе