Исследование стационарных и динамических потоков в сетях без ограничений и с ограничениями на достижимость тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

ВОДОЛАЗОВ Николай Николаевич

ИССЛЕДОВАНИЕ СТАЦИОНАРНЫХ И ДИНАМИЧЕСКИХ ПОТОКОВ В СЕТЯХ БЕЗ ОГРАНИЧЕНИЙ И С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ

Специальность 01.01.09 - дискретная математика

и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

0 3 033 2077

Ярославль 2011

4853773

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

Научный руководитель: кандидат физико-математических наук,

профессор Ерусалимский Яков Михайлович

Официальные оппоненты: доктор физико-математических наук,

профессор Соколов Валерий Анатольевич;

кандидат физико-математических наук, доцент Басангова Елена Одляевна

Ведущая организация: Воронежский государственный университет

Защита диссертации состоится 25 февраля 2011 года в 14 ч. 00 мйн. на заседании диссертационного совета Д.212.002.03 при Ярославском государственном университете им. П.Г. Демидова по адресу: 150008, г. Ярославль, ул. Союзная, 144, аудитория 426.

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им. П.Г. Демидова

Автореферат разослан 20 января 2011 г.

Ученый секретарь диссертационного совета ^Яблокова С.И

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Известно, что графовые модели (т.е. математические модели, имеющие в своей основе графы и процессы на графах) предоставляют необходимую основу для решения задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управления производством, сетевого и календарного планирования, информационных сетей и многих других. Классическими достижениями этой области математического моделирования являются законы Кирхгофа для электрических цепей, открытие А.Келли природы химических изомеров и созданная Л.Р. Фордом и Д.Р. Фал-керсоном теория потоков в сетях.

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

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

Обычно поток не перемещается по сети мгновенно, а требуется определенное время для прохождения по каждой дуге. В часг-

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

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

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

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

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

1 Ерусалимский Я.М. Графы с нестандартной достижимостью. Задачи, приложения: моногр. / Я.М. Ерусалимский, В.А. Скороходов, М.В. Кузьминова, А.Г. Петросян. -Ростов-на-Дону: Южный федеральный университет, 2009. -195 с.

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

Степень разработанности проблемы. Исследованиями в области графовых моделей и разработки алгоритмов решения задач на таких моделях занимались многие ученые как в нашей стране, так и за рубежом. Выдающимся достижением в этой области следует назвать теорию потоков в сетях, созданную Л.Р. Фордом и Д.Р. Фалкер-соном. Дальнейшее развитие эта теория получила в работах Е.А. Ди-ница, Дж. Р. Эдмондса и P.M. Карпа, A.B. Карзанова, A.B. Голдберга и многих других. Впервые задачи о нестандартной достижимости рассмотрены в работах Я.М. Ерусалимского и Е.О. Басанговой, позже, в работах А.Г. Петросяна, В.А. Скороходова и других исследовались стацинарные потоковые задачи на таких сетях, работы М.В. Кузьминовой посвящены решению задач о динамическом потоке на сетях с нестандартной достижимостью.

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

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

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

Научная новизна диссертационного исследования заключается в доказательстве Г^1Р-полноты задачи поиска максимального потока на графах с некоторыми видами нестандартной достижимости, построении полиномиальных алгоритмов для задачи поиска максимального потока для других видов нестандартной достижимости, в постановке задач о максимальном всплеске и о максимальном объёме сети и в построении алгоритмов для их нахождения.

Научная и практическая значимость. Работа носит теоретический характер. Полученные в диссертации результаты могут найти применение в задачах логистики и маршрутизации в коммуникационных сетях.

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

Основные положения диссертационного исследования, выносимые на защиту:

1. Доказана МР-полнота задачи нахождения максимального потока для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к >2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимость.

2. Построены полиномиальные алгоритмы нахождения максимального потока для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к- 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями.

3. Исследована задача нахождения максимального всплеска в сети и приведен алгоритм ее решения.

4. Исследована задача нахождения максимального объема сети и приведен алгоритм ее решения.

Апробация работы. Основные результаты работы докладывались соискателем на Воронежской весенней математической школе «Понтрягинские чтения» в 2008, 2009 и 2010 годах, на семинарах кафедр алгебры и дискретной математики ЮФУ и математического моделирования ЮФУ. Работа поддержана ФЦП «Научные и научно-педагогические кадры инновационной России», Государственный контракт № 02.740.11.0208 от 7 июля 2009 г.

Публикации. Содержание диссертационного исследования и его результаты изложены в публикациях автора. По теме диссертации опубликовано 7 научных работ. В работах [2] - [7] научному руководителю (Я.М. Ерусалимскому) принадлежит постановка задач. Доказательства приведенных в работах положений, алгоритмы и их обоснование выполнены автором диссертационного исследования. Общий объем работ, опубликованных по теме диссертации, -5,7 п.л. Список публикаций приведен в конце автореферата.

