Лекции по "Развитию операционных систем"

Лекция 12.

 

п.12.  Сети. Потоки в сетях.

 

12.1.  Сеть. Поток в сети.

 

Функциональное назначение большинства физически реализованных сетей состоит в том, что они служат носителями систем потоков, т.е. систем, в которых некоторые объекты текут, движутся или транспонируются по системе каналов (дуг сети) ограниченной пропускной способности. Вот некоторые примеры практических задач.

1.  Пусть имеется сеть  автомобильных дорог, по которым  можно проехать из пункта A в пункт B. Дороги могут пересекаться в промежуточных пунктах. Количество автомобилей, которые могут проехать по каждому отрезку дороги в единицу времени, не безгранично, оно определяется такими факторами, как ширина проезжей части, качество дорожного покрытия, действующие ограничения скорости движения и т.д. (обычно это называют «пропускной способностью» дороги). Каково максимальное количество автомобилей, которые могут проехать из пункта A в пункт B без образования пробок на дорогах (обычно это называют «автомобильным потоком»)? Или же можно поставить другой вопрос: какие дороги и насколько можно расширить или улучшить, чтобы увеличить максимальный поток на заданную величину?

2.  Пусть имеется сеть  трубопроводов, соединяющих пункт A (скажем, нефте-промысел) с пунктом B (скажем, нефтеперерабатывающим заводом). Трубопроводы могут соединяться и разветвляться в промежуточных пунктах. Количество нефти, которое может быть перекачено по каждому отрезку трубопровода в единицу времени, также не безгранично и определяется такими факторами, как диаметр трубы, мощность нагнетающего насоса и т.д. (обычно это называют «пропускной способностью» или «максимальным расходом» трубопровода). Сколько нефти можно пропускать через такую сеть в единицу времени?

 

Изучение этих многочисленных подобных им практических задач приводит к теории потоков в сетях. Данная теория разрабатывает решения общей задачи, которая называется задача об оптимальном потоке. Мы же рассмотрим частный случай этой задачи, которая является существенной, а именно задачи определения максимальной величины потока.

 

Введем основные понятия на сетях и рассмотрим алгоритм построения потока максимальной мощности.

Определение 12.1.  Сетью называется связный ориентированный граф G(V, E) без петель с выделенными вершинами - истоком и - стоком, причем каждой дуге поставлено в соответствие некоторое натуральное число – пропускная способность дуги.

Напомним, что истоком называется вершина, у которой , т.е. дуги только выходят; а стоком – вершина, у которой , т.е. дуги только входят.

Пропускная способность дуги характеризует максимальное количество вещества, которое может пропустить за единицу времени дуга . Договоримся на сети пропускную способность дуги записывать в круглых скобках.

 

Поток в сети определяет способ пересылки некоторых объектов из одной вершины графа в другую по направлению дуги. Число объектов (количество вещества) , пересылаемых вдоль дуги , не может превышать пропускной способности этой дуги: . Будем считать, что если существует дуга из в , то нет дуги из в . Таким образом, рассматривается поток вещества только в одну сторону.

 

Формулировка задачи о максимальном потоке:  на сети с заданными пропускными способностями дуг сформировать максимальный по величине поток между ее истоком и стоком. Этот поток обеспечивается назначением в каждой дуге величины передаваемого ею потока.

 

Задача о максимальном потоке в сети должна удовлетворять следующим условиям:

– сумма потоков дуг, выходящих из истока сети, должна быть равна сумме потоков дуг, входящих в сток

;

– для вершины v, не являющейся стоком или истоком, т.е. , количество единиц потока, входящего в вершину, должно быть равно количеству единиц потока, выходящего из нее (сохранение потока)

;

– максимальный поток на пути от истока к стоку определяется той дугой , которая имеет минимальную пропускную способность из всех дуг, принадлежащих этому пути.

 

