![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 22. Потоки в сетях. же пропускной способностью и чтобы вершины ии и* входили в одно и то же множество для всех и, так что в соответствии с изложенным в предыдущем абзаце
Если в преобразованной сети задан какой-либо поток величины с + X, то мы просто мы назначаем каждому соответствующему ребру в исходной сети поток величины с. Преобразование сечения, описанное в предыдущем абзаце, не затрагивает это назначение, поскольку оно манипулирует ребрами, в которых поток равен 0. ■ В результате такого сведения мы не только получаем ациклическую сеть, мы получаем простую двудольную структуру. Это сведение говорит о том, что мы можем, если захотим, принять эти сети, обладающие более простой структурой, в качестве стандартных вместо сетей общего вида. Сначала кажется, что такая специальная структура позволяет создавать алгоритмы вычисления максимального потока, обладающие более высоким быстродействием. Однако описанное выше сведение показывает, что мы могли использовать любой алгоритм, разработанный для таких специальных видов сетей, какими являются ациклические сети, для решения задач о максимальном потоке в сетях общего вида ценой достаточно скромных дополнительных затрат. В самом деле, классические алгоритмы вычисления максимального потока используют гибкость модели сети общего вида: оба рассмотренных нами выше подхода, а именно, алгоритмы вычисления аугментальных путей и выталкивания избыточных потоков, используют принцип остаточной сети, предусматривающий введение циклов в сеть. Когда нам приходится решать задачу о максимальном потоке применительно к ациклической сети, для ее решения мы обычно используем стандартный алгоритм, ориентированный на сети общего вида. Доказательство свойства 22.16 довольно сложное, оно показывает, что доказательства, использующие принцип сведения, требуют особого внимания, если не сказать - изобретательности. Такие доказательства важны уже потому, что не все версии задачи о максимальных потоках эквивалентны стандартной задаче, а мы желаем знать пределы, в каких мы можем применять наши алгоритмы. Математики продолжают исследование в этой области, поскольку сведение различных практических задач к другим задачам еше не установлено, как показывают следующий пример. Максимальный поток в неориентированных сетях. Неориентированная транспортная сеть есть взвешенный граф с целочисленными весами ребер, которые мы интерпретируем как пропускные способности. Циркуляцией в таких сетях является назначение весов и направлений ребрам, удовлетворяющих условию, согласно которому поток в каждом ребре не может превышать его пропускной способности, а суммарный поток, поступающий в каждую вершину, равен суммарному потоку, покидающему эту вершину. Задача о неориентированном максимальном потоке состоит в том, чтобы найти циркуляцию, которая доводит поток в заданном направлении до максимально возможного значения в заданном ребре (т.е. из некоторой заданной вершины s в другую заданную вершину t). Эта Часть 5. Алгоритмы на графах
также верно: если в неориентированной сети через ребро u-v протекает поток f, через ребро v-u протекает поток g, то мы можем поместить поток f- g в ребро u-v ориентированной сети, если f> g; в противном случае это будет поток g—f в ребре v-u. Следовательно, любой максимальный поток в ориентированной сети есть максимальный поток в неориентированной сети: это построение дает поток, и любой поток в ориентированной сети большей величины будет соответствовать некоторому потоку большей величины в неориентированной сети; однако такого потока не существует. ■ Это доказательство не утверждает, что задача о максимальном потоке в неориентированной сети эквивалентна стандартной задаче. Иначе говоря, вполне может случиться, что вычисление максимальных потоков в неориентированных сетях легче, чем вычисление максимальных потоков в стандартных сетях (см. упражнение 22.81). В целом мы можем применять к сетям со многими стоками и истоками, неориентированным сетям, к сетям с ограничениями на пропускные способности вершин и многим другим типам сетей (см., например, упражнение 22.79) алгоритмы вычисления максимального потока для st-сетей, рассмотренные в двух предыдущих разделах. Фактически свойство 22.16 утверждает, что мы можем решить все эти задачи даже при помощи алгоритма, который работает только на ациклических сетях. Далее, мы рассматриваем задачу, которая не является чисто задачей о максимальном потоке, но которую мы можем свести к задаче о максимальном потоке и решить ее с помощью алгоритмов вычисления максимального потока. Это один из способов формализовать базовую версию задачи распределения товаров, описание которой дано в начале данной главы. РИСУНОК 22.34. СВЕДЕНИЕ ЗАДАЧИ О ПОТОКАХ В
|