Структура диссертационной работы. Диссертация состоит из введения, трех глав, заключения и библиографического списка. Полный объем диссертации составляет 142 страницы, включая 72 рисунка и 3 таблицы,

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе «Обзор литературы. Основные понятия и определения» дан KpáTKnft обзор работ известных отечественных и зарубежных ученых, посвященных изучению потока в сети.

В разделе 1.1 «Задача поиска максимального потока на графе» исследованы работы, в которых изучается максимальный стационарный поток. Кратко описана история развития алгоритмов решения задачи, представлен список наиболее известных алгоритмов. Даны основные определения и теоремы, применяемые при исследовании стационарных потоков.

В разделе 1.2 «Обзор задач о динамическом потоке» анализируются исследования динамического потока на графах и показаны области его применения. Приведены основные определения и теоремы, используемые в дальнейшем.

В разделе 1.3 «Основные подходы к решению задач на графах с нестандартной достижимостью» описываются подходы к решению основных задач на графах с нестандартной достижимостью. Приведены несколько видов ограничений на достижимость, рассматриваемых в работе: графы с накоплением неубывающей магнитно-сти; графы с условием вентильной достижимости; достижимость на графах с условием барьерного перехода; ограниченная магнитная достижимость; ограниченная монотонная достижимость. Для этих видов достижимости приведены определения, правила построения вспомогательного графа, теоремы об эквивалентности путей на исходном и вспомогательных графах. Кратко описаны предыдущие результаты исследования потока в сетях с дополнительными ограничениями, в том числе приведен алгоритм прорыва, используемый ранее для поиска максимального потока в сетях с дополнительными ограничениями на достижимость.

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

этому поток определяется как множество пар. Каждая пара - путь из источника в сток и величина потока по этому пути.

Пусть (1 - некоторый путь на графе С, и - некоторая дуга

графа б. Обозначим количество раз, которое путь ц, про-

ходит по дуге и.

Определение 19. Стационарным потоком на графе

С(У,и,(р) называется множество пар Кц,,/?,)}■!,/ удовлетворяющее условиям:

N 1=1

где ц, - допустимый путь на графе С из источника 5 в сток /;

N

р1 - величина потока по пути ^Г/?, 50.1,, г/) - поток по дуге и.

N

Будем называть ^ р1 - величиной потока. 1=1

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

Сходным образом (но для решения другой задачи) поток определяется в динамических сетях. Как следует из теоремы о декомпозиции' потока, новое определение эквивалентно классическому для графов без дополнительных ограничений. Так же, как и в классическом случае, для графов с конкретными видами ограничений можно построить определение потока в виде системы уравнений и неравенств. Такое определение дано в разделе 2.2 «Поток в сети с барьерными ограничениями на достижимость».

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

ние (алгоритм прорыва). На примере показывается, что на некоторых графах (даже без барьерных ограничений) алгоритм прорыва может не находить максимального потока. В данной работе автор строит алгоритм на основе алгоритма Эдмондса-Карпа, обходящий существовавшие ранее ограничения (алгоритм 2). Однако построенный далее пример показывает, что и этот алгоритм не всегда может найти максимальный поток (пример 3).

В разделе 2.3 «Обобщение алгоритма поиска максимального потока на графы со связанными дугами» анализируются причины, по которым алгоритмы, основанные на поиске увеличивающих цепей (такие как алгоритмы Форда-Фалкерсона и Эдмондса-Карпа), могут не находить решения. Рассматривается поток на вспомогательном графе, построенном по исходному графу, в котором все пути разрешены. При построении вспомогательного графа могут1 появляться связанные дуги - дуги, суммарный поток по котором ограничен. Поэтому потребовалось изменить определение величины разреза на таком графе.

