Постановка задачи, Алгоритм построения максимального потока - Нахождение максимального потока в графе

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

Алгоритм построения максимального потока

Важным следствием теоремы Форда-Фалкерсона является алгоритм построения максимального потока в транспортной сети.

Шаг 1. Полагаем i=0. Пусть - любой допустимый поток в транспортной сети D (например, полный, можно начинать с нулевого потока: ).

Шаг 2. По сети D и потоку строим орграф приращений.

Шаг 3. Находим простую цепь, являющуюся минимальным путем из в в нагруженном орграфе. Если длина этой цепи равна бесконечности, то поток максимален, и работа алгоритма закончена. В противном случае увеличиваем поток вдоль цепи на максимально допустимую величину, такую, что при этом сохраняется условие 1 допустимого потока (для любой дуги величина, называемая потоком по дуге х, удовлетворяет условию ). В силу, используя и, получаем, что указанная величина существует. В результате меняется поток в транспортной сети D, т. е. от потока мы перешли к потоку, и при этом. Присваиваем и переходим к шагу 2.

Программа должна находить максимальный поток во введенную в нее транспортной сети.

Похожие статьи

• Орграф приращений, Теорема Форда-Фалкерсона - Нахождение максимального потока в графе

  Введем для заданной транспортной сети D и допустимого потока в этой сети орграф приращений, имеющий те же вершины, что и сеть D. Каждой дуге транспортной...

• Поток в транспортной сети - Нахождение максимального потока в графе

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

• Введение - Нахождение максимального потока в графе

  Актуальность задачи о максимальном потоке постоянно возрастает вместе со строительством трубопроводов, новых дорог, роста пользователей Интернета и любых...

• Основные понятия теории графов - Нахождение максимального потока в графе

  Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин "граф" впервые ввел в 1936 году венгерский математик Денеш Кениг....

• Параллельный алгоритм выделения дольного графа - Многокритериальная постановка задачи выбора проектов целевых программ

  Рассмотрим взвешенный предфрактальный граф, порожденный затравкой и K процессоров, где. Параллельный алгоритм выделения дольного графа основан на...

• Разработка алгоритма нахождения входного потока заявок в имитационной модели контрольно-пропускной системы на основе статистических данных

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

• Способы анализа графа рынка. Нахождение максимальной клики и максимального независимого множества - Использование квази-клик для анализа графа рынка России

  При анализе больших объемов данных зачастую их можно представить в виде графа. Основными атрибутами графа являются вершины и ребра, поэтому изучение...

• Постановка задачи и генетические алгоритмы для многокритериальной оптимизации ИП - Возможности генетических алгоритмов для решения задачи многокритериальной оптимизации инвестиционного портфеля

  Рассматриваемая задача оптимизации ИП основывается на двухкритериальной модели Г. Марковица с незначительной корректировкой (вместо поиска долей каждого...

• Постановка задачи - Методика решения задачи целочисленного программирования

  Сформулировать по заданному 24-хзначному числу модель целочисленного программирования вида: Где все параметры модели должны быть определены из следующих...

• Эволюционные механизмы формирования з-областей - Эволюционные процедуры решения комбинаторных задач на графах

  Формирование З -областей в матрице R осуществляется в процессе ее эволюционной модификации. Эволюционная модификация матрицы R производится путем...

• Решение геометрических задач на нахождение наибольшего и наименьшего значений с помощью производной, Планиметрические задачи - Применение производной в решении геометрических задач

  Планиметрические задачи Задача 1.Написать уравнения касательной и нормали к графику функциив данной точке, если: [3]. Решение. Уравнение касательной...

• Алгоритмы поиска квази-клики в графе. - Использование квази-клик для анализа графа рынка России

  Как и для поиска клик существуют алгоритмы поиска квази-клик в графе. Далее мы рассмотрим некоторые из них. Как было сказано ранее, задача поиска...

• Разработка экономико-математической модели по оптимизации отраслевой структуры производства в СХА "Горизонт", Постановка задачи - Разработка экономико-математической модели по оптимизации отраслевой структуры производства в СХА "Горизонт"

  Постановка задачи За сельскохозяйственной артелью "Горизонт" закреплено 3 890 га сельскохозяйственных угодий, в том числе 3406 га пашни, 389 га сенокосов...

• Постановка задачи - Экономико-математические методы

  Пусть имеется m поставщиков А1, А2, ...,Аm однородного груза в количествах соответственно а1, а2,...,аm единиц и n потребителей В1, В2,...,Вn этого...

• Транспортные задачи, имеющие некоторые усложнения в постановке - Экономико-математические методы

  Транспортная задача с избытком запасов: Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают...

• Принципы построения программ с автоматическим выбором шага, Решение задачи, Блок-схема программы, Результаты решения - Вычисление кратных интегралов методом ячеек с автоматическим выбором шага

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

• Общая схема модели - Постановка задачи прогнозирования продуктивности агроэкосистем

  Построенным модулям можно дать следующие краткие характеристики: Модуль "Почва" позволяет численно оценить показатель плодородия через доступные...

• Математическая модель с учетом дополнительных условий, Математическая модель транспортной задачи - Методика решения задачи целочисленного программирования

  Вводим дополнительные ограничения в модель: А) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и...

