|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[182] Рис. 27.2 27.2 Сокращение, (а) Вершины vi и V2. Здесь c(vi,V2) = 10 и c(v2, vi) = 4. (b) Ежедневно 8 ящиков перевозят из vi в V2. (с) Добавили встречные перевозки 3 ящиков в день из V2 в v\. (d) Сократили противоположные потоки - осталось 5 ящиков в день, (е) Добавили перевозку ещё 7 ящиков в день из V2 в vi. Рис. 27.3 27.3 Задача о максимальном потока для нескольких истоков и стоков сводится к обычной, (а) Сеть с пятью истоками S = {si, S2, S3, S4, s5} и тремя стоками Т = {ti, t2, Ьз}. (b) Сооответствующая сеть с одним истоком и одним стоком; добавленные рёбра имеют бесконечную пропускную способность. хватит или они будут накапливаться). Тем самым выполнено свойство сохранения потока. Величиной потока будет число шайб, ежедневно отгружаемых из Ванкувера, и нас интересует поток максимальной величины. Один из возможных потоков показан на рис.27.1(b). Из вершины и в вершину v в день отправляется f(u, v) ящиков; если f(u, v) равно 0, ящики не отправляются; отрицательные значения f(u, v) соответствуют ящикам, прибывающим в и из v. Внимательный читатель мог уже заметить, что реальная ситуация не вполне описывается нашей моделью. Именно, наша модель не учитывает встречные перевозки. Если из вершины v\ в v2 ежедневно везут восемь ящиков, а из v2 в v\ ежедневно везут три ящика, чему должны быть равны f(vi,v2) и f(v2,v\)l (Напомним, что эти величины должны быть противоположны.) Мы полагаем f(vi,v2) = 8 - 3 = 5, a f(v2,vi) = -5. Те же значения функции / соответствуют ежедневным перевозкам пяти ящиков из v\ в v2, так что в нашей модели встречные перевозки автоматически сокращаются. Впрочем, и в реальности встречные перевозки разумно «сократить» друг с другом, (экономика должна быть экономной), при этом места на грузовиках понадобится только меньше. На рис. 27.2 показан пример сокращения потоков между вершинами v\ и v2 (27.2 (а)). Сначала из v\ в v2 возили ежедневно 8 ящиков (27.2 (Ь)). Затем стали возить 3 ящика в обратном направлении (27.2 (с)), пока не догадались вместо этого уменьшить число перевозимых в обратную сторону ящиков на 3 (27.2 (с!)). Эти две различные (в жизни) ситуации соответствуют одной и той же функции /: в обоих случаях f(v\,v2) = 5, a f(v2,vi) = -5. Если теперь руководство требует начать перевозки дополнительных 7 ящиков в день из v2 в v\, то нужно прежде всего отменить перевозки 5 ящиков в обратную сторону, после чего назначить перевозку дополнительных 2 ящиков (27.2 (е)). Тем самым требование будет выполнено (несмотря на то, кстати, что в грузовиках из v2 в v\ есть места только на 4 ящика. Сети с несколькими истоками и стоками Можно рассматривать задачу о максимальном потоке для слу- чая нескольких истоков и стоков. Компания «Кленовые листья» может иметь то фабрик {si, s2,.. -sm} и п складов {t\, t2, , tn} (рис. 27.3 (а)). Но это не усложняет дела, потому что такой вариант проблемы можно свести к обычному. На рис. 27.3 (Ь) показана эквивалентная сеть с одним истоком и одним стоком. Мы добавили общий исток (supersource) s, из которого ведут рёбра бесконечной пропускной способности во все прежние истоки (c(s, s8) = 00 при всех г = 1,2,..., то). Аналогичным образом из всех прежних стоков проведены рёбра в общий сток (supersink) t. Легко видеть, что каждый поток в сети (а) соответствует потоку в сети (Ь) и наоборот (формальное доказательство оставляется читателю в качестве упр. 27.1-3) Обозначения Мы будем использовать следующее соглашение: если в выражении на месте вершины стоит множество вершин, то имеется в виду сумма по всем элементам этого множества (неявное суммирование, inplicit summary notation). Это относится и к случаю нескольких переменных. Например, если А и У - множества вершин, то дх,у) = ЕЕЛжу)- хех yeY В этих обозначениях закон сохранения потока запишется как f(u, V) = 0 для всех и £ V - {s,t}. Кроме того, в неявных суммах мы опускаем фигурные скобки (например, в равенстве f(s, V\s) = f(s, V) символ V \ s обозначает V \ {s}. Вот несколько полезных свойств таких сумм (доказательство мы оставляем читателю как упр. 27.1-4): Лемма 27.1 Пусть / - поток в сети G = (V,E). Тогда для любого X С У выполнено f(X,X) = 0. Для любых X, Y С V выполнено f(X,Y) = -f(Y,X). Для любых X, Y, Z С V из X П У = 0 следует f(X UY,Z) = f(X, Z) + f(Y, Z) и f(Z,XUY) = f(Z,X) + f(Z,Y). Для примера докажем с использованием таких обозначений, что величина потока равна сумме потоков из всех вершин в сток: \f\=f(V,t). (27.3) Интуитивно это ясно (куда ж ему ещё деваться), но можно провести и формальное рассуждение. Вот оно: По определению, \f\ = f(s,V) Применяя лемму 27.1, имеем f(s, V) = f(V, V) - f(V \s,V) = f(V, V\s) = f(V, t) + f(V,V\s\t). По закону сохранения потока второе слагаемое равно 0, и остаётся f(V,t). Обобщение леммы 27.1 будет доказано ниже (лемма 27.5) Упражнения 27.1-1 Следуя образцу рис. 27.2, изобразите две вершины и и v, для которых с(и, v) = 5, c(v, и) = 8, из и в v пересылаются 3 единицы, а из v в и - 4. Чему равен поток из и в и? 27.1-2 Проверьте, что функция / рис.27.1 (Ь) действительно является потоком. 27.1-3 Как приспособить определение потока для случая нескольких истоков и стоков? Покажите, что задача о максимальном потоке для такого случая сводится к обычной с помощью описанного нами приёма. 27.1-4 Докажите лемму 27.1. 27.1-5 Для сети G = (V, Е) и потока / на рис.27.1 (Ь), укажите пример подмножеств X, Y С V, для которых f(X, У) = -f(V\X,Y, а также подмножеств X, Y С V, для которых f(X, У) ф - f(V\X, Y. 27.1-6 Пусть имеется сеть G = (V, Е) и два потока fi и f2 на ней. Рассмотрим их сумму (функцию из V X V в Ж): (Л + /2)(Щ v) = Ми, v) + f2(u, v)(27.4) Каким требованиям из определения потока она удовлетворяет обязательно, а каким может не удовлетворять? 27.1-7 Поток / можно умножить на вещественное число а, получив функцию (af)(u,v) = а f(u,v) Докажите, что для любой сети множество потоков выпукло. Это значит, что если fi и f2 - потоки, то сумма afi + (1 - си)/2 при О а 1 тоже является потоком. 27.1-8 |
Среды: 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 | ||