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

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

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

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ НА ГРАФАХ И СЕТЯХ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ

Специальность:05.13.17 - «Теоретические основы информатики»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических на}«

5 ДЯГ 7015

005571214

Таганрог 2015

005571214

Работа выполнена в ФГАОУ ВО «Южный федеральный университет».

Официальные оппоненты: Кузнецов Олег Петрович,

доктор технических наук, профессор, институт проблем управления им. В.А. Трапезникова РАН, заведующий лабораторией №11

Леденёва Татьяна Михайловна,

доктор технических наук, профессор, ФГБОУ ВО «Воронежский государственный университет», заведующая кафедрой вычислительной математики и прикладных информационных технологий

Чернов Андрей Владимирович,

доктор технических наук, профессор, ФГБОУ ВО «Ростовский государственный университет путей сообщения», профессор кафедры информатики

Ведущая организация: ФГАОУ ВО «Самарский государственный аэро-

космический университет имени академика С.П. Королёва (национальный исследовательский университет)»

Защита состоится «21» ноября 2015 г. в 14.20 на заседании диссертационного совета Д 212.208.21 Южного федерального университета по адресу: г. Таганрог, пер. Некрасовский, 44, ауд. Д- 406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, г. Ростов-на-Дону, ул. Пушкинская, 148, http://hub.sfedu.ru/diss/announcement/e60ea3e4-c7b6-4746-Ье40-553Ь<136а1285/

Автореферат разослан «^Д » Л _ 2015 г.

Ученый секретарь диссертационного совета Д 212.208.21 доктор технических наук, профессор

Боженюк А.В.

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

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

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

Выдающимся достижением алгоритмической теории графов стала теория потоков в сетях, созданная J1. Фордом и Д. Фалкерсоном, основным достижением которой является классическая теорема Форда-Фалкерсона о равенстве максимального потока в сети пропускной способности минимального разреза. Дальнейшее развитие этой теории связано с разработкой эффективных алгоритмов решения основной экстремальной задачи — нахождения максимального потока. Среди учёных, внесших основной вклад в развитие этого направления, следует назвать Г. Данцига, Е. Диница, Дж. Эдмонтса, X. Габо-ва, А. Гольдберга, Р. Карпа, В. Кинга, Р. Тарьяна, С. Pao. Если говорить о развитии общих подходов к теории сетей, то следует особо выделить работы А.Гольдберга и С. Pao, недавние работы О.П. Кузнецова и Л.Ю. Жиляковой по ресурсным сетям.

