|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[186] Заметим, что расстояния ограничены сверху значением V (кратчайший путь не проходит дважды через одну вершину), так что общее число таких чередований есть 0(V), как мы и обещали. Подсчитаем теперь общее время работы алгоритма Эдмондса-Карпа. Каждая итерация требует времени О(Е), их будет 0(VE), поэтому всего будет 0(VE2). В разделе 27.4 мы расскажем о другом подходе к поиску максимального потока, который позволяет сделать это за 0(V2E). Его усовершенствование позволяет ещё уменьшить время работы, получив оценку 0(V3) (раздел 27.5). Упражнения 27.2-1 Найдите поток через разрез ({s, v2, V4}, {v\, v3, t}) на рис. 27.1 b). Чему равна пропускная способность этого разреза? 27.2-2 Проследите за выполнением лгоритма Эдмондса-Карпа для сети рис. 27.1 (а). 27.2-3 Укажите минимальный разрез на рис. 27.6, соответствующий нарисованному максимальному потоку. В каких случаях дополняющий путь уменьшал поток, идущий в обратном направлении? 27.2-4 Докажите, что для любых вершин и и v, любого потока / и пропускной способности с выполнено Cf(u, v)-\-cj(v, и) = с(и, v)-\-c(v, и). 27.2-5 Вспомним конструкцию из раздела 27.1, с помощью которой сеть с несколькими истоками и стоками сводится к обычной. Докажите, что если пропускная способность любого ребра исходной сети была конечной, то в получившейся сети величина любого потока конечна. 27.2-6 Рассмотрим сеть с несколькими истоками и стоками, в которой каждый исток s4- производит ровно рг- единиц потока, а каждый сток tj потребляет ровно qj единиц, т.е. f(si, V) = pi и f(V, tj) = qj. При этом 2~}гРг = 2~}j Qj- Как узнать, возможен ли поток с такими ограничениями, сведя эту задачу к задаче о максимальном потоке? 27.2-7 Докажите лемму 27.3. 27.2-8 Покажите, что при поиске максимального потока в сети G = (V, Е) достаточно сделать \Е\ шагов, если только правильно выбрать дополняющие пути на каждом шаге. (Указание. Считая, что максимальный поток известен, покажите, как следует выбирать пути.) 27.2-9 Назовём запасом связности (edge connectivity) неориентирован- ного графа минимальное число рёбер, которое необходимо удалить, чтобы сделать граф несвязным. Например, связность дерева равна единице, а связность цикла равна 2. Как узнать связность графа с помощью программы поиска максимального потока? Её следует применять не более чем к \V\ сетям, каждая из которых содержит 0(V) вершин и О(Е) рёбер. 27.2-10 Предположим, что для каждого ребра (и, v) сети обратное ему ребро (v, и) также входит в сеть Покажите, что алгоритм Эдмондса-Карпа требует не более \V\ \Е\/4 итераций. (Указание: для каждого ребра (и, v) проследите, как меняются S(s,u) и S(v,t) между теми моментами, когда ребро (и, v) критическое.) 27.3. Максимальное паросочетание в двудольном графе Некоторые комбинаторные задачи (например, задача о сети с несколькими истоками и стоками из раздела 27.1) сводятся к разобранной нами задаче о максимальном потоке. Другой пример такого рода - задача о максимальном паросочетании в двудольном графе (см. раздел 5.4). В этом разделе покажем, как с помощью метода Форда-Фалкерсона можно решить эту задачу для графа G = (V, Е) за время 0(VE). Задача о максимальном паросочетании Пусть G = (V, Е) - неориентированный граф. Паросочетанием (matching) назовем множество рёбер М С Е, не имеющих общих концов (каждая вершина v £ V является концом максимум одного ребра из М). Будем говорить, что вершина v £ V входит в паросочетание М (is matched), если в М есть ребро с концом v; в противном случае v свободна (is unmatched). Максимальное паросочетание (maximum matching) - это паросочетание М, содержащее максимально возможное число рёбер (\М\ М для любого паросочетания М). Пример паросочетания приведён на рис. 27.8. В этом разделе мы будем рассматривать паросочетания лишь в двудольных графах. Мы предполагаем, что множество V разбито на два непересекающихся подмножества L и R, и любое ребро из Е соединяет некоторую вершину из L с некоторой вершиной из R. Для задачи о максимальном паросочетании в двудольном графе есть несколько метафор. Вот наиболее известная: L - женихи, R - невесты, наличие ребра (и, v) означает, что и и v согласны стать супругами. Максимальное паросочетание доставляет ЗАГСу Рис. 27.8 27.8 Двудольный граф. Множество вершин разбито на две части L и R. (а) Паросочетание из двух рёбер. (Ь) Максимальное паросочетание состоит из трёх элементов. Рис. 27.9 27.9 Сеть, соответствующая двудольному графу, (а) Двудольный граф рис. 27.8. Выделенные рёбра образуют максимальное паросочетание. (Ь) Соответствующая сеть G и максимальный поток в ней. Пропускная способность любого ребра равна единице; поток по выделенным рёбрам равен единице, по остальным - нулю. Выделенные рёбра, соединяющие вершины из L с вершинами из R, соответствуют максимальному паросочетанию в двудольном графе. больше всего работы. Поиск максимального паросочетания в двудольном графе Мы будем использовать метод Форда-Фалкерсона для поиска максимального паросочетания в двудольном графе G = (V, Е) за полиномиальное от \V\ и \Е\ время. Для этого рассмотрим сеть G = (V,E), соответствующую двудольному графу G (рис. 27.9). Эта сеть строится так: добавяляются две новые вершины, которые будут истоком (s) и стоком (t): V = V U {s,t}. Множество (направленных) рёбер сети G таково: Е ={(s,u)\u £ L} U U {(и, v)\u е L, v е R, (и, v) £ Е} и {{v,t)\veR}. (напомним, что через L и R обозначаются доли графа). Будем считать, что пропускная способность каждого ребра равна единице. Следующая лемма устанавливает соответствие между потоками в G и паросочетаниями в G - но прежде дадим ещё одно определение. Поток / в сети G = (V, Е) называется целочисленным (integer-valued), если все значения f(u,v) - целые. Лемма 27.10 Пусть G = (V, Е) - двудольный граф с долями L и R, и G = (V, Е) - соответствующая сеть. Пусть М - паросочетание в G. Тогда существует целочисленный поток в G со значением / = \М\. Обратно, если / - целочисленный поток в G, то в G найдется паросочетание из / элементов. Доказательство Сначала докажем, что паросочетание порождает поток, задав поток / следующим образом. Если (и, v) £ М, то f(s, и) = f(u, v) = f(v,t) = 1 и f(u,s) = f(v,u) = f(t,v) = -1. Для всех остальных рёбер (и, v) £ Е положим f(u, v) = 0. Неформально говоря, каждое ребро (и, v) £ М соответствует единичному потоку по пути s -> и -> v -> t. Никакие два таких пути не содержат общих вершин (кроме истока и стока) или рёбер. Чтобы проверить, что / является потоком, достаточно заметить, что / представим в виде суммы потоков по этим путям. Поток через разрез (LL){s}, RL){t}) равен \М\, поэтому по лемме 27.5 значение потока / равно \М\. |
Среды: 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 | ||