1. Основные понятия теории множеств. Способы задания множеств. Операции над множествами. Теоретикомножественные тождества
 Скачать 4.95 Mb.
|
|
28. Задача о максимальном потоке и ее возможные варианты. Определение транспортной сети, потока в сети и разреза. Теорема Форда-Фалкерсона. Одной из наиболее интересных и важных задач теории графов является задача определения максимального потока, протекающего от некоторой вершины графа (источника) к некоторой конечной вершине (стоку). При этом каждой дуге графа приписана некоторая пропускная способность , и эта пропускная способность определяет наибольшее значение потока, который может протекать по данной дуге. Метод решения задачи о максимальном потоке (от к ) предложен Фордом и Фалкерсоном. Рассмотрим возможные варианты задачи о максимальном потоке. Задача нахождения допустимого потока минимальной стоимости. Допустим, что каждой дуге графа приписана не только пропускная способность , дающая верхнюю границу потока через дугу , но также пропускная способность , дающая нижнюю границу потока через эту дугу. В общем случае может существовать много потоков, удовлетворяющим требованиям о максимальной и минимальной пропускных способностях дуг. Если в дополнение к пропускным способностям заданы также стоимости единицы потока, протекающего по дуге, то возникает задача нахождения допустимого потока минимальной стоимости. Задача о многопродуктовом потоке.Эта задача возникает, если в сети имеется несколько источников и стоков, между которыми протекают потоки различных продуктов. В этой задаче пропускная способность является ограничением для суммы всех потоков всех видов продукции через эту дугу. Задача о потоках с выигрышами. Во всех рассмотренных выше случаях неявно допускалось, что поток на входе дуги такой же, как и на выходе. Если рассмотреть граф, в котором выходной поток дуги равен ее входному потоку, умноженному на некоторое неотрицательное число, то задачу о максимальном потоке называют задачей о потоках с выигрышами. В такой задаче потоки могут «порождаться» и «поглощаться» самим графом, так что поток, входящий в , и поток, покидающий , могут изменяться совершенно независимо. Граф, некоторые вершины которого выделены, называется сетью. Выделенные вершины называются полюсами сети. Например, дерево с корнем можно рассматривать как однополюсную сеть. Вершины, отличные от полюсов, называются внутренними вершинами сети. Ребро, инцидентное хотя бы одному полюсу, называется полюсным ребром. Остальные ребра называются внутренними. -полюсником называется сеть с полюсами, разбитыми на два класса: входных и выходных полюсов. (1,1)-полюсник называется также двухполюсной сетью. Далее будут рассматриваться только двухполюсные сети, которые будем называть просто сетями. Будем называть также цепью (без указания концов) элементарную цепь между полюсами сети. В противном случае будем указывать концы цепи и называть ее цепочкой. Транспортной называется двухполюсная сеть, в которой каждой дуге приписано целое неотрицательное число , называемое пропускной способностью дуги. Можно дать различные интерпретации транспортной сети. Пусть, например, в полюсе имеется неограниченный запас некоторого продукта и нужно организовать доставку этого продукта в полюс по сети путей сообщения с некоторыми промежуточными вершинами. В этом случае пропускная способность дуги – количество груза, которое можно перевезти в единицу времени по данной дуге. Тогда возникает задача: организовать перевозки по сети таким образом, чтобы, не превышая пропускных способностей дуг, перевозить из в максимальное количество груза в единицу времени. Для каждой вершины сети обозначим через множество всех дуг, входящих в , а через – выходящих из . Для источника и стока имеем . Потоком в сети называется целочисленная функция , определенная на дугах сети и удовлетворяющая условиям: , ; (1) , ( , , ). (2) Второе условие называют уравнением сохранения. Оно представляет собой для каждой внутренней вершины сети закон Кирхгофа, согласно которому сумма значений потока по ребрам, входящим в вершину, равна сумме значений потока по ребрам, исходящим из вершины. На рис. 1 приведен пример сети , в которой каждой дуге приписана двойка . 8,8 7,6 2,2 2,0 5,5 9,7 Рис. 1. Пример транспортной сети Если сложить уравнения сохранения для всех вершин, то останутся только члены, соответствующие дугам и : . Таким образом, для любого потока величина груза, выходящего из источника равна величине груза, прибывающего в сток . Эту величину обозначают и называют величиной потока: . Поток в сети, имеющий наибольшую величину, называется максимальным. Основная задача состоит в нахождении максимального потока для данной транспортной сети. Для ее решения используют специальные подмножества дуг сети, называемые разрезами или сечениями. Разрезом сети называется множество ребер, при удалении которого сеть становится несвязной, причем полюсы попадают в разные компоненты связности. Очевидно, что любая цепь проходит через одно ребро разреза. Пусть – некоторое подмножество вершин сети, для которого полюс , а другой полюс . Обозначим – дополнение множества до множества . Тогда , а . Множество дуг сети, имеющих начало в , а конец в , называется разрезом, порождаемым множеством вершин , и обозначается . Например, для сети на рис. 1 выберем . Тогда . Имеем разрез . Ребро разреза называется прямым, если оно ориентировано слева направо, и обратным – в противном случае. Сумма пропускных способностей всех прямых дуг разреза называется пропускной способностью разреза и обозначается . Разрезы, которые обладают наименьшей возможной пропускной способностью, называются минимальными. В 1955 г. Форд и Фалкерсон доказали следующую теорему о максимальном потоке и минимальном разрезе. Теорема. Максимальная величина потока в сети равна пропускной способности любого минимального разреза. Доказательство. Докажем сначала, что величина любого потока не превосходит пропускной способности любого разреза: . Просуммируем уравнения сохранения (2) по всем вершинам . Получим , (3) где значения коэффициентов зависят от расположения концов дуги относительно множеств и . На рис. 2 показаны шесть возможных вариантов такого расположения. 2 3 5 1 6 4 Рис. 2. Возможные расположения концов произвольной дуги 1. . В этом случае в ходит в складываемые уравнения дважды: со знаком ”+” для вершины и со знаком ”–” для вершины . Следовательно, . 2. . В этом случае в ходит только в уравнение сохранения для вершины , поэтому . 3. . В этом случае в ходит только в уравнение сохранения для вершины , поэтому . 4. . В этом случае , т. к. нет в складываемых уравнениях. 5. . Результат аналогичен п. 3. 6. . Результат аналогичен п. 4. Для дуг шестого типа в сумму (3) добавим и вычтем . Тогда для дуг, выходящих из источника ( ), и дуг, идущих против разреза ; для дуг разреза ; для остальных дуг. Перепишем уравнение (3) в виде , откуда для любого потока и любого разреза . (4) Отсюда следует, что максимальное значение потока в сети равно минимальному значению пропускных способностей разрезов этой сети: . 29. Определение прибавляющей цепи. Алгоритм Форда-Фалкерсона построения максимального потока в транспортной сети. Из теоремы Форда-Фолкерсона следует, что максимальный поток в сети не превосходит минимальной пропускной способности разреза, то есть . (1) Анализ неравенства (1) показывает, что величина потока совпадает с пропускной способностью разреза тогда и только тогда, когда выполняется условие: (2) Алгоритм, который приводится ниже, направлен на построение такого разреза, для которого выполняется условие (2). Если удается построить такой разрез, то задача решена, если нет, то производится увеличение потока с помощью прибавляющих цепей. Дадим определение прибавляющей цепи. Рассмотрим в сети цепь из источника в сток, то есть последовательность вершин такую, что между вершинами и есть дуга ( ), которой может оказаться прямой или обратной . Пусть в сети задан поток . Цепь из в называется прибавляющей, если для каждой ее прямой дуги выполняется строгое неравенство , а для каждой обратной дуги – строгое неравенство . Предположим, что для потока удалось найти прибавляющую цепь. Тогда увеличивая на максимально возможное число единиц на прямых дугах (с обеспечением условия ) и уменьшая на столько же единиц на обратных дугах (с обеспечением условия ), получим новый поток, величина которого на единиц больше, чем величина . Алгоритм состоит в последовательном просмотре вершин сети и присвоении им отметок. На каждом шаге алгоритма любая вершина находится в одном из трех состояний: а) не помечена; б) помечена, но не просмотрена; в) помечена и просмотрена. 0-й шаг. Зададим какой-нибудь, например, нулевой поток по сети. 1-й шаг. Помети источник любой отметкой, например, звездочкой *. После этого вершина помечена, но не просмотрена. Остальные вершины не помечены. 2-й шаг. Берем очередную помеченную, но не просмотренную вершину . Просматриваем все дуги, инцидентные этой вершине. Если вторая вершины дуги не помечена, то помечаем ее отметкой в следующих двух случаях: а) дуга выходит из вершины и поток по ней строго меньше пропускной способности; б) дуга входит в вершину и поток по ней строго больше нуля. После завершения этого шага вершина объявляется помеченной и просмотренной, а вершины, получившие при просмотре отметку , объявляются помеченными, но не просмотренными. Шаг 2 циклически повторяется до тех пор, пока не произойдет одно из двух событий, рассматриваемых далее на 3-ем и 4-ом шагах. 3-й шаг. Сток получил отметку, например, . Переходим из в вершину , по отметке вершины отыскиваем следующую вершину и т. д. до тех пор, пока не дойдем до вершины . В результате получаем прибавляющую цепь, с помощью которой увеличиваем текущий поток. Далее стираем отметки всех вершин и повторяем выполнение алгоритма с 1-го шага. 4-й шаг. Процесс расстановки отметок закончился тем, что все помеченные вершины просмотрены, но сток при этом не помечен. Пусть – множество помеченных вершин. Так как , а , то можно определить разрез . Для , то есть дуги, идущей из помеченной вершины в непомеченную, , иначе другой конец этой дуги был бы помечен. По той же причине для . Следовательно, для построенного потока и разреза , образованного помеченными вершинами, выполняются условия (1). В таком случае имеем максимальный поток. Пример 2. Пусть задана транспортная сеть и поток по ней (рис. 2). 5, 3 10, 7 4, 4 5, 5 3, 2 6, 4 2, 2 5, 5 6, 2 2, 2 9, 5 3, 3 Рис. 2. Процесс расстановки отметок показан в таблице 1. Таблица 1
Поскольку сток получил отметку, то строим прибавляющую цепь (рис. 3). 10, 7 5, 3 3, 2 6, 4 6, 2 9, 5 Рис. 3. Увеличиваем поток на две единицы на прямых дугах этой цепи и уменьшаем на две единицы на обратных. В результате получаем поток, изображенный на рис. 4. 5, 5 10, 9 4, 4 5, 5 3, 0 6, 2 2, 2 5, 5 6, 4 2, 2 9, 7 3, 3 Рис. 4. В процессе расстановки отметок для нового потока удается пометить только вершины и . Тогда – множество помеченных вершин, которое порождает минимальный разрез . Его пропускная способность совпадает с величиной потока или . 30. Определение сетевого графика. Алгоритм отыскания критического пути. Определение резервов времени и коэффициентов напряженности работ. Сетевой график представляет собой изображение хода проекта при помощи ациклической сети. Под сетью понимается ориентированный граф, в котором выделены две вершины: одна из них называется началом и не имеет входящих дуг, другая – концом, она не имеет выходящих дуг. Последовательность различных дуг, в которой начало каждой дуги совпадает с концом предыдущей, называется путем. Замкнутый путь называется контуром или ориентированным циклом. Если в сети нет ориентированных циклов, она называется ациклической. Дуги сетиизображают отдельные работы, а вершины – события, состоящие в завершении одной или нескольких работ. Каждой дуге в сетевом графике приписано целое неотрицательное число – продолжительность соответствующей работы. Обозначим – продолжительность работы ( , ). Рассмотрим некоторый путь на сетевом графике: . Длиной пути назовем сумму продолжительностей входящих в него работ: . Рассмотрим все пути из начальной вершины в конечную. Путь наибольшей длины называют критическим. Длина критического пути – основная характеристика сетевого графика, смысл которой состоит в том, что если каждая работа ( , ) будет начинаться в тот момент, когда произойдет событие (раньше она начинаться не может), и выполняться точно за время , то вся совокупность работ будет выполнена за время, равное длине критического пути. Опишем алгоритм для нахождения критического пути в сетевом графике. В процессе работы алгоритма для каждой вершины рассчитывается величина – максимальная длина пути из начала в вершину . 1°. Правильная нумерация сети. Нумерация вершин сети называется правильной, если номер начала любой дуги сети меньше, чем номер ее конца. 2°. Расстановка отметок. Пусть сеть правильно занумерована. Для каждой вершины вычисляем отметку по следующим правилам: – полагаем ; – просматриваем вершины в порядке их номеров и для -ой вершины вычисляем по формуле , (1) где максимум берется по всем вершинам , имеющим дугу , направленную в вершину . По окончании процесса вычисления отметок величина находится как отметка концевой вершины. 3°. Построение критического пути. Начиная с вершины-конца, последовательно находим дуги , для которых . Эти дуги и образуют критический путь. Параметр , вычисляемый при построении критического пути, называется «ранний срок свершения события ». Для каждого события можно рассчитать также поздний срок его свершения . Смысл этого параметра состоит в следующем: если событие «запоздает, однако произойдет не позднее , то длина критического пути (время выполения всего проекта) не изменится. Метод расчета аналогичен методу расчета , если его «вывернуть наизнанку». Пусть для правильной сети концевая вершина получила номер . Тогда для каждой вершины вычисляем отметку по следующим правилам: – полагаем ; – просматриваем вершины в обратном порядке их номеров и для -ой вершины вычисляем по формуле , (2) где минимум берется по всем вершинам , в которые ведут дуги из вершины . Резервом времени работы называется величина . (3) Задержка в выполнении работы на величину, не превышающую , не изменяет длину критического пути, то есть срока выполнения проекта. Резервы времени позволяют разбить всю совокупность работ на более важные и менее важные, что используется для управления выполнением проекта. Работы, лежащие на критическом пути, имеют резервы времени, равные нулю. Задержка в выполнении такой работы на время ровно на такую же величину изменяет время выполнения всего проекта. Поэтому возможны варианты форсирования этих работ за счет работ, имеющих большой резерв времени. При практическом применении сетевых графиков более удобными по сравнению с резервами времени являются коэффициенты напряженности работ, определяемые как отношение длины максимального пути из начала в конец, проходящего через данную работу, к длине критического пути: . (4) Из формулы (4) следует, что , причем для работ с нулевым резервом (лежащих на критическом пути) , а для работ с большим резервом времени – . На основании этого всю совокупность работ делят на зоны: критическую с , подкритическую с , и резервную. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||