Теория потоков в сетях находит все большее применение в связи с развитием телекоммуникаций (Internet, мобильная связь, глобальные компьютерные сети, облачные вычислительные системы и т.п.), логистики, теории нейронных сетей, биоинформатики. «Современная теория сетей стала прототипом междисциплинарных исследований: социология, компьютерные науки, химия, экономика, энергетика, транспорт, управление бизнесом и, сравнительно недавно, социальные сети и биоинформатика. Целям и задачам все этих наук служит эта теория» (Newman M. Networks: an Introduction//Oxford University Press, Inc., New York, NY, 2010. - 720 p.).

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

Важным инструментом тестирования, анализа программ и автоматического распараллеливания является управляющий граф программы (В.В. Воеводин, В.А. Евстигнеев, В.Н. Касьянов, C.B. Огородов, Л. Лампорт, Р. Аллэн, К. Кэннеди, М. Вольф и др.)

В прикладных задачах, обычно, изучается не сам граф, а процессы на нём. Большинство из них связаны с перемещениями по путям на графе. Соединимость одной вершины путём, ведущим из другой вершины, называется достижимостью одной вершины из другой. Три основных задачи прикладной (алгоритмической) теории графов связаны с достижимостью. Это сама задача о достижимости и нахождении кратчайшего пути, задача о случайных блужданиях по вершинам графа и задачи о потоках в сетях (поток можно считать перемещением «вещества» (информации, материи, товаров, жидкости, энергии и т.п.) по путям, ведущим из источника в сток). Среди работ по этой тематике отметим монографию М.И. Нечипуренко, В.К. Попкова, С.М. Майнагашева и др. «Алгоритмы и программы решения задач на графах и сетях» (Новосибирск: Наука. Сиб. отд-ние, 1990._515 с.) и монографию В.К. Попкова «Математические модели связности» (2-е изд., Новосибирск: Изд-во ИВМиМГ СО РАН, 2006. - 490 е.), в которых рассмотрены различные задачи о достижимости: о кратчайшем пути, наиболее надежном пути, наиболее вероятном пути и др. В этих задачах экстремум ищется на всем множестве путей графа. В прикладных задачах такой подход не всегда оправдан. Не все пути могут быть допустимы для рассмотрения, например, из-за технологических ограничений.

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

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

Ограничения на достижимость возникают в прикладных задачах. Рассмотрим телекоммуникационную сеть. Будем интерпретировать её как граф, вершины которого соответствуют пунктам приема и передачи информации. Дуги соответствуют каналам связи. В процессе передачи сигнала по каналу связи с ним могут происходить изменения - сигнал может затухать и если его уровень понизится до уровня естественного шума, то возникает его потеря.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Научная новизна заключается в следующем:

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

вом допустимых путей на графе с ограничениями на достижимость и множеством путей на развертке. Метод характеризуется общностью для различных типов ограничений на достижимость в ориентированных графах и сетях -смешанной, магнитной, монотонной, вентильной, барьерной, ступенчатой — и отличается от известных аналогов, в частности от метода временной развертки динамического потока, учетом видов ограничений на достижимость, что позволяет эффективно решать оптимизационные задачи на графах широкого класса (стр. 28-29, 33-34, 53-55, 60-62,100-103, 105-106, 121-122).

2. Разработан метод решения задач нахождения кратчайших путей на графах при различных ограничениях на достижимость на основе перехода к задаче отыскания кратчайшего пути на развертке из вершины в подмножество вершин, что позволяет применять известный алгоритм Дейкстры, который непосредственно, без перехода к развертке, неприменим для решения задач в исходной постановке (стр. 27 - 39, 42 - 44).

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

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

5. Дан конструктивный вывод балансового соотношения, доказана разложимость потока в сумму фронтальных потоков, а также его разложимость в сумму двух потоков специального вида для случая динамических потоков тождественно равных нулю при / < О, что позволяет дать оценку сверху средней величины динамического потока на временном промежутке величиной максимального стационарного потока (стр. 126 -140).

6. Исследован эффект всплеска динамического потока в сети, даны необходимые и достаточные условия для топологии сети, при которых возможно возникновение всплесков, при этом максимальная величина всплеска в случае динамических потоков является, наряду с величиной максимального стационарного потока, параметром сети (стр. 149 —163).

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

вертка является конечным графом, что делает алгоритмически разрешимыми задачи нахождения оптимальных путей и потоков в данном классе динамических графов (стр. 166 -180).

8. Даны необходимые и достаточные условия существования функции Гранди графа, отличные от известных условий достаточности; для неориентированных графов доказано существование бесконтурной ориентации, сохраняющей функцию Гранди, что в совокупности позволяет обосновать и синтезировать алгоритм нахождения семейства функций Гранди графа в ориентированном и неориентированном случаях (стр. 184 -192).

Основные положения, выносимые на защиту

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

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

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

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

5. Метод временной развёртки динамических графов и сетей, имеющих нейтральные дуги и дуги, которые в различные временные промежутки могут присутствовать (промежутки активности) или отсутствовать (промежутки пассивности), и доказанная на его основе алгоритмическая разрешимость задач нахождения оптимальных путей и потоков в периодическом случае.

6. Методы нахождения семейства функций Гранди графа в ориентированном и неориентированном случаях на основе связи этой функции на ориентированном графе и на его бесконтурных частичных графах, а также на основе существования бесконтурной ориентации, сохраняющей функцию Гранди неориентированного графа.

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

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

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

Внедрение и использование результатов работы. Полученные в работе результаты

- Внедрены в ФГАНУ «Спецвузавтоматика» при выполнении НИР по госконтракту №2/Бр-13 от 20.042013 и в целом приняты к использованию в основной деятельности данной научно-исследовательской организации.

- Использованы в Институте математики, механики и компьютерных наук имени И.И. Воровича ЮФУ в работах по Проекту Е02-01-231 «Нестандартная достижимость на ориентированных графах». Грант конкурсного центра Минобразования РФ по разделу естественные науки.

- Использованы в Институте математики, механики и компьютерных наук имени И.И. Воровича ЮФУ в работах по проекту 7857 «Графы и сети с нестандартной достижимостью». Ведомственная программа Минобрнауки РФ «Развитие научного потенциала высшей школы», подпрограмма № 3, раздел 3.3.

- Использованы в учебном процессе кафедры алгебры и дискретной математики ЮФУ в лекционных курсах «Конечные графы и сети», «Алгоритмы на графах», «Дискретная математика», читаемых на факультете математики, механики и компьютерных наук ЮФУ, включены в учебное пособие [35], имеющее гриф Минобразования РФ «Допущено в качестве учебного пособия для студентов высших учебных заведений по направлениям подготовки и специальностям «Прикладная математика и информатика» и «Математика»» и монографию [33].

Апробация работы. Основные результаты апробированы на ряде научных конференций и семинаров различного уровня, в том числе: Всероссийского: III всероссийской школе-семинаре «Математическое моделирование и биомеханика в современном университете» (Ростов н/Д, 2007), на весенней Воронежской математической школе «Понтрягинские чтения - XXI (Воронеж, 2010), на весенней Воронежской математической школе «Понтрягинские чтения - XXII (Воронеж, 2011), на весенней Воронежской математической школе «Понтрягинские чтения - XXV (Воронеж, 2014), международного". международном конгрессе математиков (Мадрид, 2006), на IV-й Международной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования» (Воронеж, 2011), на Кишинёвском и Одесском семинарах по графам и гиперграфам проф. А.А.Зыкова, на семинаре в Бранденбургском техническом университете (Коттбус, Германия, 2014, рук. проф. С. Пикенхайм), на VI международной

конференции «Современные методы прикладной математики, теории управления и компьютерных технологий» (Воронеж, 2013), на VII международной конференции «Современные методы прикладной математики, теории управления и компьютерных технологий» (Воронеж, 2014), на международных конференциях «Современные методы и проблемы теории операторов и гармонического анализа и их приложения III, IV и V» (Ростов-на-Дону 2013, 2014, 2015), а также на семинаре кафедры алгебры и дискретной математики Южного федерального университета, на семинаре кафедры математического моделирования Южного федерального университета, на семинаре кафедры математической кибернетики ВМК МГУ (2012), на НТС в Самарском государственном аэрокосмическом университете им. акад. С.П. Королева (Самара, 2015, рук. проф. Сергеев В.В.), на семинаре в ИПУ РАН (Москва, 2015, рук. проф. Кузнецов О.П.).

Публикации по теме исследования. Всего по теме диссертации опубликовано 47 работ. Из них в изданиях из списка ВАК, рекомендованных для опубликования результатов диссертационных исследований, — 13, в реферируемых зарубежных изданиях - 2, в спецвыпусках журналов из списка ВАК 3, монографий - 1, учебников - 1, учебных пособий - 2.

Личный вклад автора. Все результаты, изложенные в диссертации, получены автором либо самостоятельно, либо при его непосредственном активном творческом участии. В совместных работах, опубликованных со своими учениками, автору принадлежит общая постановка задач и осуществление непосредственного руководства. Диссертационные работы учеников (Басангова Е.О., Логвинов С.Ю., Скороходов В.А., Петросян А.Г., Кузьмино-ва М.В., Водолазов H.H.) посвящены в основном алгоритмам решения задач о кратчайших путях, случайных блужданиях, потоках в сетях на графах и сетях с конкретными видами ограничений на достижимость. В настоящей работе рассмотрены наиболее общие вопросы, связанные с ограничениями на достижимость на графах и сетях, а также их возможные приложения.

Структура и объём диссертации. Работа состоит из введения, семи глав и трех приложений на 258 стр., список литературы содержит 226 наименований.

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

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

Пусть G(X,U,f) - орграф. (Здесь X -множество вершин, [/-множество дуг, f :U ->А'х J- отображение сопоставляющее каждой дуге упорядоченную пару вершин (начало дуга; конец дуги).

Определение 0. Путем длины п на графе будем называть отображение ц: [1; л]Л- —> I], для которого выполнено условие:

(Р2°/°/0(0 = (А °/°-"X' +1), / = 1,2,...и —1.

Здесь (р2 ° / ° /¿Х0 - конец дуги //(г), {Р\° / ° /00 +1)" начало дуги //(г +1). Таким образом, путь - это такая последовательность дуг графа, в которой каждая следующая дуга начинается в вершине, в которой заканчивается предыдущая дуга. В связи со сказанным, для пути из п дуг мы можем

использовать и другое обозначение - {н,}"= 1.

Графы со смешанной достижимостью

Первый вид ограничений - смешанная достижимость. Множество дуг графа представлено' следующим образом: и = их У->и2, ик Ф 0, и2 0. Дуги множества ик будем называть нейтральными, а множества и2 - запрещенными.

Определение 1.2.1 ▲ Смешанным путем на графе С(Х, I/, /) будем называть путь {г<,-}"=1 удовлетворяющий условию:

V/ (и,- е и2 => г/,+1 е £/д) г е [1 ;и - % = {1,2,...,« -1} . А

Это означает, что в последовательности дуг смешанного пути дуги множества I]2 не следуют подряд (прорежены дугами множества 17к).

Определение 1.3. Графом со смешанной достижимостью будем называть граф, на котором допустимыми являются только смешанные пути (см. определение 1.2).

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

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

Для преодоления возникших трудностей строится вспомогательный граф (развёртка) и устанавливается соответствие между множеством допустимых путей на графе со смешанной достижимостью и множеством путей на развертке.

Опишем построение развёртки для графа со смешанной достижимостью С?(Х,[/=С/ди£/2,/). Множеством вершин этого графа является множество где X' - дубликат множества X, т.е. каждой вершине х&Х соот-

1 Нумерация определений, утверждений, теорем, рисунков соответствует тексту диссертации.

ветствует х' е X'. Если и е ик, /(а) = (х,у), на развёртке ей соответствует две дуги, первая соединяет вершину х с вершиной у, а вторая дуга начинается в вершине х' и заканчивается в вершине у. Если и<=иг, /(и) = (х,у), на развёртке ей соответствует дуга, которая соединяет вершину х с вершиной у'.

Пример 1.1. Рассмотрим граф, изображенный на рис. 1.1.

7

5

Рис. 1.1.

На рисунке запрещенные дуги обозначены пунктиром. Путь, проходящий через вершины 7 - 5- 6 не является смешанным, также не является смешанным путем 1-2-3—4—5-6. Единственный смешанный путь, соединяющий вершину 1 с вершиной 6, проходит через вершины1-8-4-5-6.

На рис. 1.2 приведена развёртка - С для графа рис. 1.1.

1' Г 3' 4' 5* 6' Г 8"

Рис. 1.2.

Имеет место:

Утверждение 1.1. Вершина у достижима из вершины X на графе Б со смешанной достижимостью тогда и только тогда, когда на развёртке С существует путь из вершины х хотя бы в одну из вершин множества {у, у'}.

Если на исходном графе заданы длины дуг, то развёртку тоже считаем взвешенным графом, полагая длины её дуг равными длинам породивших их дуг исходного графа.

Утверждение 1.2. Длина кратчайшего пути из вершины х в вершину у на графе й со смешанной достижимостью равна длине кратчайшего пути из вершины X в вершины множества {у, у'} на развёртке С. Этот кратчайший смешанный путь может быть восстановлен по кратчайшему пути из вершины X в вершины множества {у,у'} на развёртке Б'.

Ясно, что этот кратчайший путь на графе G' может быть найден с помощью алгоритма Дейкстры.

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

Графы с накоплением неубывающей магнитности Определение 1.4. А Пусть дан граф G(X,U,f), U = UHuUM UH n UM = 0. Множество им называется множеством магнитных дуг, а Ufj - множество немагнитных дуг. Пусть ц - путь, состоящий из п дуг. С каждым отрезком [г; j]N (1 < г < j < п) пути свяжем числовую характеристику

Vi,y)=SlM»»)}n£/Af|, (2)

m=i

равную количеству магнитных дуг этого отрезка, при этом каждая магнитная дуга считается столько раз, сколько раз она встречается в пути. Характеристика называется величиной накопленной неубывающей намагниченности на отрезке [г; j]N пути /л ▼

Определение 1.5. Путь /л называется магнитно-накопительным путем порядка k(> 1) с неубывающей намагниченностью на графе G, если выполняется следующее условие:

> kXU+((p2 о / о //Х»0)

Здесь р2(х;у) = у, U+{z) - множество дуг, выходящих из вершины z . Другими словами, если к 1 -му шагу от своего начала путь /у накопил намагниченность (г), большую либо равную к, и среди дуг, выходящих из концевой вершины I -й дуги, есть хотя бы одна магнитная, то следующая (/ +1) -я дуга магнитно-накопительного пути порядка к обязана быть дугой из множества Uм ■

Определение 1.6. Граф, на котором рассматриваются только магнитно-накопительные пути порядка к , будем называть графом с накоплением неубывающей намагниченности порядка к .

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

Пример 1.2. Рассмотрим граф G, изображенный на рис. 1.6. Множество магнитных дуг UM = {(a,b), (Ь,с)} (помечены буквой «М»), множество немагнитных дуг UH = {(a,c),(b,d),(c,d)} (помечены буквой «Н»). Порядок магнитности к = 1. Развёртка G' для графа G изображена на рис. 1.7.

Рис. 1.6. Граф G

Я

Рис. 1.7. Развертка графа - граф G'

При отсутствии условия намагниченности путь {{а, b), (Ь, с)} является допустимым, однако, на рис. 1.7 видно, что с добавлением условия намагниченности такой путь становится недопустимым. Ясно, что имеют место утверждения аналогичные утверждениям 1.1 и 1.2.

Завершает главу рассмотрение ещё одного типа достижимости - барьерной достижимости. Она также как и магнитная достижимость определяется не локально, а глобально (на отрезках пути).

Пусть G(X,U,f) - граф, U = U0 Ub , множества U0, U+ и U+

попарно не пересекаются. Множество U0 - множество нейтральных дуг, U+ - множеством дуг, увеличивающих барьерный показатель (множество увеличивающих дуг), U+ - множество дуг барьерного перехода (множество барьерных дуг).

Определение 1.7. А С каждым отрезком [0;z']z (где 0 < i < п ) пути М из п дуг свяжем числовую характеристику ßß (/), определенную индуктивно следующим:

1. /у0) = 0.

ßM(i\ если n(i) eU„;

2- ßM(i + l) = . ßM(i) + l, если //(/)ei7+;

0, eciu ß(i) eUB.

Характеристикаß^ii) называется величиной накопленной энергии на отрезке [0;/]/ пути М ■ ▼

Определение 1.8. Графом с барьерной достижимостью высоты h (h^N) будем называть граф, все пути ц на котором удовлетворяют условию:

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

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

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

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

В § 2.1 рассмотрена задача о случайном блуждании по вершинам графа со смешанной достижимостью.

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

1

(4)

Рис. 2.1.

Построим развёртку графа.

Рис.2.2.

Если на дуги вспомогательного графа перенести вероятности перехода с исходного графа, то произойдёт нарушение основного вероятностного соотношения:

5>(и) = 1 (5)

иеи+Ы

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

р'(и) = ——1----(6)

иеи+(х)

Для тупиковых вершин считаем, что после попадания в неё, вероятность остаться в ней равна единице. Ясно, что для графа рис. 2.2

/>'((1Д)) = //(0,8')) = //((1,7)) = 1, //((5',1)) = 1;//((Г,7)) = //((!',2)) = I •

Построение развёртки и указанный выше перенос на неё переходных вероятностей с исходного графа делает справедливым следующее утверждение:

Утверждение 2.1. Вероятность попасть из вершины х в вершину у на

графе О со смешанной достижимостью за п шагов равна вероятности попасть из вершины х хотя бы в одну из вершин множества {у, у'} за п шагов на развёртке С.

В § 2.2. определен новый тип достижимости - монотонная достижимость.

Определение 2.1. Пусть С(Х,17,/)) - граф и и = 1/0 о С/, *ии2 множества - непустые попарно непересе-

кающиеся. Множество С/0 будем называть нейтральным, а множества и ■, / = 1,2,...,/и- монотонными уровня /.

Определение 2.2. Пусть -»£/ - путь на графе в{х,и,/).

Свяжем с ннм числовую последовательность {а,- (ц)}"ых, я, (р) = е и) • т.е. последовательность номеров множеств, которым принадлежат дуги пути.

Определение 2.3. ▼ Путь //:[1;и]у —»£/ на графе будем называть монотонным, если подпоследовательность положительных элементов последовательности {а,(я)}"=1 является неубываюгцей. ▲

Таким образом, монотонность пути означает следующее, - если он на каком-то шаге прошел по дуге из множества с номером к , то на любом из последующих шагов он не может проходить по дугам множеств с номерами \,2,...,к—1.

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

В § 2.3. введён в рассмотрение ещё один вид достижимости, которую мы назвали вентильной.

Графы с вентильной достижимостью Определение 2.5. ▲ Пусть {/,/)) - граф и и = множества [/,• - непустые попарно непересекающиеся. Множество £/0 будем называть нейтральным, а множества и. вентильными уровня г. ▼

Определение 2.6. ▲ Путь /г:[1;и]д. на графе будем называть вентильным, если выполнено условие

//(г)е1/к о//({1;/-ф)пик_х *0,к = \,...,т. ▼ (7)

Вентилъность пути означает следующее,- если он на каком-то шаге прошел по дуге из множества с номером к -1, то на любом из последующих шагов он может проходить по дугам множеств с номерами 1,2,...,к.

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

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

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

Определение 3.1. ▲ Пусть С(Х, С/, /, с) - сеть с ограничениями на достижимость, с - пропускная способность дуг, т.е. с'.и —>(0,+°о), р — допустимый путь из источника в сток. С каждой дугой и, через которую проходит путь /л , свяжем характеристику У^(и) - кратность дуги и на

пути р. , равную количеству прохождений пути по этой дуге и определённую равенством:

= ▼ (8) Определение 3.2. ▲ Пусть С(Х, и, /, с) - сеть с ограничениями на достижимость, ¡л — допустимый путь из источника в сток. Потоком по пути р будем называть такую постоянную е(0,°о), которая удовлетворяет условию:

у^и)-<рм<с(и) (9)

для любой дуги пути р.. ▼

Определение 3.3. Поток по пути р называется насыщающим этот путь, если существует такая дуга пути р, для которой в соотношении (9) выполнено равенство.

Определение 3.4. ▲ Пусть и, /, с) - сеть с ограничениями на достижимость. Потоком в такой сети будем называть множество элементами которого являются пары вида {р\ (рИ), где р - допустимый путь

из источника в сток, (рц — поток по пути ¡л, при этом для каждой дуги графа выполнено условие

з>ли><р„*т (ю)

ие/ЧА'^И'

Определение 3.5. ▲ Пусть С{Х, и, /, с) - сеть с ограничениями на достижимость, У - поток в такой сети. Величиной потока 4х на дуге и будем называть величину (Рч>(и), определенную равенством:

а/. Т. (11)

4>ч( и) = Т.<Ри

Определение 3.6. А Пусть С(ХЪ £/, /, с) — сеть с ограничениями на достижимость, $ - источник, I — сток, Ч7 - поток в такой сети. Величиной потока будем называть характеристику

UBll.it)

равную суммарному потоку по всем дугам, заканчивающимся в стоке. ▼

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

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

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

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

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

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

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

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

кратчайшего пути между вершинами на графе с затуханием на дугах и усилением в вершинах.

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

Когда мы рассматриваем динамические потоки, то добавляется дискретное время / £2. Считается, что каждый переход по дуге совершается за единицу дискретного времени (т.е. за один такт).

Приведем определение динамического потока:

Определение 5.2. Динамическим потоком в сети ах,и,/,с) называется отображение (р: и х 2 -> , удовлетворяющее следующим условиям:

)Х9>(».0 = ХК"-' + О; х е X, х * х * г, Г е 2

иеПМ) иеС/Л*) (14)

0 < <р{и^) < с(и),

где 5 - источник; Г - сток; ? - время, с(и) - пропускная способность дуги.

Определение 5.3. Величиной потока <р в момент времени ? назовем величину \{ср,(), определенную равенством:

Н<Р,0 = Х<РЫ).

иёи_(г)

т.е. суммарный поток, входящий в сток в момент времени /.

Определение 5.4. Величиной потока ср на интервале [Т{\Т2]г (далее вместо [Г,;Г2]2 будем писать [Г,;Г2]^ называется величина У(<р, [Г,, Т2 ]), определенная равенством:

К(9>,[Г1;Г2])= !у(9>,0 (16)

т.е. суммарный поток, приходящий в сток за промежуток времени [Г1;Г2]. Ясно, что имеет место равенство:

2>(и, 0= X <?>(», 0 + X <?>(», 0 + X ср(и, 0 =

и^и иеи^) иеи\(и^и\>и_(г)) ие[/_(г)

= X р(">0+ X ?>(«<, 0+^,0

(17)

X <р(и,о+ 5>(«,о = !>(«,/+1)+ X 1)

иес/д*) иее/\([/+(;г)ис/_(г)) и^и_(,г)

19Ки,/ + 1) + К(9»,/ + 1).

иеС/\((7+(5)иС/_(г))

Обозначим

I<J)= Z (p{u,t\II(t)= X <p(u,t),III(t)= X <K",0

ueU+(«) u<EU\(U^s)uU_(r)) ueU_(r)

Доказана

Теорема 5.1. Для любого динамического потока ср тождественно равного нулю при t<0 и любого Т > О, Т е Z имеет место основное балансовое соотношение:

£/(0 = 1]) + I(T) + II(T) + IU(T). (19)

/<0;г]

Для произвольного динамического потока (р и произвольных Тх <Тт,Тх,Т2 е Z, справедливо следующее балансовое соотношение:

1(Т1) + П(ТХ) + Ш(Т1)+ £/(/) =

i<Ti+i;r2] (20)

= V(<pX0\T2 -1]) + 1(Т2) + П(Т2) + Ш(Т2).

Определение 5.6. Два динамических потока и ,р2 будем называть эквивалентными на временном промежутке [Т^Т^,^ <Т2,Т]УТ2 eZ, если для любого t e[Tl\T2]z имеет место равенство F(<Pi,t) = F(<p2,t).

Определение 5.7. Пусть <р - динамический поток. Динамический поток (р{ будем называть частью потока <р, если для любой дуги и любого t выполнено неравенство:

0 <<pl(ii,t) < <p(u,t). (21)

Определение 5.8. Пусть (р - динамический поток, тождественно равный нулю при t < 0. Фронтальным потоком потока <р будем называть поток (pF, который удовлетворяет условиям:

1. cpF является частью потока ср ;

2. <pF (и,0) = <р(и,0), Vw е U ;

3. <pF (u,t) = 0, Vw е U+ (s), \ft > 1.

Фронтальный поток - это та часть потока (р, которая порождена подачей в сеть в момент ( = 0 на дуги множества [/+(л-)тех же значений, что имел поток <р, и «заглушкой» входа в сеть при t > 1.

Теорема 5. 2. Для любого динамического потока (р в ориентированной сети G(X,U,f,c) тождественно равного нулю при t< 0 существует фронтальный поток <pF.

Теорема 5. 3. Для любого динамического потока <р в ориентированной сети G(X,U,f,c), тождественно равного нулю при / < 0, и Г>0, Г eZ имеет место равенство:

ср(и,t) = (pF(u,t) + <(\F(u,t) + --- + <pTF(г/,/), V/ < Т (22)

Здесь <plF -фронтальный поток для потока <p-<pF, <p2F -фронтальный поток для потока <p — <pF— cp]F, и т.д.

Равенство (22) будем называть разложением потока на промежутке [0;Г] в сумму фронтальных потоков.

Теорема 5.4. Пусть <p(u,t)- динамический поток в сети G(X,U,f,c), равный нулю на всех дугах сети при t< 0, тогда для произвольного Т &N, существуют такие потоки <pt(u,i), <p2(u,t), для которых выполнены следующие условия:

1. потоки <px(u,t), <p2(u,t) - части потока <p(u,t) ;

2. поток tp^uj) равен нулю на всех дугах графа при t>T;

3. поток эквивалентен потоку <р на промежутке [Oj^], т.е. v(<p,t)=vfa,t\te[0;T];

4. поток <р2 эквивалентен нулевому потоку на промежутке [0;Г], т.е. v(<p2,t)= 0, ? e[0;7"]z.

Обозначим через v^ величину максимального стационарного потока сети, тогда, очевидно, имеет место теорема:

Теорема 5.5. Пусть <p(u,t)— динамический поток в сети G(X,U,f,c) равный нулю на всех дугах сети при t< О, тогда для произвольного Т е N имеет место оценка

ф,[0 ;фут.Г. (23)

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

Пример 5.2. Рассмотрим сеть, изображенную на рис. 5.11. Пропускные способности всех дуг будем считать равными 1.

Рис. 5.11.

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

1. Этот поток равен 0 на всех дугах при t < 0.

2. На дуге, выходящей из источника этот поток равен 1 при t > 0.

3. При t = 1 «единица» потока с первой дуги передается на дугу верхнего пути.

4. При t = 2 «единица» потока с первой дуги передается на дугу пути, следующего за верхним путём и т.д. до t = 10, а далее все повторяется.'

Ясно, что при / = 10 в сети наблюдается всплеск равный 10. Очевидно, что этот всплеск максимальный.

Пример 5.3. Рассмотрим сеть, изображенную на рис.5.12. Будем считать, что пропускная способность дуги, выходящей из источника равна 1, а остальных дуг равна 5.

Рис. 5.12.

Зададим на этой сети поток, считая его нулевым на всех дугах при / < 0, а далее заданный рисунками 4512а, 5.126,.....

Рис. 5.12а.

Рис.5.12в.

! !

Рис. 5.12д.

Рис.5.12б.

Рис. 5.12г.

! 2 0 Рис. 5.12е.

и т.д., пока не получим:

Рис. 5.12ж.

Следующие четыре момента времени поток выглядит так: * о

1 5 5

Рис. 5.12 е.

5 5

Рис.5.12 ж.

Рис. 5.12з. Рис. 5.12и.

Затем всё повторяется, начиная с рис. 5.12г.

Таким образом, мы получили поток, дающий четыре раза подряд всплеск равный 5. Ясно, что это всплески максимально возможной величины.

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

Теорема 5.5. даёт верхнюю оценку объема потока на временном интервале. Чем больший всплеск удаётся получить, тем большее «падение» потока должно перед этим произойти, поскольку для возникновения всплеска необходимо накопить внутри сети (т.е. не выдавая его в сток) достаточное количество «материала».

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

Пример 5.6. На рис. 5.23 изображена сеть, в которой пропускные способности дуг, обозначенных пунктиром, равны единице, а остальных дуг - четырем. Ясно, что на этом графе всплесков динамического потока быть не может.

Рис. 5.23. Пример сети, не допускающей всплесков.

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

Теорема 5.5. Для того чтобы в ориентированной сети существовал ди-налшческий поток, имеющий всплески, необходимо и достаточно, чтобы существовал такой насыщенный поток ц/ и концевая вершина у ближайшего к стоку разреза с минимальной пропускной способностью, из которой на графе G'y¡w ведут в сток пути разной длины, имеющие суммарную пропускную способность, большую чем пропускная способность этой вершины.

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

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

Теорема 7.1. Пусть g - функция Гранди графа С(Х,Г), содержащего контуры, тогда существует такой бесконтурный частичный граф G(X, Г') , имеющий туже самую функцию Гранди g .

Следствие из теоремы 7.1. Пусть g- функция Гранди графа G(X, Г), содержагцего контуры, тогда существует максимальный по вложению бесконтурный частичный граф G(X, Г') , имеющий ту же самую функцию Гранди g.

Теорема 7.2. Пусть g - функция Гранди частичного графа G(X,V) графа G(X, Р). Для того, чтобы g была функцией Гранди графа G(X,T) необходимо и достаточно, чтобы для любых двух вершин х, у несоединенных дугой на графе G(X,V) и соединенных дугой на графе G^.r) выполнялось условие:

g(x)*g(y).

Теорема 7.3. Пусть G{XJ) - неориентированный граф, g - его функция Гранди, тогда существует такая ориентация его дуг, что полученный ори-

ентированный граф не содержит контуров и g является функцией Гранди этого ориентированного графа (причём единственной).

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

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

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

В приложении 4 содержатся акты использования результатов работы.

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

Публикации в изданиях из списка ВАК РФ:

1. Ерусалгшский, Я.М. Некоторые задачи достижимости на графах с ог-

раничениями на прохождения по дугам [текст]/ Я.М. Ерусалгшский,

С.Ю. У7огегшоя//Известия вузов. Северо-Кавказский регион.

Ест.науки. -1996. -№2(94).- С. 14-17. (2Ы 0917.05073)

2. Ерусалгшский, Я.М. Общий метод решения задач о достижимости

[текст]// Известия вузов. Северо-Кавказский регион. Ест. науки. -

2000-№3. - С. 62-63. (Ш 1009.05082)

3. Ерусалшккий, Я.М. Потенциальный оператор, функция Грина на

ориентированных графах и некоторые их приложения в квантовой механике [текст]/ ¡Ерусалшккий Я.М., Степовой Д.В.// Известия вузов. Северо-Кавказский регион. Ест. науки. - 2001. - S1. - С. 67-71.

4. Ерусалшккий, Я.М. Графы с вентильной достижимостью. Марков-

ские процессы и потоки в сетях [текст]//Я.М. Ерусалгшский, В.А. Скороходов // Известия вузов. Северо-Кавказский регион. Ест. науки. - 2003. -3. - С. 3-5. (Zbl 1050.68109)

5. Ерусалшккий, Я.М. Биномиальные коэффициенты в тождествах для

натуральных чисел, факториалов и многочленов [текст]// Известия вузов. Северо-Кавказский регион. Ест. науки. - 2008. - №5(147). -С. 27-29. (Zbl 1199.11052)

6. Ерусалшккий, Я.М. Случайные блуждания по графу-решётке и ком-

бинаторные тождества [электронный ресурс]// Инженерный вестник Дона. - 2015. - №2 ч.2. - 12 стр. URL .•ivdon.ru/ru/magazine/archive/n2p2y2015/2964. Режим доступа: свободный

7. Ерусалшккий Я.М. Нестационарный поток в сети /Я.М. Ерусалим-

ский, H.H. Водолазов //Вестник ДГТУ. - 2009. - т.9 №3. - С. 402409.

8. Ерусалшккий, Я.М. Максимальный всплеск в сети и максимальный

объём сети[текст]/ Я.М. Ерусалшккий, H.H. Водолазов/Известия вузов. Северо-Кавказский регион. Ест. науки. -2010. - № 6. - С. 9-13. (Zbl 1224.94074)

9. Ерусалшккий, Я.М. Потоки в сетях с нестандартной достижимостью// Известия вузов. Северо-Кавказский регион. Ест. науки. — 2012.-№ 1.-С. 17-21.

10. Ерусалшккий, Я.М. О всплесках динамического потока и минимальных разрезах [текст] / Я.М. Ерусалшккий, А.Е. Куликовский/ Известия вузов. Северо-Кавказский регион. Ест. науки. - 2014. - № 4. - С.5-9.

11. Ерусалшккий, Я.М. Графы с ограничениями на достижимость и их

приложения к задачам оптимизации технологических процессов [электронный ресурсу/Современные проблемы науки и образования. - 2014. - № 6. - 7 с. URL: science-education.ru/120-15477. Режим доступа: свободный

12. Ерусалшккий, Я.М. Графы с затуханием на дугах и усилением в

вершинах и маршрутизация в информационных сетях[электронный

ресурс]//Инженерный вестник Дона. - 2015. - №1.

URL: ivdon.ru/ni/magazine/archive/n 1 v2015/2782. Режим доступа:

свободный

13. Ерусалшккий Я.М. Случайные блуждания по графу-решётке. Немар-

ковский случай [текст]//Фундаментальные исследования. -2015. — № 2. - С.5267-5275.

Публикации в зарубежных реферируемых изданиях:

14. Erusalimsky, I.M. Family of Grandy Functions for Oriented Graphs

[текст]// Turkish Journal of Mathematics. -1995. - v.19, №3. - P. 269273. (Zbl 0859.05071)

15. Erusalimskii, Ya. MBijoin points, bibridges, and biblocks of directed graphs [текст] /Ya. M. Erusalimskii, G. G. Svetlov/Cybernetics. Plénum Publishing Corp. - 1980. -Nol. - P. 41^14. (Zbl 0462.05034) статьи в спецвыпусках журналов из перечня ВАК РФ:

Хб.Еруссипшский, Я.М. Отображения конечных множеств и треугольник Паскаля [текст]// Известия вузов. Северо-Кавказский регион. Ест. науки. -2001. - Математическое моделирование. - С. 68-69.

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

18. Ерусалгшский, Я.М. Общий подход к нестандартной достижимости

на ориентированных графах [текст]/ Я.М. Ерусалгшский, В.А.Скороходов/ Известия вузов. Северо-Кавказский регион. Ест. науки. -2005. - Псевдодифференциальные уравнения и некоторые проблемы математической физики - С. 64-67.

Материалы всероссийских и международных конференций:

19.Ерусалгшский Я.М. Биномиальные коэффициенты в тождествах для натуральных чисел [текст]//Современные методы теории краевых задач: Материалы воронежской весенней математической школы «Понтрягинские чтения - XVII»/ - Воронеж: ОАО «Центральное Черноземное книжное издательство», 2006. - С.63-64.

20. Erusalimskiy Y.M. Binomial Coefficients in Equalities for Natural Num-

bers [текст]// International Congress of Mathematicians. - Madrid. -

2006. - Abstracts. - P.480.

21. Ерусалгшский Я.М. Динамические периодические графы [текст] /

Я.М. Ерусалгшский, М.В. Кузьминова// Математическое моделирование и биомеханика в современном университете: Труды III всероссийской школы-семинара/ Ростов н/Д: Из-во «Терра Принт»,

2007, - С.39-40.

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

23. Ерусалгшский, Я.М. NP-полнота задачи нахождения максимального

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

24. Ерусалимский, Я.М. Полиномиальные алгоритмы нахождения мак-

симального потока в сетях с некоторыми видами нестандартной достижимости [текст]/ H.H. Водолазов, Я.М. Ерусалимский // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения - XXII»/ Воронеж: Из-во ВГУ, 2011- С. 62-63.

25. Ерусалимский, Я.М. Пространственно-временные фракталы [текст]

//материалы IV международной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования»/Воронеж: Изд.-полигр. центр ВГУ, 2011. - С. 62-63.

26. Ерусалимский, Я.М. Достижимость на графах с зависимостью огра-

ничений от времени [текст]/Я.М. Ерусалимский В.А. Скороходов // материалы V международной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования»/ Воронеж: Изд.-полигр. центр ВГУ, 2012. - С. 111112.

27. Ерусалимский, Я.М. Уравнения математической физики на графах с

нестандартной достижимостью [текст]/ Я.М. Ерусалимский, В.А. Скороходов// Международная конференция «Современные методы прикладной математики, теории управления и компьютерных технологий», сборник трудов VI международной конференции/Воронеж: Изд.-полигр. центр ВГУ, 2013. - С. 96-98.

28. Ерусалимский, Я.М Задача о кратчайшем пути на графах с меняю-

щейся длительностью при условии случайных задержек на дугах/ Я.М. Ерусалимский, В.А. Скороходов [текст]//Современные методы теории краевых задач: материалы Весенней воронежской математической школы «Понтрягинские чтения ХХ1У»/Воронеж: 2013, - С. 79-80.

29. Ерусалимский, Я.М. Всплески динамических потоков в сетях [текст]//

Международная научная конференция «Соврем, методы и проблемы теории операторов и гармонического анализа и их приложения -III», Тезисы докладов, Изд-во СКНЦ ВШ, Ростов н/Д, 2013, - С.103-104.

30.Ерусалимский, Я.М., О всплесках динамического потока и минимальных разрезах [текст у Я.М. Ерусалимский, А.Е. Куликовский/ Современные методы теории краевых задач: материалы Весенней воронежской математической школы «Понтрягинские чтения XXV»/Воронеж: Изд.-полигр. центр ВГУ, 2014. - С. 64-65.

31. Ерусалимский, Я.М. О гармонических функциях на графах с нестан-

дартной достижимостью [текст]/Я.М. Ерусалимский, В.А. Скороходов/ Международная научная конференция «Современные методы и проблемы теории операторов и гармонического анализа и их приложения - III». Тезисы докладов/ Ростов н/Д: Изд-во СКНЦ ВШ, 2014.-С. 88-89

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

32. Erusalimskiy, I. On the Dynamic Flows in Networks [TeKCT]//Universal J.

of Communications and Network, 2014, v2, #6, - P. 101 - 105, DOI: 10.13189

33. Ерусалимский, Я.М. Графы с нестандартной достижимостью: задачи,

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

34. Ерусалимский, Я.М. Дискретная математика: теория, задачи, прило-

жения [текст]//М.: «Вузовская книга», 1998. - 280 с.

35. Ерусалимский, Я.М. Дискретная математика: теория, задачи, прило-

жения. - 10-е изд. перераб. и дополн. [текст] //М.: Вузовская книга, 2009, - 288 с.

36. Ерусалимский, Я.М. Прибыль от потоков с обратной связью в орсе-

тях с ограничениями на достижимость [текст У Ерусалимский Я.М., Скороходов В.А.Н Известия вузов. Северо-Кавказский регион. Ест. науки. Приложения. - 2003, №8. - С.3-8.

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

38. Ерусалимский, Я.М. Случайные процессы в сетях с биполярной маг-нитностью/Я.М. Ерусалимский, А.Г. Петросян//Известия вузов. Северо-Кавказский регион. Ест. науки. Приложения. - 2005, №11. -С.10-16.

39 .Ерусалимский, Я.М. Смешанная достижимость на частично-ориентированных графах [деп. рукопись]/Е.О. Басангова, Я.М. Ерусалимский// Деп. в ВИНИТИ, № 5892-82Б, Ростов н/Д: Ростовский госуниверситет, 1982. - 17 с. АО. Ерусалимский, Я.М. О функции Гранди графа [текст]// Деп. в ВИНИТИ, №1576-81, Ростов н/Д: Ростовский госуниверситет, 1981. - 5 с.

41. Ерусалимский, Я.М. Смешанная достижимость на частично-

ориентированных графах [деп. рукопись]/Басангова Е.О., Ерусалимский Я.М./ Вычислительные системы и алгоритмы, Ростов н/Д.: ИРУ, 83, - С. 135-140. (Zbl 0578.05029)

42.Ерусалимский, Я.М. Частично-ориентированные графы и различные виды смешанной достижимости [текст] / Е.О. Басангова, Я.М. Ерусалимский/ Алгебра и дискретная математика, Элиста.: 1985, - С.70-75.

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

44. Ерусалимский, Я.М. Смешанная достижимость на графах (общий подход). Эйлеровость графов со смешанной достижимостью [деп.

рукопись]// Деп. в ВИНИТИ, №2640-В88/ Ростов н/Д, Ростовский госуниверситет, 1988. - 11с.

45. Ерусалимский, Я.М. Пути с задержками в вершинах на орграфах

[текст]// Дискретные модели и структуры/ Элиста: КалмГУ, 1991. -С. 46-49.

46. Ерусалимский, Я.М. Поток на графах с ограничениями на достижи-

мость [текст]/ H.H. Водолазов, Я.М. Ерусалимский/ Труды научной школы И.Б.Симоненко/Ростов-на-Дону: Изд-во ЮФУ, 2010. - С. 4457.

47.Ерусалимский, Я.М. Основы дискретной математики. Матрицы графа. Алгоритмы анализа графов [текст]//Математика. Общий курс : учебник, 4-е изд., стер. /Б.М. Владимирский, А.Б. Горстко, Я.М. Ерусалимский/Спб.: Издательство «Лань», 2008.-960 е./ - С. 811855.

В материалах [4], [7],[8],[10],[21-24],[26-28], [30], [31], [33],[38], [39], [41],[46], опубликованных с соавторами, Я.М. Ерусалимскому принадлежат постановки задач, разработка общих методов построения разверток, общих схем алгоритмов, соавторам принадлежит их приложение к конкретным видам ограничений на достижимость, а также реализации алгоритмов. В работе [19] Ерусалимскому Я.М. принадлежат постановки задач, общие методы решения задач о кратчайших путях, случайных блужданиях и потоках в сетях с ограничениями на достижимость, о динамических периодических сетях и динамических графах.

Подписано в печать 13.07.2015 г. Формат 60x84 Vie. Усл. печ.л. 1,86.Уч.-изд.л. 1,56. Тираж 150 экз. Заказ № 4547.

Отпечатано в отделе полиграфической, корпоративной и сувенирной продукции Издательско-полиграфического комплекса КИБИ медиа ЦЕНТРА ЮФУ. 344090, г. Ростов-на-Дону. пр. Стачки, 200/1. тел. (863) 247-80-51.