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

Естественная цель для заданной потоковой сети состоит в организации трафика, обеспечивающей как можно более эффективное использование доступной про- пускной способности. Таким образом, основная алгоритмическая задача, которая будет рассматриваться в этой главе, формулируется так: для потоковой сети найти поток максимально возможной величины.

Размышляя над алгоритмом для этой задачи, необходимо учитывать, что струк- тура потоковой сети устанавливает верхние границы для максимальной величины потока s-t. Основное «препятствие» для существования больших потоков заключа- ется в следующем: предположим, узлы графа разделены на два множестваA и B так, что 5 A и t B. Интуитивно ясно, что любой поток, проходящий от 5 к t, должен в какой-то момент переходить из A в B — а следовательно, заполнять часть про- пускной способности ребер из A в B. Из этого следует, что каждый такой «разрез» графа устанавливает ограничение на максимально возможную величину потока.

Алгоритм нахождения максимального потока, который мы разработаем в этом разделе, будет объединен с доказательством того, что величина максимального потока равна минимальной пропускной способности любого такого разбиения, на- зываемого минимальным разрезом. Дополнительно наш граф также будет вычислять минимальный разрез. Вы увидите, что задача нахождения разрезов с минимальной пропускной способностью в потоковой сети полезна с точки зрения ее возможных практических применений — например, при нахождении максимального потока.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. коян: Восходящий узел - включение в общий поток; Нисходящий узел - исключение из общего потока.
  2. Наличие максимально полной информации о допрашиваемом
  3. 6. Таблица минимальных и максимальных размеров и сроков наказаний по Уголовному кодексу РФ 1996 г.
  4. Альбатрос (восхождение на поток)
  5. ТЕОРИЯ ПОТОКА СОЗНАНИЯ
  6. 3.9. ПОТОК СОЗНАНИЯ
  7. ПОТОК СОЗНАНИЯ
  8. 2.2.1. Поток образов
  9. Глава 3. ОТКРОЙТЕ СВОЙ ПОТОК ОБРАЗОВ
  10. 12.2.1. Групповой поток образов