![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 22, Потоки в сетях. как единого целого: мы покажем при доказательстве свойства 22.1, что объем нефти, поступающей в сток
Мы можем прямо смоделировать эту ситуацию при помощи сети (взвешенный орграф, согласно определению из главы 21), которая обладает одним истоком и одним стоком. Ребра сети соответствуют трубам нефтепровода, вершины соответствуют пересечениям труб с установленными на них вентилями, которые регулируют, сколько нефти попадает в выходное ребро, а вес, присвоенный ребру, соответствует пропускной способности труб. Мы полагаем, что ребра ориентированы, и это обстоятельство отражает тот факт, что нефть может перемещаться только в одном направлении в каждой трубе. По каждой трубе проходит определенное число единиц потока, который меньше или равен ее пропускной способности, и каждая вершина удовлетворяет условию равновесия, суть которого заключается в том, что входной поток равен выходному потоку. Абстракция транспортной сети представляет собой полезную модель решения задач, которая прямо применяется к широкому кругу приложений, а косвенно — к еще более широкому кругу приложений. Иногда мы обращаемся к представлению нефти, текущей по нефтепроводу, в стремлении отыскать интуитивную поддержку базовых идей, в то же время наши рассуждения одинаково применимы как к товарам, перемещающимся по распределительным каналам, так и к другим многочисленным ситуациям. Модель потоков применяется непосредственно к сценарию распределения: мы интерпретируем размеры потоков как их интенсивность, так что транспортная сеть описывает потоки товаров точно так же, как и потоки нефти. Например, мы можем интерпретировать поток, представленный на рис. 22.5, как факт, определяющий необходимость переправки двух элементов в единицу времени из вершины 0 в 1 и из 0 в 2, одного элемента в единицу времени из 0 в 2, одного элемента в единицу времени из 1 в 3 и из 1 в 4 и т.д. Другая интерпретация модели потоков для сценария распределения заключается в том, что потоки интерпретируются как объемы поставляемых товаров с той характерной особенностью, что сеть описывает только одноразовую поставку товара. Например, мы можем интерпретировать поток, представленный на рис. 22.5, как поставку четырех единиц товара из вершины 0 в 5 в рамках следующего трехэтапного процесса: сначала пересылаются две единицы товара из 0 в 1 и две единицы из 0 в 2, так что в каждой из этих вершин оседают по две единицы товара. Далее производится пересылка по одной единице товара из 1 в 3, из 1 в 4, из 2 в 3 и из 2 в 4, при этом в каждой из вершин 3 и 4 остается по две единицы товара. И, наконец, пересылка завершается доставкой двух единиц товара из вершины 3 в 5 и из 4 в 5. Как и в случае использования расстояния в алгоритмах поиска кратчайшего пути, мы вполне можем, когда это удобно, отказаться от любой физической интерпретации, поскольку все рассматриваемые нами определения, свойства и алгоритмы основаны исключительно на абстрактной модели, которая не обязательно подчиняется физическим зако- Часть 5. Алгоритмы на графах
Определение 22.1. Будем называть сеть с вершиной s, выбранной в качестве истока, и с вершиной t, выбранной в качестве стока, st-сетью. В этом определении мы используем понятие " выбранный", которое означает, что вершина s не обязательно должна быть истоком (вершина, у которой отсутствуют входящие ребра), а вершина t — стоком (вершина, у которой отсутствуют исходящие ребра), но, тем не менее, они рассматриваются именно в этом качестве, поскольку в наших рассуждениях (и в предлагаемых нами алгоритмах) игнорируются ребра, направленные в s, и ребра, исходящие из. Во избежание путаницы, в примерах мы будем рассматривать сети с одним истоком и стоком; ситуацию более общего характера мы рассмотрим в разделе 22.4. Мы будем называть вершины s и /, соответственно, " истоком" и " стоком" st- сети, поскольку именно эти роли они исполняют в рассматриваемой сети. Остальные вершины сети мы будем называть внутренними вершинами. Определение 22.2. Транспортная сеть (flow network) есть st-сеть с положительными весами ребер, которые мы будем называть пропускными способностями (capacities). Поток (flow) в транспортной сети есть множество ребер с неотрицательными весами, в дальнейшем реберными потоками (edge flows), которые удовлетворяют требованию того, что ни один поток в ребре не может быть больше пропускной способности ребра и что суммарный поток, поступающий в каждую внутреннюю вершину, равен суммарному потоку, вытекающему из этой вершины. Мы будем называть суммарный поток, устремленный в некоторую вершину, притоком (inflow) 4-5 3 2 РИСУНОК 22.6. УПРАВЛЕНИЕ ПОТОКАМИ В СЕТИ Открыв вентили вдоль пути 0-1-3-5, мы можем инициировать в этой сети поток, который может перемещать две единицы потока (диаграмма вверху); открыв вентили вдоль пути 0-2-4-5, мы получаем еще одну единицу потока в сети (диаграмма в центре). Звездочками отмечены заполненные ребра. Поскольку ребра 0-1, 2-4 и 3-5 наполнены, прямого способа увеличить поток из 0 в 5 не существует, но если мы откроем вентиль в вершине 1, чтобы перенаправить достаточную часть потока с тем, чтобы заполнить ребро 1-4, мы увеличиваем пропускную способность ребра 3-5, которой достаточно для увеличения потока на пути 0-2-3-5, благодаря чему достигается максимальный поток рассматриваемой сети (диаграмма внизу).
|