|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[190] некоторой вершины и в некоторую вершину v может увеличить потенциал лишь за счёт появления новой переполненной вершины v (так будет, если v - не сток и не исток), то есть не более чем на 2\V\. Наконец, ненасыщающее проталкивание из и в v уменьшает Ф по крайней мере на единицу, так как вершина и перестаёт быть переполненной и слагаемое h[u] исчезает, а появиться может лишь слагаемое h[v] (если вершина v не сток, не исток и не была переполненной), которое на единицу меньше. Таким образом, общая сумма, на которую увеличивается Ф во время работы программы, не превосходит (2У)(2У2) + (2У)(2УЯ) = 4У2(У + \Е\) (мы используем следствие 27.21 и лемму 27.22) Но Ф 0, поэтому общая сумма, на которую Ф уменьшится, и тем самым общее количество ненасыщающих проталкиванийю не превосходит 4У2(У + \Е\). Теорема 27.24 Общее число операций подъёма и проталкивания при исполнении программы Generic-Preflow-Push на сети G = (V, Е) равно 0{V2E). Доказательство Применяем следствие 27.21 и леммы 27.22, 27.23. Следствие 27.25 Алгоритм, основанный на проталкивании предпотока, можно реализовать так, чтобы на сети G = (V, Е) время его работы было 0{V2E). Доказательство Легко видеть (упр. 27.4-1), что можно выполнить подъём за время О {V) и проталкивание за время 0(1), что и даёт требуемую оценку. Упражнения 27.4-1 Как реализовать алгоритм проталкивания предпотока так, чтобы на подъём уходило время 0(V), и на проталкивание 0(1)? (При этом общее время будет 0(V2E).) 27.4-2 Докажите, что алгоритм проталкивания предпотока, на все 0(V2) подъёмов тратит 0(VE) времени. 27.4-3 Допустим, мы нашли максимальный поток в сети G методом проталкивания предпотока. Как теперь быстро найти минимальный разрез? 27.4-4 Как найти максимальное паросочетание в двудольном графе, используя метод проталкивания предпотока? Каково время работы вашего алгоритма? 27.4-5 Пусть все пропускные способности рёбер сети G = (V, Е) - це- лые числа от 1 до к. Оцените в терминах \V\, \Е\ и к время работы алгоритма проталкивания предпотока. (Указание: сколько ненасыщающих проталкиваний можно применить к ненасыщенному ребру, прежде чем оно станет насыщенным?) 27.4-6 Докажите, что строку 7 процедуры Initialize-Preflow можно заменить строкой h[s]\V[G]\-2, не нарушая корректности и не меняя асимптотики времени работы алгоритма. 27.4-7 Обозначим через Sf(u,v) расстояние (количество рёбер) от вершины и до вершины v в остаточной сети Gf. Покажите, что во время выполнения программы Generic-Preflow-Push остаётся верными следующие утверждения: если h[u] < У,то/г[и] Sf(u,t); если h[u] V, то h[u] Sf(u,s). 27.4-8* Как и в предыдущем упражнении, Sf (и, v) обозначает расстояние от вершины и до вершины v в остаточной сети Gf. Как изменить алгоритм проталкивания предпотока, чтобы во время его работы оставались верными такие утверждения: если h[u] < \V\, то h[u] = Sf (и, t); если h[u] V, то h[u] = Sf(u,s). (Дополнительные действия должны укладываться в 0(VE) операций.) 27.4-9 Покажите, что число ненасыщающих проталкиваний, выполненных программой Generic-Preflow-Push на сети G = (V,E), не превосходит 4У2£ (если \V\ 4). 27.5. Алгоритм поднять-и-в-начало Пользуясь методом проталкивания предпотока, мы применяли операции подъёма и проталкивания в более или менее произвольном порядке. Более продуманный порядок выполнения этих операций позволяет уменьшить время работы алгоритм (по сравнению с оценкой 0(V2E) из следствия 27.25). В этом разделе мы рассмотрим алгоритм «поднять-и-в-начало» (lift-to-front algorithm), использующий эту идею; время его работы есть 0(V3), что асимптотически по крайней мере не хуже, чем 0(V2E). Алгоритм «поднять-и-в-начало» хранит все вершины сети в виде списка. Алгоритм просматривает этот список, начиная с головы, и находит в нем переполненную вершину и. Затем алгоритм «обслуживает» эту вершину, применяя к ней операции подъёма и проталкивания до тех пор, пока избыток не станет равным нулю. Если для этого вершину пришлось поднять, её перемещают в на- чало списка (отсюда и название алгоритма), и просмотр списка начинается вновь. При анализе алгоритма пользуемся понятием допустимого ребра - ребра остаточной сети, по которому возможно проталкивание. Сначала мы изучим некоторые их свойства и рассмотрим процесс «обслуживания» вершины. Допустимые рёбра Пусть / - предпоток в сети G = (V, Е), a h - высотная функция. Назовем ребро (и, v) допустимым (admissible), если оно входит в остаточную сеть (с/(и, v) > 0) и h(u) = h(v) + 1 Остальные рёбра мы будем называть недопустимыми (inadmissible). Обозначим через Efth множество допустимых рёбер; сеть G/th = (V,Efth) назовём сетью допустимых рёбер (admissible network). Она состоит из рёбер, по которым возможно проталкивание. Поскольку вдоль допустимого ребра высота уменьшается, имеет место такая лемма: Лемма 27.26 (Допустимые рёбра образуют ациклический граф) Пусть / - предпоток в сети G = (V,E); пусть h - высотная функция. Тогда сеть допустимых рёбер G/th = (V,Efth) не содержит циклов. Посмотрим, как изменяют сеть допустимых рёбер операции подъёма и проталкивания. Лемма 27.27 Пусть / - предпоток в сети G = (V, Е) и h - высотная функция. Пусть (и, v) - допустимое ребро и вершина и переполнена. Тогда по (и, v) возможно проталкивание. В результате выполнения этой операции новые допустимые рёбра не появляются, но ребро (и, v) может стать недопустимым. Доказательство В результате проталкивания в остаточной сети может появиться только ребро (v,u). Поскольку ребро (и, v) допустимо, то h(v) = h(u) - 1, и потому ребро (v, и) недопустимо. Если проталкивание оказывается насыщающим, то в результате Cf(u,v) = 0 и ребро (и, v) исчезает из остаточной сети (и становится недопустимым). Лемма 27.28 Пусть / - предпоток в сети G = (V, Е) и h - высотная функция. Если вершина и переполнена и из нее не выходит допустимых рёбер, то возможен подъём вершины и. После подъёма появится по крайней мере одно допустимое ребро, выходящее из вершины и и не будет рёбер, входящих в и. Доказательство Как мы видели (лемма 27.14), в переполненной вершине и возможно либо проталкивание, либо подъём. Так как из и допустимые рёбра не выходят, то проталкивание в ней невозможно, и возможен подъём. При этом высота вершины увеличивается так, что проталкивание становится возможным, то есть появляется допустимое ребро. |
Среды: 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 | ||