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

Задача о максимальном потоке

Читайте также:
  1. Ваша задача
  2. Газовые струи в поперечном потоке
  3. ГЛАВНАЯ ЗАДАЧА —ИЗМЕНЕНИЕ НРАВСТВЕННОСТИ ЛЮДЕЙ
  4. Деформация мира. Задача возращения
  5. ДУВП. Задача Коши. Теорема Коши-Пикара. Теорема Пеано. Краевая задача.
  6. Задание 2. Задача № 110
  7. Задача 1.

На практике часто возникает проблема определения максимальной проводимости некоторой реальной сети: сети транспортной, сети ЭВМ, других. Иногда нужно определить самый дешёвый поток и т.д. Все эти и многие другие задачи решаются с помощью алгоритмов, которые работают на сетях. Так, алгоритм о максимальном потоке ищет максимально возможную пропускную способность сети, алгоритм минимальной стоимости – самый дешёвый поток. В данном разделе будем рассматривать задачу о максимальном потоке.

Задача заключается в нахождении такого множества потоков по дугам, чтобы величина Q (vs) была максимальной.

Разрез S отделяет vs от vt, если вершины vs, vt принадлежат разным сторонам разреза: vs Vs, vt Vt, V = Vs Vt. Пропускной способностью с (S) разреза S называется сумма пропускных способностей дуг разреза, которые начинаются в Vs и заканчивается в Vt:

с (S) = .

 

2.3. Алгоритм размещения пометок для задачи


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


Читайте в этой же книге: Введение | Виды графов | Представление графов с помощью матриц | Алгоритм Форда-Фалкерсона | Графы со многими источниками и стоками | Решение. Этап 1. | Решение. Этап 1. | Этап 3. |
<== предыдущая страница | следующая страница ==>
Потоки в сетях| О максимальном потоке

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