Орграф приращений, Теорема Форда-Фалкерсона - Нахождение максимального потока в графе
Введем для заданной транспортной сети D и допустимого потока в этой сети орграф приращений, имеющий те же вершины, что и сеть D. Каждой дуге транспортной сети D в орграфе приращений соответствует две дуги: и - дуга, противоположная по направлению дуге. Припишем дугам орграфа приращений длину:
Т. е. орграф является нагруженным. При этом очевидно, что длина любого пути из в в орграфе равна либо 0, либо бесконечности.
Теорема Форда-Фалкерсона
Пусть D - транспортная сеть, - допустимый поток в этой сети, - множество вершин таких, что длина минимального пути из в в орграфе приращений равна нулю. Тогда, если, то - максимальный поток, величина которого равна.
Пусть. Тогда выполняется равенство
(1)
Если, так как в противном случае, используя имеем, а следовательно, в силу существует путь нулевой длины из в, что противоречит условию. Но тогда из (1) получаем
Следствие 1. Используя теорему Форда-Фалкерсона получаем, что величина максимального потока в транспортной сети равна пропускной способности минимального разреза.
Следствие 2. Пусть - допустимый поток в транспортной сети D. Тогда, если длина минимального пути из v1 в vn в орграфе приращений равна бесконечности, то - максимальный поток.
Похожие статьи
-
Поток в транспортной сети - Нахождение максимального потока в графе
Функция, определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в...
-
Основные понятия теории графов - Нахождение максимального потока в графе
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин "граф" впервые ввел в 1936 году венгерский математик Денеш Кениг....
-
Введение - Нахождение максимального потока в графе
Актуальность задачи о максимальном потоке постоянно возрастает вместе со строительством трубопроводов, новых дорог, роста пользователей Интернета и любых...
-
Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
-
При анализе больших объемов данных зачастую их можно представить в виде графа. Основными атрибутами графа являются вершины и ребра, поэтому изучение...
-
В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих...
-
В теории чисел большую роль играет числовая функция, называемая функцией Эйлера. Определение 3.1. Функцией Эйлера называется функция, определенная на...
-
Q(x) - соответствует площади боковой поверхности данного тела от точки А до точки х. Q(x)>х€[a, x]. Q (x+?x)>х€[a, x+?x], тогда ?Q=Q...
-
Теорема 1. Предел постоянной равен самой постоянной. . Доказательство. f(x)=с, докажем, что . Возьмем произвольное e>0. В качестве d можно взять любое...
-
Доказательство теоремы - Об одной теореме теории чисел
Доказательство теоремы проводится отдельно для случая, когда (т. е. показатель степени в равенстве (2) - НЕЧЕТНОЕ число) и когда (т. е. показатель...
-
Свойство 1. Вероятность достоверного события равна единице. Действительно, если событие достоверно, то каждый элементарный исход испытания...
-
Разработка алгоритма нахождения входного потока заявок в имитационной модели контрольно-пропускной системы на основе статистических данных В наши дни...
-
В данной работе доказывается методами элементарной математики "большая" или "последняя" теорема Ферма. Некоторая, излишняя в обычных случаях, подробность...
-
Метод максимального правдоподобия - Основы научных исследований
Разработан Р. Фишером. Пусть Х 1 ,х 2 ...х N - выборка из генеральной совокупности случайной величины Х с функцией плотности вероятности Р(х, и),...
-
Теорема Ферма - Математичний аналіз
Якщо ф-я диф. в деякому околі Т. х0 і досягає в ній екстремума, то похідна = 0. Доведення: Нехай ф. досягає в екстремума в т. х0, тоді існує окіл т. х0,...
-
Целью расчета установившихся режимов (электрического расчета) ЭС является определение параметров режима ветвей и узлов: потоков активной и реактивной...
-
Рассмотрим взвешенный предфрактальный граф, порожденный затравкой и K процессоров, где. Параллельный алгоритм выделения дольного графа основан на...
-
Теперь исходя из нашей модели мы можем просчитать оптимальное кол-во трудящихся, которое потребуется для роста экономики: (39) Рассчитаем данные по годам...
-
Построим функцию роста валового регионального продукта: Таблица 11-Данные для функции роста ВРП Год (t) Y (миллион рублей) 1 372930 2 483951 3 648211 4...
-
Для того, чтобы узнать, на сколько максимум может увеличится ВРП Краснодарского края, не хватает оптимального значения капитала. Для этого построим...
-
Нахождение квази-клик за заданный период - Использование квази-клик для анализа графа рынка России
К полученному графу рынка мы можем применить алгоритм поиска максимальной квази-клики в графе. Поэтому, для целей практического применения, возникла...
-
О квази-клике. - Использование квази-клик для анализа графа рынка России
Квази-клика - представляет собой релаксацию строгого условия полноты клики, то есть допускается отсутствие некоторых ребер в искомом подграфе. На данный...
-
О клике. Определим формально задачу поиска максимальной клики, согласно статьи On the maximum quasi-clique problem [17]. Пусть G=(V, E) - простой...
-
Введение - Моделирование крупномасштабной транспортной сети предфрактальными графами
Транспорт - важный стратегический комплекс, в значительной степени определяющий мощь экономики страны и обеспечивающий нужды общества в перемещении людей...
-
Поскольку процесс инвестирования, как правило, имеет большую продолжительность в практике анализа эффективности капитальных вложений, обычно приходится...
-
Оценка времени поездки на основе моделирования транспортных потоков
Оценка времени поездки на основе моделирования транспортных потоков С. Н.Козорезова Постоянное увеличение количества транспортных заторов на...
-
Формирование З -областей в матрице R осуществляется в процессе ее эволюционной модификации. Эволюционная модификация матрицы R производится путем...
-
Ответ: y=f(kx) получается из Графика функции f(x) сжатием его вдоль оси ох в k раз, если k>1 и растяжением в 1 деленную на k раз, если k>0 но меньше 1....
-
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 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Використання концепції ефективного автомобіля для моделювання динаміки транспортних потоків у транспортній мережі міста Постановка проблеми. Однією з...
-
Синтаксис и семантика. Теорема Райса - Рекурсивные функции
Попробуем теперь проанализировать круг проблем, неразрешимость которых доказана в предыдущем пункте. Общим для них является то, что по кодам, т. е....
-
Интегральная теорема Муавра-Лапласа
Предположим, что в условиях схемы Бернулли проводится испытаний, в результате каждого из которых с вероятностью () происходит событие. Интегральная...
-
В основе модели крупномасштабной транспортной сети лежит принцип иерархической организации территорий (в нисходящем направлении). Рассмотрим карту сети...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
Скорость падения дождевых капель на определенный предмет
Введение Математика, как наука родилась тысячи лет назад, ибо человек всегда старался познать мир. Эти знания были необходимы древним купцам и...
-
Несобственный интеграл. - Неопределенный интеграл
Несобственные интегралы I рода. О: Несобственным интегралом I рода от функции f(x), определенным на множестве [а,?], называется предел, к которому...
-
Ряды конгруэнций - Формационные основы универсальных алгебр
5.1. Конечная цепь конгруэнции алгебры А вида (1) , Называется Рядом конгруэнций, а число -- Длиной ряда. Фактор алгебры называется Главным , если и из ,...
-
Решетки (структуры) - Формационные основы универсальных алгебр
Понятие решетки (пример 11) играет исключительно важную роль в изучении самых общих алгебр. И это, в первую очередь, связано с иным подходом в...
-
Основные понятия сетевых и графовых моделей Объектом исследования является сеть, состоящая из узлов и линий связи. Предполагается, что в сети имеется два...
-
Экономические и финансовые сети На протяжении долгих лет глобализация ведет к увеличению зависимости различных организаций друг от друга. Правительства,...
Орграф приращений, Теорема Форда-Фалкерсона - Нахождение максимального потока в графе