ГЕНЕРАТОР ЗАДАНИЙ ДЛЯ ИЗУЧЕНИЯ ПОТОКОВЫХ АЛГОРИТМОВ

Рязанов Ю.Д., доцент

Трунов Ю.А.

г. Белгород, ФГБОУ ВПО БГТУ им. В.Г. Шухова

В качестве математической модели систем, между элементами которой могут перемещаться или перетекать некоторые объекты, можно использовать сеть — ориентированный взвешенный граф [1, 2]. В графе взвешены дуги. Вес дуги представляет собой пропускную способность. Примером такой системы может служить сеть автодорог, соединяющих населенные пункты, по которым движутся автомобили. Максимальное количество автомобилей, которые могут проехать по участку дороги за единицу времени, определяет пропускную способность этого участка (зависит от ширины проезжей части, качества дорожного покрытия, действующих ограничений скорости движения и т. д.). Другим примером может служить сеть трубопроводов, соединяющих нефтепромыслы с нефтеперерабатывающими заводами. Трубопроводы могут соединяться и разветвляться в промежуточных пунктах. Пропускная способность отрезка трубопровода определяется максимальным количеством нефти, которое может быть перекачено по этому отрезку за единицу времени (зависит от диаметра трубы, мощности нагнетающего насоса и т. д.).

В сети выделяют вершину s, называемую источником, ей соответствует элемент системы, из которого начинается перемещение объектов, и вершину t, называемую стоком, ей соответствует элемент системы, в котором заканчивается перемещение объектов. Объекты, которые перемещаются или перетекают из источника в сток, называются единицами потока. Функция f(x, y), значение которой определяет количество единиц потока, проходящей по дуге (x, y), называется потоком, если выполняются следующие условия:

1) количество единиц потока, проходящих по каждой дуге (x, y), не может быть меньше нуля и ограничивается пропускной способностью этой дуги;

2) для каждой промежуточной вершины (отличной от источника и стока) число приходящих единиц потока в эту вершину должно быть равно числу единиц потока, выходящих из нее;

3) количество единиц потока, выходящих из источника должно равняться количеству единиц, приходящих в сток: сколько единиц потока вышло из источника, столько же единиц потока должно прийти в сток.

Суммарное число единиц потока, выходящих из источника или входящих в сток, называется величиной потока.

Дугу, в которой поток равен пропускной способности, назовем насыщенной, а дугу, в которой поток равен нулю — пустой.

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

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

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

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

Алгоритмы, связанные с анализом сети, изменением потока и поиском потоков, обладающих определенными свойствами, называют потоковыми [1]. Основными потоковыми алгоритмами являются:

а) поиск увеличивающей цепи;

б) поиск максимального потока;

в) поиск минимального разреза;

г) поиск потока минимальной стоимости.

Одним из эффективных способов изучения и осознания потоковых алгоритмов является их «ручное» пошаговое выполнение на конкретных примерах с графическим отображением результатов всех шагов. Особенностью потоковых алгоритмов является следующее:

1) для сетей небольшого размера не все ветви алгоритма могут быть выполнены, а, следовательно, недостаточно хорошо изучены;

2) для сетей большего размера алгоритм может быть выполнен за большое число шагов, что делает изучение алгоритма утомительным, неэффективным, а иногда и невозможным, но и при этом не все ветви алгоритма могут быть выполнены;

3) результат выполнения алгоритма может быть «односторонним», например, увеличивающая цепь может содержать только прямые дуги, минимальный разрез может быть около источника или около стока, произвольный максимальный поток может совпадать с максимальным потоком минимальной стоимости.

Из этого следует, что изучать потоковые алгоритмы путем их «ручного» выполнения с графическим отображением результатов всех шагов можно только на особых, «показательных» примерах. Придумать такие примеры практически невозможно, а оценка произвольного примера требует слишком много времени и сил. Поэтому, для получения большого количества разнообразных «показательных» примеров разработано специальное программное обеспечение — генератор заданий для изучения потоковых алгоритмов.

Программное обеспечение включает в себя генератор случайный слабосвязных сетей, процедуры реализации потоковых алгоритмов, включающие анализ хода выполнения алгоритма, и процедуру анализа результата. Это позволяет автоматически генерировать большое количество разнообразных сетей и отбирать «показательные» примеры. Полученные таким образом примеры используются в учебном процессе при изучении потоковых алгоритмов в дисциплинах «Дискретная математика», «Теория графов и ее приложения», «Исследование операций и теория игр».

Литература

1. Майника.Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981.

2. Форд Л. Р., Фалкерсон Д. Р. Потоки в сетях. - М.: Мир, 1966.