Содержание к диссертации
Введение
Глава 1. Обзор литературы. основные понятия и определения 12
1.1. Задача поиска максимального потока на графе 13
1.2. Обзор задач о динамическом потоке 24
1.3. Основные подходы к решению задач на графах с нестандартной достижимостью 28
Глава 2. Поток на графах с нестандартной достижимостью 47
2.1. Определение потока в сети с ограничениями на достижимость 49
2.2. Поток в сети с барьерными ограничениями на достижимость 50
2.3. Обобщение алгоритма поиска максимального потока на графах со связанными дугами 62
2.4. NP-полнота задачи нахождения максимального целочисленного потока с ограничениями на достижимость 73
Глава 3. Динамические потоки в сетях 100
3.1. Основные определения 100
3.2. Ограничение на величину динамического потока 102
3.3. Нахождение максимального всплеска на графе 110
3.4. Нахождение потока, имеющего максимальный объем 119
Заключение 131
Библиографический список используемой литературы
- Обзор задач о динамическом потоке
- Основные подходы к решению задач на графах с нестандартной достижимостью
- Обобщение алгоритма поиска максимального потока на графах со связанными дугами
- Нахождение максимального всплеска на графе
Введение к работе
Актуальность темы исследований. Стремительные перемены, происходящие в мире, ставят перед наукой много вопросов, связанных с перспективами развития экономики, ее ближайшим и отдаленным будущим. В современных условиях повышение эффективности перемещения товаров от производителя к потребителям, информации между компьютерами через электронные сети по всему миру с меньшими затратами является актуальной проблемой. Выбор оптимальных решений таких задач в контексте глобализации современного мира требует научного поиска в этой области.
Известно, что графовые модели (т.е. математические модели, имеющие в своей основе графы и процессы на графах) предоставляют необходимую основу для решения задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управления производством, сетевого и календарного планирования, информационных сетей и многих других. Классическими достижениями этой области математического моделирования являются законы Кирхгофа для электрических цепей, открытие А.Келли природы химических изомеров и созданная Л.Р. Фордом и Д.Р. Фалкерсоном теория потоков в сетях.
Если приписать каждой дуге ориентированного графа поток некоторого вещества, граф становится удобной моделью при исследовании целого ряда проблем в транспорте, связи и других областях, связанных с движением товаров, информации и т.п.
Задача поиска потока максимальной величины и двойственная ей задача поиска минимального разреза - это классические задачи теории потоков в сетях, имеющие важные научные и практические приложения. Например, определение максимальной интенсивности транспортного потока между двумя пунктами и определение части сети дорог, которая насыщена и образует «узкое место».
Обычно поток не перемещается по сети мгновенно, а требуется определенное время для прохождения по каждой дуге. В частности, когда принимается решение о маршрутизации пакета в одной части сети, результат может быть заметен в другой части сети спустя некоторое время. Следовательно, не только величина передающегося потока, но и время, требуемое для передачи, играет важную роль.
Изменение потока с течением времени - это важная особенность задачи о потоке в сети, возникающая в различных приложениях, таких как управление дорожным и воздушным движением, информационные сети (в том числе Интернет) и финансовые потоки. В таких приложениях величины потока по дугам непостоянны и могут изменяться с течением времени.
Указанные выше стороны потока в сети не охватываются классическими моделями стационарного потока. В таких случаях появляется необходимость в рассмотрении потока, изменяющегося с течением времени, т.е. динамического потока, который включает временное измерение и поэтому является более удобным инструментом моделирования многих практических задач.
В классической постановке задач о потоках в сетях граф выступает в качестве носителя задачи о потоке (определяет топологию задачи и пропускную способность дуг), далее рассматривается два класса задач - задачи о стационарном потоке (т.е. в которых поток не меняется во времени) и динамические (в терминологии Л. Форда и Д. Фалкерсона), когда поток меняется в дискретном времени. Теорию стационарных задач, в отличие от динамических, можно считать завершенной.
Последнее время получило развитие исследование сетей с ограничениями на достижимость, которые являются средством для моделирования производственных процессов и телекоммуникационных сетей при наличии ограничений на порядок выполнения отдельных работ, правил транспортировки и т.п. . Обычная (стандартная) достижимость предполагает, что допустимыми
1 Ерусалимский Я.М. Графы с нестандартной достижимостью. Задачи, приложения: моногр. / Я.М. Ерусалимский, В.А. Скороходов, М.В. Кузьминова, А.Г. Петросян. -Ростов-на-Дону: Южный федеральный университет, 2009. - 195с.
являются все возможные пути на графе. Нестандартная достижимость предполагает, что допустимыми являются не все возможные пути на графе, а только те, которые удовлетворяют некоторым дополнительным условиям. В зависимости от того, какие условия рассматриваются, возникают разные виды нестандартной достижимости. Это означает, что в таких сетях не только топология графа и пропускные способности дуг являются основными их характеристиками, новой характеристикой сети становится тип достижимости. Такие сети мы называем сетями с нестандартной достижимостью. Эти сети являются новым классом графовых математических моделей и расширяют класс задач, к которым графовые модели применимы.
Степень разработанности проблемы. Исследованиями в области графовых моделей и разработки алгоритмов решения задач на таких моделях занимались многие ученые, как в нашей стране, так и за рубежом. Выдающимся достижением в этой области следует назвать теорию потоков в сетях, созданную Л.Р. Фордом и Д.Р. Фалкерсоном. Дальнейшее развитие эта теория получила в работах Е.А. Диница, Дж. Р. Эдмондса и P.M. Карпа, А.В. Карзанова, А.В. Голдберга и многих других. Впервые задачи о нестандартной достижимости рассмотрены в работах Я.М. Ерусалимского и Е.О. Басанговой, далее в работах А.Г. Петросяна, В.А. Скороходова и других рассматривались стацинарные потоковые задачи на таких сетях, в работах М.В.Кузьминовой начато рассмотрение динамических задач на сетях с нестандартной достижимостью.
Объект и предмет исследования. Объектом исследования являются графы с нестандартной достижимостью и динамические графы, в том числе с нестандартной достижимостью. Предметом диссертационного исследования являются решения задач поиска максимального потока на графах с нестандартной достижимостью и максимального динамического потока.
Цель исследования. Целью исследования является поиск алгоритмов для решения задач о максимальном потоке на графах с дополнительными
ограничениями на достижимость, а также построение алгоритмов для поиска максимального всплеска в сети и нахождения максимального объема сети.
Научная новизна диссертационного исследования заключается в
доказательстве NP-полноты задачи поиска максимального потока на графах с
некоторыми видами нестандартной достижимости, построении
полиномиальных алгоритмов для задачи поиска максимального потока для
других видов нестандартной достижимости, постановка задачи о
максимальном всплеске и о максимальном объёме сети и построении алгоритмов для их нахождения.
Научная и практическая значимость. Работа носит теоретический характер. Полученные в диссертации результаты могут найти применение в задачах логистики и маршрутизации в коммуникационных сетях.
Достоверность и обоснованность полученных в диссертационном исследовании теоретических результатов обеспечивается корректным применением математического аппарата, строгим математическим обоснованием предложенных методов и алгоритмов.
Основные положения диссертационного исследования, выносимые на защиту:
Доказана NP-полнота задачи нахождения максимального потока для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к > 2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимость.
Построены полиномиальные алгоритмы нахождения максимального потока для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к = 1 и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями.
Исследована задача нахождения максимального всплеска в сети, и приведен алгоритм ее решения.
4. Исследована задача нахождения максимального объема сети, и приведен алгоритм ее решения.
Апробация работы. Основные результаты работы докладывались соискателем на Воронежской весенней математической школе «Понтрягинские чтения» в 2008, 2009 и 2010 годах, на семинарах кафедра кафедры алгебры и дискретной математики ЮФУ, кафедры математического моделирования ЮФУ. Работа поддержана ФЦП «Научные и научно-педагогические кадры инновационной России», Государственный контракт № 02.740.11.0208 от 7 июля 2009 г.
Публикации. Содержание диссертационного исследования и его результаты изложены в публикациях автора. По теме диссертации опубликовано 7 научных работ, 2 работы написаны без соавторов. Общий объем работ, опубликованных по теме диссертации, - 5,7 п.л. Список публикаций приведен в конце автореферата.
Структура диссертационной работы. Диссертация состоит из введения, трех глав, заключения и библиографического списка. Полный объем диссертации составляет 142 страницы, включая 72 рисунка и 3 таблицы.
Личный вклад автора. Все основные результаты работы получены лично автором, научному руководителю принадлежит постановка задачи и обсуждение результатов. Использованные материалы других авторов помечены ссылками.
Обзор задач о динамическом потоке
В настоящее время теория графов [27, 33, 43] стала эффективным средством решения вопросов, относящихся к широкому кругу различных областей и имеющих важные практические приложения. В виде графов можно представить, например, схемы дорог и электрических цепей, карты, схемы управления и блок-схемы программ и т.п. Использование ЭВМ при решении прикладных задач с применением теории графов потребовало создания эффективных алгоритмов решения оптимизационных задач на графах.
Возникнув в начале 50-х годов 20-го, века новое научное направление — исследование потоков в сетях получило широкое распространение, а в последние годы оказало существенное влияние на многие области науки и техники.
Задача поиска потока максимальной величины и двойственная ей задача поиска минимального разреза — это классические комбинаторные задачи, которые имеют научные и практические приложения. Например, определение максимальной интенсивности транспортного потока между двумя пунктами на карте и определение части сети дорог, которая насыщена и образует «узкое место».
В связи с этим предметом диссертационного исследования является решение задач поиска максимального потока в графах с нестандартной достижимостью и максимального динамического потока.
В первой главе дан краткий обзор работ известных отечественных и зарубежных ученых, посвященных изучению потока в сети. В разделе 1.1 «Задача поиска максимального потока на графе» исследованы работы, в которых изучается максимальный стационарный поток. В разделе «Обзор задач динамического потока» анализируются исследования динамического потока на графах и области его применения. В разделе 1.3 «Основные подходы к решению задач на графах с нестандартной достижимостью» описываются подходы к решению основных задач на графах с нестандартной достижимостью, которые явились предпосылками для их дальнейшего изучения.
Задача о максимальном потоке в сети развивалась одновременно с линейным программированием, являясь его частным случаем, и поэтому может быть решена как задача линейного программирования. В 1951 году Г.Б. Данциг [49] предложил использовать симплекс-метод для решения задачи о максимальном потоке.
Существующие специальные, более эффективные, алгоритмы решения задачи о максимальном потоке привлекали исследователей, начиная с 1956 года, когда Л.Р. Фордом и Д.Р. Фалкерсоном был разработан метод увеличивающих цепей [42, 53]. Структура транспортной задачи позволила Л.Р. Форду и Д.Р. Фалкерсону разработать лучший с вычислительной точки зрения алгоритм, чем симплекс-метод. Однако время работы алгоритма Форда-Фалкерсона зависит от величины пропускных способностей дуг. Л.Р. Фордом и Д.Р. Фалкерсоном в [42] был приведен пример сети с иррациональными пропускными способностями дуг, в которой алгоритм Форда-Фалкерсона не заканчивает свою работу и, более того, даже не сходится к оптимальному решению.
В 1970 году Е.А. Диниц [50] и в 1972 году Дж.Р. Эдмондс и P.M. Карп [51] в своих работах показали, что использование кратчайших увеличивающих цепей дает полиномиальный алгоритм решения задачи поиска максимального потока с временем работы, не зависящим от пропускных способностей дуг. Это позволяет решать задачу с любыми пропускными способностями дуг, в том числе иррациональными. Е.А. Диниц [50] предложил находить все кратчайшие увеличивающие пути за один шаг. Метод поразрядного сокращения невязок, разработанный Дж.Р. Эдмондсом и P.M. Карпом [51] и Е.А. Диницом [11], также дает полиномиальное решение задачи. Работы Е.А. Диница, Дж.Р. Эдмондса и P.M. Карпа явились основой для разработки десятков алгоритмов для более эффективного нахождения максимального потока. Так, А.В. Карзановым [65] в 1974 г. было введено понятие предпотока, используемое во многих последующих алгоритмах. Предпоток подобен потоку за исключением того, что суммарная величина потока, входящего в вершину, может быть больше суммарной величины потока, исходящего из вершины.
Все методы, начиная с работ Дж.Р. Эдмондса, P.M. Карпа [51] и Е.А. Диница [50], используют понятие расстояния. При этом обычно длина дуги считается единичной. Дж.Р. Эдмондс и P.M. Карп в работе [51] обсуждают возможность назначения дугам не единичной длины, однако до работы [61] временная сложность алгоритмов, использующих дуги не единичной длины, была не лучше сложности алгоритмов, использующих дуги единичной дуги.
В 1998 А.В. Голдберг и С. Рао [61] предложили использовать адаптивную длину дуг (ноль для дуг с большой пропускной способностью и единица для дуг с маленькой пропускной способностью). Это позволило им улучшить временную сложность их алгоритма.
В табл. 1 (из [59] и [61]) приведен ряд важнейших алгоритмов нахождения максимального стационарного потока. Число вершин в графе обозначено буквой п, а число дуг — буквой т . Время работы некоторых алгоритмов зависит от пропускных способностей дуг сети.
Основные подходы к решению задач на графах с нестандартной достижимостью
Обычно поток не перемещается по сети мгновенно, а требуется определенное количество времени для прохода по каждой дуге. В частности, когда принимается решение о маршрутизации пакета в одной части сети, результат может быть заметен в другой части сети только спустя некоторое время. Не только величина передающегося потока, но и время, требуемое для передачи, играет важную роль.
Изменение потока с течением времени — это важная особенность задачи о потоке в сети, возникающая в различных приложениях, таких как управление дорожным и воздушным движением, информационных сетях (в том числе Интернет) и финансовых потоках. В таких приложениях величины потока по дугам непостоянны и могут изменяться с течением времени.
Указанные выше стороны потока в сети не охватываются классическими моделями стационарного потока. В этих случаях появляется необходимость, в рассмотрении потока, изменяющегося с течением времени, т.е. динамического потока, который включает временное измерение и поэтому является более удобным инструментом для моделирования многих практических задач.
Л.Р. Форд и Д.Р. Фалкерсон, принимая во внимание важность времени перемещения, ввели его в свою модель потоков в сети. В своей книге [42] они привели стандартное определение динамического потока, который является расширением понятия стационарного потока. Каждая дуга {х,у) графа моделирует трубопровод из узла х в узел у . Пропускная способность дуги характеризует поперечное сечение соответствующей трубы. Пропускная способность ограничивает величину потока, входящего в трубу в единицу времени. Время прохождения дуги (х,у) соответствует длине трубы и определяет, как долго поток проходит от вершины X к вершине У по дуге (х,у). Частицы, выходящие из источника в один и тот же момент времени, могут приходить по разным путям и попадать в сток в разные моменты времени.
В работе [42] Л.Р. Форд и Д.Р. Фалкерсон доказывают существование максимального Г-периодического динамического потока. Т -периодический динамический поток по сети G соответствует некоторому стационарному потоку в растянутом по времени варианте G(T) этой сети [42]. Такая сеть может быть построена по G следующим образом. Каждой вершине х ставится в соответствие Т+ \ вершина ,-, і = 0,...,Т сети G(T). Каждой дуге (х,у) ставится в соответствие Т дуг вида ( ,,Ум), / = 0,...,Т — 1. Все такие дуги имеют пропускную способность, равную пропускной способности исходной дуги с((Х;, ум)) = с((х, у)) . Иногда добавляют дуги ( ,-, хм ) , / = 0,..., Т -1 для того, чтобы учесть остатки в вершине х. Таким дугам приписывается пропускная способность, равная бесконечности.
Если узлы s0,sx,...,sk рассматривать в качестве источников, а узлы t0,t{,...,tk в качестве стоков, то условия (2), характеризующие Т-периодический поток из s в t, совпадут с условиями (1), характеризующими стационарный поток в сети G(T) из источников в стоки. Рассмотрим пример сети G (рис. 4). На рис. 5 изображена растянутая по времен сеть (3) для сети
Сеть G(3) Растягивая сеть, как описано выше, задачу о максимальном динамическом потоке можно всегда решать как задачу о максимальном потоке в соответствующей расширенной сети. Более того, таким образом можно решать задачу даже в том случае, если пропускная способность дуг меняется с течением времени. Однако этот метод имеет серьезное ограничение. Размер растянутой по времени сети экспоненциален по log Т. Величина log Т является размером закодированной в некоторой кодировке записи Т. Таким образом, алгоритм, использующий растянутую по времени сеть, имеет время работы полиномиальное относительно Т и экспоненциальное относительно log?" (записи Т в условиях задачи). Такие алгоритмы называются псевдополиномиальными.
Л.Р. Форд и Д.Р. Фалкерсон в [42] предложили более эффективный алгоритм решения задачи, который применим, если пропускная способность дуг не меняется с течением времени. Для нахождения максимального динамического потока используется понятие повторенного во времени потока. Повторенный во времени поток — это динамический поток, который строится из обычного стационарного потока на графе. Для его построения стационарный поток разлагается на потоки по простым путям, динамический поток можно получить из разложения исходного стационарного потока, посылая по каждому пути поток величины, равной величине стационарного потока по этому пути, в течение первых Т — к +1 (на временном интервале [О, Т — к] ) тактов, где к -длина пути. В остальные моменты времени величина потока равна 0.
В работе [42] показано, что построенный таким образом повторенный по времени поток - корректно определенный динамический поток. Л.Р. Форд и Д.Р. Фалкерсон доказывают, что максимальный динамический поток всегда может быть получен как повторенный по времени поток, порожденный стационарным потоком, максимизирующим следующую функцию:
Обычная (стандартная) достижимость предполагает, что допустимыми являются все возможные пути на графе. Нестандартная достижимость предполагает, что допустимыми являются не все возможные пути на графе, а только те, которые удовлетворяют некоторым дополнительным условиям. В зависимости от того, какие условия рассматриваются, возникают разные виды нестандартной достижимости. Впервые задачи о нестандартной достижимости были рассмотрены в работах Я.М. Ерусалимского и Е.О. Басанговой ([3-6, 19, 26]).
В этом разделе мы рассмотрим основные понятия, теоремы и алгоритмы, возникающие при исследовании графов с нестандартной достижимостью.
В работе [14] выделяют два типа нестандартной достижимости: строгую и нестрогую. Нестрогая достижимость подразумевает, что введены правила, которым должна удовлетворять следующая дуга пути. Если во множестве дуг, выходящих из вершины, в которой мы находимся, нет ни одной дуги, удовлетворяющей этим правилам, то следующая дуга может быть любой. Для строгой достижимости в этом случае путь непродолжаем, т.е. выбор следующей дуги запрещен.
К ограничениям достижимости нестрогого типа относятся графы с накоплением неубывающей магнитности, графы с накоплением-исчезновением магнитности, графы с условием биполярной магнитности и графы с условием механической достижимости. К ограничениям достижимости строгого типа относятся графы с условием вентильной достижимости, графы с барьерной достижимостью, графы с ограниченной магнитной достижимостью и графы с ограниченной монотонной достижимостью [14]. На графах с нестандартной достижимостью для решения ряда задач (поиск кратчайшего пути, поиск максимального потока, задачи о случайных блужданиях [39] и др.) нельзя применять классические алгоритмы. Для многих задач на графах с нестандартной достижимостью в отличие от обычной достижимости имеет смысл рассматривать мультиграфы (графы с кратными дугами), так как задачи, поставленные на мультиграфе с нестандартной достижимостью, не могут быть сведены к задаче на обычном графе заменой кратных дуг одной (кратчайшей из них в задаче о кратчайших путях или дугой суммарной пропускной способности в потоковых задачах). Это связано с тем, что кратные дуги могут быть разных типов.
Обобщение алгоритма поиска максимального потока на графах со связанными дугами
В рамках дальнейшего исследования для изучения потоков на графах с нестандартной достижимостью нам потребовалось расширить определение потока. В отличие от классического случая, где важно только число частиц, приходящих в вершину, в случае нестандартной достижимости эти частицы могут быть разного вида в зависимости от пройденного ими ранее пути. Поэтому поток определяется как множество пар. Каждая пара — путь из источника в сток и величина потока по этому пути. Сходным образом (но для решения другой задачи) поток определяется в динамических сетях [54]. Как следует из теоремы о декомпозиции потока, новое определение эквивалентно классическому для графов без дополнительных ограничений (раздел 2.1. этой главы). Так же, как и в классическом случае, для графов с конкретными видами ограничений можно построить определение потока в виде системы уравнений и неравенств. Такое определение мы будем рассматривать в разделе 2.2 «Поток в сети с барьерными ограничениями на достижимость».
Далее мы рассмотрим поток в сетях с барьерными ограничениями на достижимость и приведем существовавший ранее алгоритм «прорыва». На примере показано, что на некоторых графах (даже без барьерных ограничений) этот алгоритм может не находить максимального потока. В данной работе автор строит алгоритм на основе алгоритма Форда-Фалкерсона, обойдя ограничения существовавшего ранее алгоритма. Однако, как показано на примере ниже, и этот алгоритм не всегда может найти максимальный поток [9, 10].
В разделе 2.3 «Обобщение алгоритма поиска максимального потока на графы со связанными дугами» анализируются причины, по которым алгоритмы, основанные на поиске увеличивающих цепей (такие как алгоритмы Форда-Фалкерсона и Эдмондса-Карпа), могут не находить решения. Рассматривается поток на вспомогательном графе, построенном по исходному графу, в котором все пути разрешены. Но, как указано в [14], при построении вспомогательного графа могут появляться связанные дуги — дуги, суммарный поток по котором ограничен. Поэтому потребовалось изменить определение величины разреза на таком графе. Согласно работе [14] часть теоремы Форда-Фалкерсона о том, что максимальный поток ограничен сверху величиной минимального разреза, выполнена и для нового определения разреза. Однако из приведенных примеров мы видим, что другая часть — о том, что существует поток, величина которого достигает величины минимального разреза, не выполнена. На основании этого делается вывод о неприменимости алгоритмов поиска максимального потока, основанных на поиске увеличивающих путей.
В данном разделе автором строится новый алгоритм поиска максимального потока для графов со связанными дугами, и рассматриваются графы, на которых можно применять этот алгоритм.
В разделе 2.4 «NP-полнота задачи нахождения максимального целочисленного потока с ограничениями на достижимость» показано, что задача поиска потока на графах с дополнительными ограничениями на достижимость может быть NP-полна для некоторых видов достижимости [12]. Для доказательства этого утверждения строится специальный вид достижимости — NP- достижимость.
Решение задачи 3-SAT [1] сводится к нахождению максимального потока в специально построенном графе с NP-достижимостью. Показано, что решение задачи о максимальном потоке на графе, построенном в теореме об NP-полноте, с NP-достижимостью эквивалентно задачам на том же графе для сетей с барьерными ограничениями на достижимость, вентильными ограничениями на достижимость (при к 2), магнитными ограничениями на достижимость, монотонными ограничениями на достижимость. Для задачи поиска потока максимальной величины в сети с вентильными достижимостями при к — \ и для задачи поиска потока максимальной величины для графов с ограниченными магнитными достижимостями построены полиномиальные алгоритмы нахождения максимального потока. 2.1. Определение потока в сети с ограничениями на достижимость
Напомним классическое определение стационарного потока (определение 4.).
Подчеркнем, если в графе есть ограничения на допустимые пути, то для определения потока нельзя использовать определение 4. Это связано с тем, что для графов с дополнительными ограничениями на пути важно не только суммарное количество частиц, входящих в вершину, но и пути частиц до попадания в эту вершину.
В ранних работах авторы не давали строгого определения потока в сетях с барьерной достижимостью. Введем в рассмотрение это определение. Пусть // - некоторый путь на графе G, и - некоторая дуга графа G . Обозначим В(/л,и) количество раз, которое путь М проходит по дуге и . В силу теоремы о декомпозиции потока [28] определение 4 является эквивалентным определению 19 при отсутствии дополнительных ограничений на пути.
Отметим, что для конкретного вида ограничений на достижимость можно построить эквивалентное определение стационарного потока с дополнительными ограничениями на достижимость в виде системы линейных уравнений и неравенств (как и в определении 4). Такое определение будет построено в следующем разделе при рассмотрении потока в сети с барьерными ограничениями на достижимость.
Рассмотрим один из видов ограничений на потоки в сети - поток с барьерными ограничениями на достижимость.
Поток в сети с барьерными ограничениями на достижимость Постановка задачи. Требуется найти максимальный поток в графе G(V,U\ф) с дополнительным ограничением на пути частиц, которое в [23] названо барьерной достижимостью. Множество дуг графа U разбито на три непересекающихся подмножества: U н (нейтральные дуги), U+ (увеличивающие дуги) и U Б (барьерные дуги). С каждой частицей, проходящей по графу, связано целое число / - её барьерный уровень. Для частиц, выходящих из источника, он равен 0. Если барьерный уровень меньше некоторого заданного числа к, то при прохождении дуг из множества U+ барьерный уровень увеличивается на 1, при прохождении дуг из множеств Uн и UБ барьерный уровень не изменяется. Частица может проходить по дугам множества только в случае, если её барьерный уровень равен к.
Алгоритм прорыва для поиска максимального потока в сети с барьерными ограничениями на достижимость. Решение описанной задачи предложено в [23]. Для этого по исходному графу строится вспомогательный граф (по правилам, описанным в главе 1). В соответствии с идеей, изложенной в [23], пропускная способность дуг вспомогательного графа не определена. Вместо этого определен максимальный поток по множеству дуг вспомогательного графа, который поставлен в соответствие дуге исходного графа (множеству связанных дуг). Следовательно, применить алгоритм Форда-Фалкерсона нельзя.
В работе [23] авторами был развит новый подход к построению алгоритма. Его сущность состоит в том, что алгоритм ищет кратчайший простой путь на вспомогательном графе из источника в сток, по которому можно пустить увеличивающий поток. Поток увеличивается на некоторую величину, и пропускная способность множеств связанных дуг, через которые прошел увеличивающий путь, уменьшается на эту же величину. Таким образом, в отличие от алгоритма Форда-Фалкерсона алгоритм, описанный в [23] (алгоритм прорыва), ищет не увеличивающую цепь, а увеличивающий путь. Ясно, что найденный поток будет неулучшаемым.
Приведенный ниже пример показывает, что неулучшаемый поток может быть не максимальным в случае, когда возможен блокирующий поток [70]. Блокирующий поток в [70] рассматривается как поток, для которого не существует увеличивающего пути из источника в сток. Надо сказать, в таких случаях (блокировки) алгоритм Форда-Фалкерсона находит решение, поскольку существует увеличивающая цепь
Нахождение максимального всплеска на графе
Покажем, что если формула 3-SAT выполнима, то существует поток величины к 4-1. На графе, соответствующем формуле, положим поток по частям, поставленным в соответствие литералам, равным 0 или 1, в зависимости от значения переменных X (пустим поток по верхней части, если переменная ложна, и по нижней, если она истинна). Так как формула выполнима, то каждая скобка D содержит хотя бы один литерал xi или xi 5 значение которого равно «истина». Тогда можно пропустить поток через вершину Di и через верхнюю или нижнюю часть графа в зависимости от значения литерала.
Таким образом, мы показали, что формула 3-SAT выполнима тогда и только тогда, когда на поставленном в соответствие графе с условиями NP-достижимости существует поток величины к + 1. По формуле, для которой мы решаем задачу 3-SAT, можно провести процедуру построения графа, указанную выше, за полиномиальное время. Тогда можно найти максимальный поток на этом графе, и если он равен к +1, то формула выполнима и по потоку можно указать набор значений переменных, на котором формула истинна. Если максимальный поток оказался меньше чем к + 1, то формула не является выполнимой. Теорема доказана.
Пользуясь этой теоремой, можно показать NP-полноту задачи нахождения максимального потока для сетей с барьерными, вентильными, магнитными и монотонными достижимостями. Пусть рассматривается достижимость, которая разбивает множество дуг р графа на непересекающиеся подмножества [ ) І . Обозначим множество подмножеств дуг lr={t/;}M. Обозначим множество подмножеств дуг Z = {Е1,Е2,Е3,Е4,Е5}, где 19 2 3 4 5 подмножества дуг из NP-достижимости. Тогда для доказательства NP-полноты задачи нахождения потока максимальной величины для каждой из указанных выше достижимостей достаточно указать отображение W :Z — Y такое, чтобы при замене ограничений NP-достижимости на ограничения соответствующей достижимости на графе из теоремы 9 оставалось выполненным условие NP-достижимости: если частица проходила по дуге из множества Е] и среди дуг, выходящих из вершины, в которой находится частица, есть дуга из множества
Е2, то следующая дуга, по которой пройдет частица, должна быть из множества Е2. Все пути, допустимые при NP-достижимости, должны оставаться допустимыми при замене ограничений на достижимость. При выполнении этого условия множество допустимых путей для NP-достижимости будет совпадать с множеством допустимых путей для соответствующей достижимости, и поток максимальной величины для задачи с условиями NP-достижимости будет совпадать с потоком максимальной величины на графе с соответствующими ограничениями на достижимость. Задачи нахождения потока максимальной величины будут эквивалентными на графе, построенном в теореме 9.
Таким образом, для доказательства следствий требуется указать отображение W множества подмножеств дуг графа при NP-достижимости на множество подмножеств дуг графа при соответствующей достижимости и показать, что при таком отображении W и при замене условия NP-достижимости на условия соответствующей достижимости множество допустимых путей на графе, построенном в теореме 9, не изменится. С помощью такого отображения W можно заменить ограничения, накладываемые NP-достижимостью на другие ограничения за полиномиальное время. Заменив ограничения, мы сведем задачу нахождения максимального потока на графе с NP-достижимостью к задаче нахождения максимального потока на графе с другим видом достижимости. Тогда из NP-полноты задачи нахождения потока максимальной величины в сети с NP-достижимостью следует NP-полнота задачи нахождения максимального потока в сети с другими видами ограничений на достижимость.
Отметим, что задача нахождения максимального потока на графе, построенном в теореме, для барьерной, магнитной, вентильной и монотонной достижимостей принадлежит классу NP, так как если дан поток, то за полиномиальное время можно проверить, что он удовлетворяет ограничениям соответствующей достижимости и ограничениям на величину потока по дуге.
Следствие 1. Задача нахождения потока максимальной величины в сети с барьерными ограничениями на достижимость (при k = 1) NP-полна.
Для доказательства построим отображение: W{E ) = U,,; W(E2) = UH ; W(E3) = U+ ; W(E4) = UH W{E5) = UE . тогда на графе из теоремы 9, если из вершины v выходят дуги подмножества 2) то из v выходят только дуги подмножества Е2 и Е5. Но подмножеству Е5 было поставлено в соответствие подмножество UБ. Поэтому, если ранее частица прошла по дуге из Ех 5 то она, в силу конфигурации графа, не могла пройти по дуге из подмножества Еъ (и, следовательно, U+ ), барьерный уровень частицы в вершине V равен 0, и она может выйти только по дуге из подмножества Е2.
