|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[188] которого ведёт ненасыщенная труба - другими словами, мы поднимаем и ровно настолько, чтобы появилась ненасыщенная труба, ведущая вниз. В конце концов мы добьёмся того, что в сток приходит максимально возможное количество жидкости (для данных пропускных способностей труб). При этом предпоток может ещё не быть потоком (избыток жидкости сливается). Продолжая подъём вершин (которые могут стать выше истока), мы постепенно отправим избыток обратно в исток (что означает сокращение потока жидкости от истока) - и превратим предпоток в поток (который окажется максимальным). Основные операции Итак, алгоритм проталкивания предпотока использует две основные операции: проталкивание потока из вершины в соседнюю и подъём вершины. Дадим точные определения. Пусть G = (V, Е) - сеть с истоком s и стоком t, а / - предпоток в G. Функция h : V -> N называется высотной функцией (height function) для предпотока /, если h(s) = \V\, h(t) = 0 и h(u) h(v) + 1 для любого остаточного ребра (и, v) £ Ef. Следующая лемма даёт очевидную переформулировку этого условия: Лемма 27.13 Пусть / - предпоток в сети G = (V, Е) и h - высотная функция. Тогда если для вершин и, v £ V, выполнено h(u) > h(v) + 1, то остаточная сеть не содержит ребра (и, v) («по круто идущим вниз трубам идёт максимально возможный поток».) Теперь определим основные операции. Процедура Push (и, v) применима, если вершина и переполнена (то есть Cf(u, v) > 0) и если h(u) = h(v) + 1. При этом поток из вершины и в её соседа v растёт - его увеличение ограничено избытком жидкости вии остаточной пропускной способностью ребра (u,v). \textsc{Push>($u,v$) 1$\triangleright$ дано: вершина $u$ переполнена, $c f(u,v)>0$ и $h(u)=h(v)+l$. 2$\triangleright$ надо: протолкнуть $d f(u,v)=\min(e[u],c f(u,v)$ единиц потока из $u$ в $v$ 3$d f(u,v)\leftarrow\min(e[u],c f(u,v)$ 4$f[u,v]\leftarrow f[u,v]+d f(u,v)$ 5$f[v,u]\leftarrow -f[u,v]$ 6$e[u]\leftarrow e[u]-d f(u,v)$ 7$e[v]\leftarrow e[v]+d f(u,v)$ Мы предполагаем, что избыток в вершине равен е[и] > 0, и что остаточная пропускная способность ребра (и, v) также положи- тельна. Поэтому мы можем направить тт(е[и], Cf(u, v)) > 0 единиц потока из и в v (мы вычисляем эту величину в строке 3), не превысив пропускной способности и не сделав избыток отрицательным. Следовательно, если функция / останется предпотоком (если он им была). Мы изменяем / в строках 4-5 и е в строках 6-7. Условие h(u) = h(v) + 1 гарантирует, что мы направляем дополнительный поток лишь по рёбрам, идущим вниз с единичной разницей высот. Впрочем, более крутые рёбра уже насыщены и так (лемма 27.13) Операция Push называется проталкиванием из вершины и в вершину v (применённым к вершине и). Проталкивание называется насыщающим (saturating), если в результате ребро (и, v) становится насыщенным (saturated), то есть если Cf(u,v) обращается в нуль (ребро исчезает из остаточной сети); в противном случае проталкивание считают ненасыщающим (nonsaturating). Процедура Lift (и) поднимает переполненную вершину и на максимальную высоту, которая допустима по определению высотной функции. Посмотрим на соотношение высот вершины и её соседей в остаточной сети. По определению высотной функции высота вершины превосходит высоту соседа в остаточной сети не более чем на 1. Если есть сосед, который на единицу ниже, то можно выполнить проталкивание (но нельзя выполнить подъём). Если все соседи не ниже, то проталкивание выполнить нельзя, а подъём - можно, после чего возможно проталкивание. Вот как выглядит процедура подъёма (lifting): \textsc{Lift}($u$) 1$\triangleright$ дано: вершина $u$ переполнена; для любого ребра $(u,v)\in E f$ выполнено неравенство $h(u)\le h(v)$. 2$\triangleright$ надо: увеличить $h[u]$, подготовляя проталкивание из вершины $и$ 3$h[u]\leftarrow l+\min\{h[v]I(u,v)\ in E f\}$ Заметим, что если вершина и переполнена, то в Ef найдётся по крайней мере одно ребро, выходящее из и (минимум в строке 3 берётся по непустому множеству). Чтобы доказать это, вспомним, что f[V, и] = е[и] > 0, поэтому существует по крайней мере одна такая вершина v, для которой f(v, и) > 0. Получаем С/(и, v) = с(и, v) - f[u, v] = с(и, v) + f[v, и] > 0, а это означает, что (и, v) £ Ef. (Если в вершине жидкость выливается, то она откуда-то приходит, и есть резерв, состоящий в уменьшении этого прихода.) Общая схема алгоритма Алгоритм начинается с вызова Initialize-Preflow, задающего начальный предпоток: f[u,v]={ с(и, v) если и = s, c(v, и) если v = s, О в остальных случаях. (27.9) \textsc{Initialize-Preflow}($G,s$) 1for (для) каждой вершины $u\in V[G]$ 2do $h[u]\leftarrow 0$ $e[u]\leftarrow 0$ 4for (для) каждого ребра $(u,v)\in E[G]$ 5do $f[u,v]\leftarrow 0$ 6$f[v,u]\leftarrow 0$ 7$h[s]\leftarrow V[G]$ 8for (для) каждой вершины $u\in Adj[s]$ 9do $f[s,u]\leftarrow c(s,u)$ 10$f[u,s]\leftarrow -c(s,u)$ 11$e[u]\leftarrow c(s,u)$ В массиве h хранятся высоты, в массиве е - избытки, с(и, v) - пропускные способности (считаем, что они заданы так, что вычисление с(и, v) требует времени 0(1)). Поток записывается в массив Поток по каждому ребру, выходящему из истока s, становится равным пропускной способности этого ребра. По остальным рёбрам поток равен 0. В каждой смежной с истоком вершине v появляется избыток e[v] = c(s, v). Начальная высота задается формулой Это действительно высотная функция, так как рёбра (и, v), для которых h[u] > h[v] + 1, выходят только из истока (и = s), но эти рёбра насыщены и их нет в остаточной сети. Программа Generic-Preflow-Push даёт общую схему алгоритма, основанного на проталкивании предпотока. \textsc{Generic-Preflow-Push} 1\textsc{Initialize-Preflow} 2while (пока) возможны операции подъ\"~~а5ма или проталкивания 3do выполнить одну из этих операций Следующая лемма показывает, что пока есть хоть одна переполненная вершина, какая-то из операций подъёма или проталкивания возможна. О, в противном случае. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||