Если пропускная способность дуги равна идущему через нее потоку (на сети значение обозначается числом без скобок), то такая дуга называется насыщенной, а любой путь, в который она включена, называется насыщенным путем. Поток называется насыщенным, если любой путь из в содержит дугу , для которой . Первая часть решения задачи о максимальном потоке как раз и состоит в нахождении насыщенного потока. Но насыщенный поток не всегда является максимальным.

 

Поток в сети будет максимальным, если величина этого потока больше величины любого другого потока в этой сети.

 

 

12.2.  Разрез на сети.

 

Максимальный поток определяется с помощью одного из основных понятий теории сетей – разреза.

Разрез может быть представлен как множество дуг, исключение которых из сети сделало бы орграф несвязным.

Предположим, что дана некоторая сеть. Разобьем множество вершин V этой сети на два непересекающихся подмножества и так, чтобы исток попал в подмножество , а сток – в подмножество , т.е. . В этом случае говорят, что на сети произведен разрез, отделяющий исток от стока .

Пусть - разрез на сети, представляющий совокупность дуг, которые связывают подмножества вершин A и B. В разрез входят дуги, обозначим их , начальные вершины которых принадлежат подмножеству A, а конечные – подмножеству B, т.е. . А также в разрез входят дуги, обозначим их , начальные вершины которых принадлежат подмножеству B, а конечные – подмножеству A, т.е. .

 

Пропускной способностью или величиной разреза называется величина , которая определяется следующей формулой:

.           (12.2.1)

Потоком через разрез называется величина , которая определяется следующей формулой:

.        (12.2.2.)

 

Пример 12.1.  Рассмотрим сеть с заданными пропускными способностями дуг, которые записаны в круглых скобках.

 

Построим на сети некоторый поток, величину которого по каждой дуге будем записывать без скобок:

путь :  , значит, по этому пути пропускаем поток в 2 единицы;

путь :  , значит, по этому пути пропускаем поток в 3 единицы;

путь :  , значит, по этому пути пропускаем поток в 1 единицу;

Проведем на этой сети, например, разрез , при котором вершины разбиты на подмножества и . Тогда сам разрез состоит из дуг , , , , т.е.

.

Так, например, пропускная способность разреза на рисунке равна

(ед.),

а поток через этот разрез составляет:

(ед.).

,

 

 

12.3.  Алгоритм нахождения максимального потока на сети.

 

Если на сети сформирован некоторый поток, то для ответа на вопрос: будет ли он максимальным, используют теорему Форда-Фалкерсона.

 

Теорема 12.1.  (Теорема Форда-Фалкерсона)

Максимальный поток в сети равен минимальной пропускной способности разреза:

.

 

Доказательство теоремы – это алгоритм определения максимального потока по сети.

 

Алгоритм нахождения максимального потока на сети.

 

Этап 1.  Насыщение потока.

Шаг 1.  Сформировать произвольный начальный поток.

Шаг 2.  Найти оставшиеся возможные пути из истока в сток , имеющие только ненасыщенные дуги. Если такой путь найден, то переходим к шагу 3. Если путь не найден, то переходим к шагу 4.

Шаг 3.  Увеличить поток по найденному пути таким образом, чтобы одна из дуг стала насыщенной.

Шаг 4.  Получившийся поток насыщен.

 

Этап 2.  Пометка вершин сети. (Перераспределение потока.)

Шаг 5.  Вершину пометить .

Шаг 6.  Пусть – любая из уже помеченных вершин; – произвольная непомеченная вершина, смежная с вершиной . Вершину помечаем , если данные вершины соединены ненасыщенной дугой , и помечаем , если соединены непустой дугой .

После пометки вершин возможны два случая: вершина оказалась либо помеченной, либо непомеченной.

Шаг 7.  Вершина оказалась помеченной. Значит, существует последова-тельность помеченных вершин от к . В этой последовательности каждая последующая вершина помечена буквой предыдущей вершины. На дугах последовательности определяем новый поток. Увеличиваем на единиц поток на дугах, имеющих направление от к и уменьшаем на единиц поток на дугах, имеющих обратное направление. Число равно наименьшей разнице между пропускной способностью и потоком дуг, входящих в последовательность. Заметим, что поток можно увеличивать (уменьшать) на прямых (обратных) дугах настолько, пока одна из дуг не станет насыщенной (пустой). Далее вновь переходим к пометке вершин (шаг 5). Перераспределение потока сохраняет все его свойства и увеличивает поток на единиц в вершину .

 