Пусть дан граф С(Г,(/,ф), V - множество вершин, I/ - множество дуг, ф: и V х V, причем множество дуг разбито на к попарно непересекающихся подмножеств: В = {1У, },!,;

ы

Назовем (/,- е В подмножеством связанных дуг. Пусть задано

отображение с:5->Л+ - пропускная способность множества связанных дуг.

Определение 22. Назовем величиной разреза (5, Т) графа со связанными дугами следующую величину;

(.V, 7')п£/,*0

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

Утверждение теоремы Форда-Фалкерсона о том, что величина максимального потока ограничена сверху пропускной способностью минимального разреза справедливо и для нового определения разреза. Однако на приведенных примерах (примеры 4, 5, 6) показано, что второе утверждение теоремы Форда-Фалкерсона о том, что существует поток, величина которого достигает величины минимального разреза, не выполнено. На основании этого делается вывод о неприменимости алгоритмов поиска максимального потока, основанных на поиске увеличивающих путей.

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

В разделе 2.4 «ЫР-полнота задачи нахождения максимального целочисленного потока с ограничениями на достижимость» показано, что задача поиска потока на графах с дополнительными ограничениями на достижимость может быть МР-полна для некоторых видов достижимости. Для доказательства этого утверждения построен специальный вид достижимости - ЫР-достижимость.

Пусть множество дуг исходного графа разбито на 5 подмножеств: 1} - Е{ и Е2 и Еъ и Е4 и Е5.

Определение 23. Путь д будем называть ИР-путем, если выполнено условие:

[V» = 1,...,| ц |-1

((Звд еИ:т<п, ц(ш) е Ех) л ((0+ ((рг ° ф ° ц)(")) слЕг)ф 0))] => =>[ц(я + 1)е£2].

Иными словами, если путь до л-го шага проходил по дугам из множества Е{ и среди выходящих дуг из концевой вершины п-й дуги есть хотя бы одна дуга из множества Ег, то (п +1) -я дуга обязана быть из множества Ег.

Для доказательства теоремы об №Р-полноте задачи нахождения максимального потока в сети с ИР-достижимостью нужно различать только подмножества дуг £,, Е2 и Еъ и Е4 и Е5, т.е. различать дуги подмножеств Еъ, ЕА и Е$ не требуется. Разделение на Еъ, £4 и Е5 введено в определение достижимости для удобства

доказательства следствий из- ИР-полноты задачи для МР-достижимости, а именно, ЫР-полноты задачи для конкретных видов ограничений (магнитной, барьерной, вентильной и монотонной).

Решение задачи З-БАТ сведено к нахождению максимального потока в специально построенном графе с ЫР-достижимосгью. Доказана следующая теорема:

Теорема 9. Задача нахождения максимального целочисленного потока в сет с ИР-достижимостью ЫР-полна.

Показано, что решение задачи о максимальном потоке на графе, построенном в теореме об МР-полноте с ИР-достижимостью, эквивалентно задачам на том же графе для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к >2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимость. Доказаны следующие следствия из теоремы 9.

Следствие 1. Задача нахождения потока максимальной величины в сети с барьерными ограничениями на достижимость (при к -1) ЫР-полна.

Следствие 2. Задача нахождения потока максимальной величины в сети с барьерными ограничениями на достижимость (при к>\) ЫР-полна.

Следствие 3. Задача нахождения потока максимальной величины в сети с вентильными достижимостями (при к-2) NP-пoлнa.

Следствие 4. Задача нахождения потока максимальной величины в сети с вентильными достижимостями (при к > 2 ) ИР-полна.

Следствие 5. Задача нахождения потока максимальной величины в сети с магнитными достижимостями (при к -1) ИР-полна.

Следствие 6. Задача нахождения потока максимальной величины в сети с магнитными достижимостями (при к > 1) ИР-полна.

Следствие 7. Задача нахождения потока максимальной величины в сети с монотонными достижимостями (при г = 2) ИР-полна.

Следствие 8. Задача нахождения потока максимальной величины в сети с монотонными достижимостями (при г >2) ИР-полна.

Для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к = 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями построены полиномиальные алгоритмы нахождения максимального потока. Доказаны следующие теоремы:

Теорема 10. Задача поиска потока максимальной величины в сети с вентильными-достижимостями при к = 1 может быть решена за полиномиальное время.

Теорема 11. Задача поиска потока максимальной величины для графов с ограниченными магнитными достижимостями может быть решена за полиномиальное время.

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

Таблица

^-полнота задачи нахождения максимального потока на графах с дополнительными ограничениями на достижимость

Вид ограничений на достижимость Параметр задачи Сложность задачи

Барьерная достижимость V/c е N Задача 1\1Р-полна (следствия 1 и 2)

Вентильная достижимость ksN, k> 2 Задача ЫР-полна (следствия 3 и 4)

k = 1 Приведен полиномиальный алгоритм (теорема 10)

Магнитная достижимость V/c e N Задача МР-полна (следствия 5 и 6)

Монотонная достижимость re N,r>2 Задача МР-полна (следствия 7 и 8)

r = 1 При Г = 1 совпадает с задачей без ограничений.

Ограниченная магнитная достижимость Нет Приведен полиномиальный алгоритм (теорема 11)

В третьей главе «Динамические потоки в сетях» рассматриваются динамический поток на графе и ограничения на величину максимального динамического потока. Вводится понятие средней величины потока.

Определение 27. Пусть дан интервал времени ]Тх\Т1\г,

Vif Т)

Т = Т2-ТХ+1>0. Назовем - ^ - средней величиной

динамического потока на промежутке [Т{,Т2\7 ,

В диссертации доказана следующая теорема. Теорема 12. Средняя величина динамического потока f в сети G за время Т не может превосходить величины максимального стационарного потока.

Приведен пример (пример 8), который показывает, что величина динамического потока может в некоторые моменты времени превосходить величину максимального стационарного потока.

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

Определение 29. Назовем максимальным всплеском в сети С величину № = тах (0 / где Е - множество всех

динамических потоков на графе С .

Максимальный всплеск - максимальная величина потока, которая может достигаться в стоке в какой-то момент времени, не заданный заранее.

Определение 30. Назовем объемом потока / на графе

С(У,Е, ф, с) в момент времени / величину /1/(/) = ^Г/(с,/).

сеЕ

Таким образом, объем потока в момент времени / - это сумма величин потока на всех дугах сети в данный момент времени (объем «вещества», находящегося в сети в этот момент времени).

Далее решаются две задачи.

1. Нахождение максимального всплеска на графе.

2. Нахождение динамического потока, имеющего максимальный объем.

Построены алгоритмы решения задач: для первой задачи -алгоритм, названный нами алгоритмом Эдмондса-Карпа с обратным поиском; для второй - алгоритм 4.

Доказаны следующие теоремы.

Теорема 13. Алгоритм Эдмондса-Карпа с обратным поиском находит максимальный всплеск на графе С.

Теорема 14. Алгоритм 4 находит поток, имеющий максимальный объем.

Для алгоритмов, разработанных в диссертационной работе, автором на языке С# написана реализующая их программа "Моделирование потоков с ограничениями на достижимость" (прилагается к диссертации на компакт-диске). Программа позволяет визуализировать представленные алгоритмы и выполнять их по шагам. В процессе работы алгоритмов можно наблюдать за конвертацией графа, изменением меток вершин и дуг графа и основными переменными алгоритма.

В программе реализованы предложенные автором алгоритмы поиска максимального потока на графах с барьерными ограничениями (алгоритм 2 в диссертационной работе), поиск максимального потока на графах со связанными дугами (алгоритм 3), алгоритм поиска максимального всплеска и алгоритм поиска максимального объема сети. Программа позволяет перестраивать графы с вентильными достижимостями (при количестве вентильных уровней к = 1) по правилам, предложенным автором в теореме 10, и перестраивать графы с ограниченными магнитными достижимостями по правилам, предложенным автором в теореме 11. Как показано в соответствующих теоремах, подобное перестроение позволяет решать задачу о потоке на графах с вентильными (при к -1) и ограниченными магнитными достижимостями за полиномиальное время.

Помимо алгоритмов, предложенных автором, программа реализует алгоритм Эдмондса-Карпа и позволяет перестраивать графы с магнитными, вентильными, барьерными, ограниченными магнитными и монотонными достижимостями по правилам, предложенным ранее.

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

Публикации автора по теме диссертации

Статьи в ведущих рецензируемых научных журналах и изданиях, включенных в перечень ВАК:

1. Водолазов H.H. Об особенностях потока в сетях с барьерной достижимостью. / H.H. Водолазов // Вестник ДГТУ. -2008 -Т.8. -№2 (37). -С. 127-136.

2. Ерусалимский Я.М., Водолазов H.H. Нестационарный поток в сети. / Я.М. Ерусалимский, H.H. Водолазов // Вестник ДГТУ. -2009. -Т. 9. -№3(42). - С.402-409.

3. Водолазов H.H., Ерусалимский Я.М. Максимальный всплеск в сети и максимальный объем сети // Известия Высших учебных заведений. Северо-Кавказский регион. - 2010. - № б. - С. 9-13.

Другие публикации:

4. Водолазов H.H. Об особенностях потока в сетях с барьерной достижимостью. / H.H. Водолазов. // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения-XIX». - Воронеж: ВГУ, 2008. - С.64-66.

5. Ерусалимский Я.М., Водолазов H.H. Нестационарный и случайный поток в сети. / Я.М. Ерусалимский, H.H. Водолазов. // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения-ХХ». -Воронеж: ВГУ, 2009. - С.56-57.

6. Ерусалимский Я.М., Водолазов H.H. NP-полнота задачи нахождения максимального потока в графах с дополнительными ограничениями на достижимость. / Я.М. Ерусалимский, H.H. Водолазов. // Современные методы теории краевых задач: материалы Воронежской весенней' математической школы «Понтрягинские чтения-XXI» (доп. выпуск). - Воронеж: ВГУ, 2010. - С. 14-15.

7. Водолазов H.H., Ерусалимский Я.М. Поток на графах с ограничениями на достижимость. // Труды научной школы И. Б. Симо-ненко. - Ростов-на-Дону: Изд-во ЮФУ, 2010. - С. 44-57.

ВОДОЛАЗОВ Николай Николаевич

ИССЛЕДОВАНИЕ СТАЦИОНАРНЫХ И ДИНАМИЧЕСКИХ ПОТОКОВ В СЕТЯХ БЕЗ ОГРАНИЧЕНИЙ И С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

В печать 18.01.2011.

Объём 1,13 усл. п.л. Офсет. Формат 60x84/16.

Бумага тип №3. Заказ №23. Тираж 130 экз. Цена свободная

Издательский центр ДГТУ

Адрес университета и полиграфического предприятия: 344000, г. Ростов-на-Дону, пл. Гагарина,!.

ВВЕДЕНИЕ.

Глава 1. ОБЗОР ЛИТЕРАТУРЫ. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ.

1.1. Задача поиска максимального потока на графе.

1.2. Обзор задач о динамическом потоке.

1.3. Основные подходы к решению задач на графах с нестандартной достижимостью.

Глава 2. ПОТОК НА ГРАФАХ С НЕСТАНДАРТНОЙ

ДОСТИЖИМОСТЬЮ.

2.1. Определение потока в сети с ограничениями на достижимость.

2.2. Поток в сети с барьерными ограничениями на достижимость.

2.3. Обобщение алгоритма поиска максимального потока на графах со связанными дугами.

2.4. ЫР-полнота задачи нахождения максимального целочисленного потока с ограничениями на достижимость.

Глава 3. ДИНАМИЧЕСКИЕ ПОТОКИ В СЕТЯХ.

3.1. Основные определения.

3.2. Ограничение на величину динамического потока.

3.3. Нахождение максимального всплеска на графе.

3.4. Нахождение потока, имеющего максимальный объем.

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

Известно, что теория графов предоставляет необходимую основу для решения задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управления производством, сетевого и календарного планирования, информационных сетей и многих других.

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

Задача поиска потока максимальной величины и двойственная ей задача поиска минимального разреза - это классические комбинаторные задачи с многочисленными научными и практическими приложениями. Например, определение максимальной интенсивности транспортного потока между двумя пунктами и определение части сети дорог, которая насыщена и образует «узкое место».

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

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

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

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

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

Степень разработанности проблемы. Исследованиями в области теории графов занимались многие ученые как в нашей стране, так и за рубежом. Выдающимся достижением алгоритмической теории графов следует назвать теорию потоков в сетях, созданную JI.P. Фордом и Д.Р. Фалкерсоном [42, 53]. Дальнейшее развитие эта теория получила в работах Е.А. Диница [11, 50], Дж. Р. Эдмондса и P.M. Карпа [51], A.B. Карзанова [65], A.B. Голдберга [59, 61] и многих других. Задачи о нестандартной достижимости рассмотрены в работах

Я.М. Ерусалимского [14, 15, 19, 26, 31], Е.О. Басанговой [3-5], А.Г. Петросяна [18, 25, 34-36], В.А. Скороходова [13, 17, 22, 24, 39-41] и других.

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

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

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

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

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

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

Основные положения диссертационного исследования, выносимые на защиту:

1. Доказана ЫР-полнота задачи нахождения максимального потока для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к >2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимо сть.

2. Построены полиномиальные алгоритмы нахождения максимального потока для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к = 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями.

3. Исследована задача нахождения максимального всплеска в сети и приведен алгоритм ее решения.

4. Исследована задача нахождения максимального объема сети и приведен алгоритм ее решения.

Представление материалов диссертационной работы на конференциях. Основные результаты работы докладывались соискателем на Воронежской весенней математической школе «Понтрягинские чтения» в 2008, 2009 и 2010 годах.

Публикации. Содержание диссертационного исследования и его результаты изложены в публикациях автора. По теме диссертации опубликовано 7 научных работ ([7-10, 12, 20, 21]), 2 работы написаны без соавторов.

Структура диссертационной работы. Диссертация состоит из введения, трех глав, заключения и библиографического списка. Полный объем диссертации составляет 142 страницы, включая 72 рисунка и 3 таблицы.

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

Рассмотрены два варианта задачи о максимальном объеме в сети: вариант при котром поток, имеющий максимальный объем в сети в момент времени t, не продолжаем на все ^ е Z, и вариант, когда полученный поток должен быть продолжаем на все X е Z. Предложены алгоритмы для решения этой задачи. Доказано, что эти алгоритмы находят поток, имеющий максимальный объем.

ЗАКЛЮЧЕНИЕ

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

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

Для достижения поставленной цели были решены следующие задачи:

1. Доказана МР-полнота задачи нахождения максимального потока для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к > 2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимость.

2. Построены полиномиальные алгоритмы нахождения максимального потока для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к — 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями.

3. Исследована задача нахождения максимального всплеска в сети и приведен алгоритм ее решения.

4. Исследована задача нахождения максимального объема сети и приведен алгоритм ее решения.

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

В диссертационной работе подробно рассмотрен поток в сетях с барьерными ограничениями на достижимость, и проанализирован существовавший ранее алгоритм. Показано, что на некоторых графах (даже без барьерных ограничений) алгоритм «прорыва» [14] может не находить максимального потока. Автором работы построен алгоритм на основе алгоритма Эдмондса-Карпа, который обходит ограничения существовавшего ранее решения (алгоритм 2). Однако построенный пример показывает, что и этот алгоритм не всегда может найти максимальный поток.

Проанализированы причины, по которым алгоритмы, основанные на поиске увеличивающих цепей (такие как алгоритмы Форда-Фалкерсона и Эдмондса-Карпа), могут не находить решения. Рассмотрено обобщение задачи — поток на вспомогательном графе, построенном по исходному графу, в котором все пути разрешены, но некоторые дуги являются связанными. Потребовалось изменить определение величины разреза на таком графе.

Согласно работе [14] часть теоремы Форда-Фалкерсона о том, что максимальный поток ограничен сверху величиной минимального разреза, выполнена и для нового определения разреза. Однако на приведенных в данной работе примерах показано, что другая часть - о том, что существует поток, величина которого достигает величины минимального разреза, не выполнена. На основании этого делается вывод о неприменимости алгоритмов поиска максимального потока, основанных на поиске увеличивающих путей, в сетях с дополнительными ограничениями на достижимость.

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

Автором показано, что задача поиска потока на графах с дополнительными ограничениями на достижимость может быть ЫР-полна для некоторых видов достижимости. Для доказательства этого утверждения построен специальный вид достижимости — ЫР-достижимость.

Решение задачи 3-8АТ сведено к нахождению максимального потока в специально построенном графе с МР-достижимостью. Доказано, что решение задачи о максимальном потоке на графе, построенном в теореме об ИР-полноте, с ИР-достижимостью, эквивалентно задачам на том же графе для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к > 2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимость.

Для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к = 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями построены полиномиальные алгоритмы нахождения максимального потока.

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

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

• Нахождение максимального всплеска на графе — динамического потока, имеющего максимально возможную величину в какой-то момент времени, не заданный заранее.

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

Построены алгоритмы решения указанных задач: для первой задачи — алгоритм Эдмондса-Карпа с обратным поиском; для второй — алгоритм 4, доказаны теоремы о том, что эти алгоритмы находят правильное решение.

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

Цели и задачи, поставленные в диссертационном исследовании, были полностью решены: доказана ТМР-полнота задачи поиска макимального потока для некоторых видов ограничений на достижимость, для других видов достижимости построены полиномиальные алгоритмы поиска потока, построены и обоснованы алгоритмы поиска максимального всплеска и максимального объема сети, разработана программа, реализующая построенные алгоритмы.

1. Ахо А. Построение и анализ вычислительных алгоритмов. / А. Ахо, Дж. Хопкрофт, Дж. Ульман. -М.: Мир, 1979. 536с.

2. Басакер Р. Конечные графы и сети. / Р. Басакер, Т. Саати; пер. с англ. -М.:Наука, 1973.-368с.

3. Басангова Е.О. Алгоритм нахождения максимального потока в частично-ориентированной сети. / Е.О. Басангова, Я.М. Ерусалимский // Дискретные структуры и их приложения. -Элиста: КГУ, 1988. С.23-28.

4. Басангова Е.О. Различные виды смешанной достижимости. / Е.О. Басангова, Я.М. Ерусалимский // Алгебра и дискретная математика: сб. — Элиста: КГУ, 1985. С.70-75.

5. Басангова Е.О. Смешанная достижимость на частично-ориентированных графах. / Е.О. Басангова, Я.М. Ерусалимский // Вычислительные системы и алгоритмы: сб. -Ростов-на-Дону: РГУ, 1983. С.135-140.

6. Басангова Е. О. Смешанная достижимость на частично-ориентированных графах. / Е.О. Басангова, Я.М. Ерусалимский. Деп. в ВИНИТИ. —1982. №5892-82.

7. Водолазов H.H. Поток на графах с ограничениями на достижимость: тр. науч. школы И.Б. Симоненко. / Водолазов H.H., Ерусалимский Я.М. -Ростов-на-Дону: Изд-во ЮФУ, 2010. С. 44-57.

8. Водолазов H.H. Максимальный всплеск в сети и максимальный объем сети. / Водолазов H.H., Ерусалимский Я.М. // Изв. вузов. Сев.-Кавк. регион. Естественные науки. 2010. - №6. — С. 9-13.

9. М.Диниц Е.А. Метод поразрядного сокращения невязок и транспортные задачи. / Е.А. Диниц // Исследования по дискретной математике. — М.:Наука, -1973.

10. Ерусалимский Я.М. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях. / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев-Кавк. регион. Естественные науки. -2003. -№2. С. 3-5.

11. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. 4-е издание. / Я.М. Ерусалимский -М.:Вузовская книга, 2001. 280с.

12. Ерусалимский Я.М. Достижимость на графах с условиями затухания и усиления. / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев.-Кавк. регион. Естественные науки. -2004. Спецвып. Математика и механика. -С. 110-112.

13. Ерусалимский Я.М. Многопродуктовые потоки в сетях с нестандартной достижимостью. / Я.М. Ерусалимский, Петросян А.Г. // Изв. вузов. Сев.-Кавк. регион. Естественные науки. Прил. -2005. -№6. С. 8-16.

14. Ерусалимский Я.М. Некоторые задачи достижимости на графах с ограничениями. / Я.М. Ерусалимский, С.Ю. Логвинов // Изв. вузов. Сев.-Кавк. регион. Естественные науки. —1996. —№2. С. 14-17.

15. Ерусалимский Я.М. Потоки в сетях со связанными дугами. / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев.-Кавк. регион. Естественные науки. Прил. -2003. № 8. С. 9-12.

16. Ерусалимский Я.М. Эйлеровость графов со смешанной достижимостью. / Я.М. Ерусалимский // Модели, графы и алгебраические структуры: сб. -Элиста, 1989.-С. 45-48.

17. Зыков A.A. Основы теории графов. / A.A. Зыков -М.: Наука, 1987. -384с.

18. Кристофидес H. Теория графов. Алгоритмический подход. / Н. Кристофидес. -М.: Мир, 1978. -432с.

19. Кузьминова М.В. Динамические периодические графы. / М.В. Кузьминова // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения XVIII». — Воронеж, 2007. С.97-98.

20. Кузьминова М.В. Ограниченные магнитные достижимости на ориентированных графах. / М.В. Кузьминова // Изв. вузов. Сев.-Кавк. регион. Естественные науки. Прил. -2006. -№6. С. 12-26.

21. Ope О. Теория графов. -2-е изд. / О. Ope -M.: Наука, 1980. 336с.

22. ЪА. Петросян А.Г. Многопродуктовые потоки в сетях с ограничениями на достижимость. / А.Г. Петросян // Математические методы в современных и классических моделях экономики и естествознания: сб. -Ростов-на-Дону, 2005.-С. 136-138.

23. Петросян А.Г. Потоки в сетях с биполярной достижимостью. / А.Г. Петросян // Изв. вузов. Сев.-Кавк. регион. Естественные науки. Прил. — 2006.-№3.-С.32-37.

24. Петросян А.Г. Потоковая задача в многопродуктовых сетях с нестандартной достижимостью. / А.Г. Петросян // Современныепроблемы математического моделирования: сб. -Ростов-на-Дону, 2005. — С.334-340.

25. Рихтер Дж. Программирование на платформе Microsoft .NET Framework /Дж. Рихтер; пер. с англ. — 2-е изд. М.: Издательско-торговый дом «Русская Редакция», 2003. — 512с.

26. Свами М. Графы, сети и алгоритмы. / М. Свами, К. Тхуласираман; пер. с англ. М.: Мир, 1984. - 455с.

27. Скороходов В.А Устойчивость и стационарное распределение на графах с нестандартной достижимостью./ В.А Скороходов // Изв. вузов. Сев.-Кавк. регион. Естественные науки. —2007. —№4. — С.17-21.

28. Скороходов В.А. Графы с магнитной достижимостью. Марковские процессы и потоки в сетях. / В.А. Скороходов. Деп. в ВИНИТИ. -2003. №410-В2003.

29. Скороходов В.А. Случайные блуждания и потоки в сетях с магнитной достижимостью. / В.А. Скороходов // Модели и дискретные структуры: сб. -Элиста, 2002. -С.93-100.

30. Форд JJ. Р. Потоки в сетях. / JI. Р. Форд, Д.Р. Фалкерсон; пер. с англ. -М.:Мир, 1966.-276с.

31. Харари Ф. Теория графов. / Ф. Харари. -М.: Мир, 1973. 300с.

32. Ahuja R. К. A fast and simple algorithm for the maximum flow problem. / R.K. Ahuja, J.B. Orlin. // Oper. Res. -1989. -No.37. PP. 748-759.

33. Ahuja R. K. Improved time bounds for the maximum flow problem. / R.K. Ahuja, J.B. Orlin, R.E. Tarjan. // SIAM J. Copmut. -1989. -No.18. PP. 939954.

34. Alon N. Generating pseudo-random permutations and maximum flow algorithms. / N. Alon // Inf. Proc. Lett. -1990. -No.35. PP. 201-204.

35. Aronson J.E. A survey of dynamic network flows. / J.E. Aronson // Annals of Operations Research. -No. 20. -1989. PP. 1-66.

36. Cook S.A. The complexity of theorem-proving procedures. / S.A. Cook. // Proceedings of the third annual ACM symposium on Theory of computing. ACM New York, NY, USA. 1971. -PP. 151-158.

37. Dantzig G.B. Application of the simplex method to a transportation problem. / G.B. Dantzig // In Activity Analysis and Production and Allocation. -New York: Wiley, 1951. -PP. 359-373.

38. Dinic E.A. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. / E.A. Dinic // Sov. Math. Dokl. -1970. -Noll.-PP. 1277-1280.

39. Edmonds J. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. / J. Edmonds, R.M. Karp //Journal of the Association for Computing Machinery. Vol. 19. - No. 2, -1972. - PP. 248-264.

40. Even S. On the complexity of timetable and multicommodity flow problems. / S. Even, A. Itai, A. Shamir. // SIAM J. Comput. -Vol. 5. -No. 4. -1976. -PP.691—703.

41. Ford Jr. L.R. Maximal flow through a network. / L.R. Ford Jr., D.R. Fulkerson. // Canad. J. Math. -1956. -No. 8. PP. 399-404.

42. Ford L.R. Constructing maximal dynamic flows from static flows. / L.R. Ford, D.R. Fulkerson // Operations Research. -1958 -Vol.6 PP. 419-433.

43. Gabow H.N. Scaling algorithms for network problems. / H.N. Gabow // J. Comput. Syst. Sei. -1985. -No.31. PP. 148-168.

44. Galiil Z. An 0(EV log" V) algorithm for the maximal flow problem. / Z. Galiil, A. Naamad. // J. Comput. Syst. Sei. -1980. -No.21. PP. 203-217.5 2

45. Galil Z. An 0(V3E2) algorithm for the maximal flow problem. / Z. Galil // Acta Inf. -1980. -No. 14. PP. 221-242.

46. Goldberg A. V. A new approach to the maximum-flow problem. / A.V. Goldberg, R.E. Tarjan. // J. ACM. -1988. -Vol.35. -No.4. PP. 921-940.

47. Goldberg A. V. A New Approach to the Maximum-Flow Problem. / A.V. Goldberg, R.E. Tarjan // Journal of the Association for Computing Machinery. -Vol.35. -No. 4.-1988. PP. 921-940.

48. Graves S.C. A Minimum Concave-Cost Dynamic Network Flow Problem with an Application to Lot-Sizing. / S.C. Graves, J. B. Orlin // Networks -Vol.15.1985-PP. 59-71.

49. Helmberg C. Network Models with Convex Cost Structure like Bundle Methods. / C. Helmberg // Models and Algorithms for Optimization in Logistics, Dagstuhl Seminar Proceedings. http://drops.dagstuhl.de/opus/volltexte/2009/2190

50. Karp R.M. Reducibility Among Combinatorial Problems. / Karp R.M. // Complexity of Computer Computations; R. E. Miller and J. W. Thatcher (editors). -New York: Plenum, 1972. PP. 85-103.

51. Karzanov, A. V. Determining the maximal flow in a network by the method of preflows. / A.V. Karzanov // Sov. Math. Dokl. -1974. -No. 15. PP. 434-474.

52. King V. A faster deterministic maximum flow algorithm. / V. King, S. Rao, R. Tarjan. // In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, Fla., Jan. 27-29). ACM, New York, 1992. -PP.157-164.

53. King V. A faster deterministic maximum flow algorithm. / V. King, S. Rao, R. Tarjan. // J. Algorithms. -1994. -No.17. PP. 447-474.

54. Lawler E.L. Combinatorial optimization: networks and matroids. / Lawler E.L. -New York: Holt, Rinehart and Winston, 1976. -374 p.

55. Malhorta V.M. An 0(\ V \3 ) algorithm for finding maximum flows in networks. / V.M. Malhorta, Pramodh Kumar M., S.N. Maheshwari // Inf. Process. Lett. -1978. -No.7. PP. 277-278.

56. Ning Xuanxi. The Blocking Flow Theory and its Application to Hamiltonian Graph Problems. / Ning Xuanxi, Ning Angelika. -Germany, Aachen: Shaker Verlag GmbH, 2006. 249p.

57. Orlin J.B. Maximum-throughput dynamic network flows. / J.B. Orlin // Math. Progr. -1983. -Vol.27. PP. 214-231.

58. Papadimitriou C.M. Computational complexity. / C.M. Papadimitriou. // Addison-Wesley, 1994, -523p.

59. Phillips S. Online load balancing and network flow. / S. Phillips, J. Westbrook. // In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, 1993. PP. 402-411.

60. Skutella M. An Introduction to Network Flows Over Time. / M. Skutella // Research Trends in Combinatorial Optimization. Berlin: Springer Berlin Heidelberg, -2009. PP. 451-482.

61. Sleator D.D. A data structure for dynamic trees. / D.D. Sleator, R.E. Tarjan. // J. Comput. Syst. Sei. -1983. -No.26. PP. 362-391.

62. Tarjan R.E. A simple version of Karzanov's blocking flow algorithm. / R.E. Tarjan // Oper. Res. Lett. -1984. -No.2. PP. 265-268.