• Нахождение кратчайшего пути в транспортной сети - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

  В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих...

• Описание установки, Постановка задачи - Нейтрон-спектрометрический анализ изотопного состава обогащенных проб гафния

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

• Введение - Возможности генетических алгоритмов для решения задачи многокритериальной оптимизации инвестиционного портфеля

  Оптимизация инвестиционного портфеля (ИП) [Дубровин и др., 2008], [Мищенко и др., 2002], [Серов, 2000] является одной из важных экономических задач,...

• Алгоритм принятия решений на основе анализа иерархии целей - Формализация решения многоцелевых задач при управлении научной деятельностью

  Алгоритм использует в качестве исходных данных документы, содержащие следующие сведения: X A, k,j, i - измеряемые показатели научной работы; X A, TG,...

• Постановка задачі - Температурна залежність інтенсивності і напівширини спектрів індивідуальних смуг фотолюмінесценції іонів Mn2+ в кристалах ZnS

  Одним із перспективних напрямів при дослідженні кристалів ZnS:Mn є дослідження температурних характеристик його спектрів. Нова інформація в цьому напрямі...

• Данные об исследуемой культуре - Постановка задачи прогнозирования продуктивности агроэкосистем

  В результате численных экспериментов были обнаружены следующие недостатки модели: Структуру сети и ее обучение необходимо проводить под каждую конкретную...

• Постановка задачі - Економетричні моделі

  Задача. Для виготовлення чотирьох видів продукції використовують три види сировини. Запаси сировини, норми його витрати і прибуток від реалізації...

• Задача поиска маршрутов в графе (путей в орграфе)

  Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...

• Особенности постановки и решения общей задачи линейного программирования - Определение оптимальной стратегии рыночного поведения с использованием макроэкономических методов и моделей

  Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....

• Методы построения гамильтоновых циклов в графе, Алгебраический метод построения гамильтоновых циклов - Гамильтоновы циклы

  Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G...

• Решение транспортной задачи. Нахождение опорного плана тремя методами, Метод минимального элемента - Математическое моделирование в менеджменте и маркетинге

  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, j) известны и составляют dij, где i=1, m; j=1, n; i?j. Если прямого маршрута...

• ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗЛП) - Линейное программирование в экономике

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

• Построение статистического правила для решения задачи построения MST - Анализ статистических свойств процедуры построения минимального остовного дерева

  Минимальное остовное дерево в связанном взвешенном неориентированном графе-это остовное дерево данного графа, в котором сумма весов, входящих в него...

• Постановка задачи, Основные сведения - Комплексное исследование численных методов для задачи решения нелинейных уравнений

  Провести комплексное исследование численных методов для задачи решения нелинейных уравнений. 1. Решить нелинейные уравнения А) ; Б) ; В) . 2....

• Постановка задачи, Понятие о кубатурных формулах, Метод ячеек - Вычисление кратных интегралов методом ячеек с автоматическим выбором шага

  Найти при помощи метода ячеек значение интеграла , Где - область, ограниченная функциями . 2. Теоретическая часть Рассмотрим K-мерный интеграл вида: (1)...

• Общая постановка задачи линейного программирования (ЛП) - Решение оптимизационных экономических задач методами линейного программирования

  Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейного функционала при линейных ограничениях. В литературе...

• Алгоритм розв'язку задачі визначення оптимального горизонту планування амортизаційної стратегії - Взаємозв'язок між горизонтом планування й витратами на амортизацію для малого підприємства

  Перед пошуком розв'язку задачі зробимо деякі перетворення в моделі. Для перетворимо рівняння (2.2) і отримаємо: Отримаємо: Тепер підставимо отриманий...

• Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах

  Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...

• Многокритериальная постановка задачи выбора проектов целевых программ - Многокритериальная постановка задачи выбора проектов целевых программ

  В настоящее время Российская Федерация входит в состав ВТО, в связи с чем, для устойчивого развития, для надежности, для стойкости [1, 2] появляется...

• Постановка задачі оптимального керування - Дослідження попиту годинників з метою оптимізації номенклатури на прикладі фірми "Годинникар"

  Стан об'єкта керування характеризується n-мірної вектор функцією, наприклад, функцією часуТак, шестивимірна вектор-функція часу цілком визначає положення...

• Нахождение квази-клик за заданный период - Использование квази-клик для анализа графа рынка России

  К полученному графу рынка мы можем применить алгоритм поиска максимальной квази-клики в графе. Поэтому, для целей практического применения, возникла...

Постановка задачи, Алгоритм построения максимального потока - Нахождение максимального потока в графе

Предыдущая | Следующая