Этап 3.  Определение максимального потока.

Шаг 8.  Вершина осталась непомеченной. Пусть – множество всех помеченных вершин, – множество всех непомеченных вершин. Тогда дуги, связывающие два подмножества вершин и , определяют разрез . Таким образом, найден поток и разрез , для которого выполняется условие .

 

Пример 12.2.  На сети из примера 12.1. сформировать максимальный по величине поток, направленный из истока в сток . Выписать ребра, образующие на сети разрез минимальной пропускной способности.

Решение. Этап 1.

Шаг 1. Воспользуемся тем, что в примере 12.1. был уже сформирован некоторый поток на сети.

Шаг 2.  Путь содержит насыщенную дугу . Больше нельзя добавить потока по этому пути. Пути , и содержат насыщенные дуги.

Но путь имеет две дуги, которые еще ненасыщенные.

Шаг 3.  Увеличиваем поток по найденному пути: . Значит, на этом пути поток увеличиваем на 1 единицу, и тем самым дуга стала насыщенной.

Шаг 4.  Таким образом, получаем насыщенный поток, поскольку каждый рассмотренный путь содержит хотя бы одну насыщенную дугу.

Этап 2.

Выясним, является ли построенный поток максимальным по величине. Строим сеть, на которой отметим все вершины и ненасыщенные дуги. На этой сети разность пропускных способностей дуги и проходящего по ней потока обозначим числом в квадратных скобках.

 

Шаг 5, 6.  Вершину пометить . На шаге 6 предусматривается пометка вершин, смежных с вершиной I, соединенных ненасыщенными дугами. Но на построенной сети таких вершин нет.

В результате вершина S оказалась непомеченной.

Этап 3.  Шаг 8.  Так как вершина S непомеченная, то поток, сформированный на сети, получился максимальным.

Строим разрез на сети. Разбиваем множество вершин на два подмножества: A и B. Так как только одна вершина оказалась помеченной, то множество A состоит из одной вершины I, а остальные образуют множество B:

.

Проводим разрез , который состоит из дуг и :

.

Определяем величину максимального потока :

(ед.)                                              ,

 

Пример 12.3.  На заданной сети в скобках указаны пропускные способности дуг. Требуется сформировать на сети максимальный поток, направленный из истока в сток , и выписать ребра, образующие на сети разрез минимальной пропускной способности.

 

Решение.  Этап 1.

Сформируем на сети какой-либо начальный поток. Рассмотрим путь . Поскольку , по этому пути пропускаем поток в 2 единицы. На сети значение потока обозначим числами без скобок. По пути пропускаем поток в 4 единицы, так как . По пути пропускаем поток в 3 единицы, так как . Таким образом, начальный поток имеет вид:

,

,

.

Начальный поток изображен на рисунке.

 

 

Каждый из рассмотренных путей содержит насыщенную дугу, поэтому эти пути насыщенные. На сети есть еще пути, которые содержат ненасыщенные дуги, а именно: , и . Для первого пути дополнительно увеличим поток на 2 единицы, так как . Второй и третий пути содержат одну и ту же дугу с минимальной для них оставшейся разностью . Поэтому для увеличения потока на 1 единицу выберем, например, путь .

Теперь каждый из этих путей содержит насыщенную дугу, следовательно, полученный поток – насыщенный.

 

 

 

 

 

 

 

 

 

 

 

 

 

Выясним, является ли построенный поток максимальным. Изобразим сеть, на которой отметим все вершины и ненасыщенные дуги. На этой сети разность пропускной способности дуги и проходящего по ней потока обозначим числом в квадратных скобках. Пропускную способность дуги, по которой поток не проходит, оставим в круглых скобках.