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

• Автор: Водолазов, Николай Николаевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Ростов-на-Дону
• Количество страниц: 142 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
Глава 1. ОБЗОР ЛИТЕРАТУРЫ. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
1.1. Задача поиска максимального потока на графе
1.2. Обзор задач о динамическом потоке
1.3. Основные подходы к решению задач на графах с нестандартной достижимостью
Глава 2. ПОТОК НА ГРАФАХ С НЕСТАНДАРТНОЙ
ДОСТИЖИМОСТЬЮ
2.1. Определение потока в сети с ограничениями на достижимость.
2.2. Поток в сети с барьерными ограничениями на достижимость
2.3. Обобщение алгоритма поиска максимального потока на графах со связанными дугами
2.4. ИР-полнота задачи нахождения максимального целочисленного потока с ограничениями на достижимость
Глава 3. ДИНАМИЧЕСКИЕ ПОТОКИ В СЕТЯХ
3.1. Основные определения
3.2. Ограничение на величину динамического потока
3.3. Нахождение максимального всплеска на графе
3.4. Нахождение потока, имеющего максимальный объем
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ИСПОЛЬЗУЕМОЙ
ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ. Программа «Моделирование потоков с ограничениями на достижимость». Прилагается на компакт-диске.

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

достижима из Х°, по крайней мере, одна из вершин множества Vy =
На основании этой теоремы строятся решения ряда задач для графов с вентильной достижимостью, например, решение задачи о кратчайшем пути.
Для примера рассмотрим граф G , изображенный на рис. 13. Пусть k = 2, U0 = {(а,Ь),(а,с)} (дуги из U0 помечены цифрой 0), £/,={(&,с)},
(дуга из U] помечена цифрой 1), U 2~ {(b, d), (с, d)} (дуги из U 2 помечены цифрой 2). Вспомогательный граф изображен на рис. 14.

Рис. 13. Граф G

Рис. 14. Граф G'
При отсутствии условия вентильной достижимости на графе С существует три пути из вершины а в вершину с1: {(а,Ь),(Ь,с/)}
рис. 14 видно, что с условием вентильной достижимости допустимым остается только путь