Математические модели и алгоритмы на графах с нестандартной достижимостью. Динамические графы

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

Содержание

Содержание
Введение
Глава 1. Нестандартные достижимости на ориентированных графах
1.1. Ограниченные магнитные достижимости

1.2. Ограниченные монотонные достижимости
1.3. Динамические графы
Глава 2. Построение вспомогательного графа как метод сведения задач на графах с нестандартной достижимостью к задачам на обычных орграфах
2.1. Построение вспомогательного графа для случая ограниченных магнитных достижимостей
2.2. Построение вспомогательного графа для случая ограниченных монотонных достижимостей
2.3. Построение вспомогательного графа для периодических динамических графов
Глава 3. Задача о максимальном потоке на периодических динамических графах и на графах с ограниченными магнитными и монотонными достижимостями
3.1. Постановка задачи. Основные определения
3.2. Потоки в сетях с ограниченными магнитными достижимостями
3.3. Потоки в сетях с ограниченными монотонными достижимостями
3.4. Максимальный поток в периодической динамической сети

Глава 4. Задача о кратчайшем пути на периодических динамических графах и на графах с ограниченными магнитными и монотонными достижимостями
4.1. Кратчайшие пути на графах с ограниченными магнитными достижимостями
4.2. Кратчайшие пути на периодических динамических графах
Глава 5. Случайные блуждания на периодических динамических графах и на графах с ограниченными магнитными и монотонными достижимостями
5.1 Задача о случайных блужданиях на графах с ограниченными магнитными достижимостями
5.2 Задача о случайных блужданиях на периодических динамических графах
5.3 Графовые модели в логистике
Заключение
Приложение
Литература

Введение
Теория графов предоставляет эффективные средства формализации задач из самых различных областей: экономики, физики, химии, плановопроизводственной практики, управления производством, сетевого и календарного планирования, информационных систем, и многих других. Одним из таких средств является ориентированный граф. Существует большое количество задач, решаемых на орграфах. Чаще всего рассматриваются задачи о достижимости (т.е. о существовании пути, связывающем две заданные вершины), о нахождении путей, обладающих какой-либо экстремальной характеристикой (например, кратчайший, или наиболее надежный путь), о случайных блужданиях, потоковая задача. Все они хорошо изучены и разработаны эффективные алгоритмы их решения. При этом предполагается, что все пути на графе являются допустимыми, т.е. не накладывается никаких ограничений на достижимость. Наиболее известные работы в этой области принадлежат Кристофидесу Н., Басакеру Р.Д., Харари Ф., Бержу К., Дейкстре Э., Флойду Р., Замбицкому Д.К., Оре О., Саати Т., Ерусалимскому Я.М., Фалкерсону Д.Р., Форду Л.Р.([2, 10-19, 23, 34, 42, 45-46]).
В отличие от классического подхода, Басанговой Е.О. и Ерусалимским Я.М. было введено понятие ориентированных графов с нестандартной достижимостью, т.е. орграфов, в которых на допустимые пути накладываются какие-либо ограничения ([3-6, 11]). В обычном
ориентированном графе, для того чтобы одна вершина была достижима из другой, необходимо существование пути, связывающего две эти вершины. В случае же орграфов с нестандартной достижимостью требуется, кроме того, чтобы этот путь удовлетворял некоторому условию (ограничению). Понятно, что в этом случае классические алгоритмы решения задач на графах непосредственно неприменимы.
В работах Ерусалимского Я.М., Басанговой Е.О., Логвинова С.Ю., Скороходова В.А., Петросяна А.Г. ([3-6, 11-18, 35-37, 39-41]) описаны

Путь /,о]: [і,и]ы —> 11 на графе От(Х,11,/, г) является допустимым, если выполняется условие: V/ є [і,н]м т(, ](/), і + ґ0-і)= 1.
Определение 1.3.6. Цепью длины п на периодическом динамическом графе Ог(Х,и,/,т) с началом в момент времени /0 є -/V называется отображение 77[,о]: [і,и]м -> и, такое, что одна вершина ребра 7[го](0 инцидентна ребру 7[,о](г-і), а другая - (і + і), і є [2,«-1]ы,, причем ребро и, і є [і,и]м проходится в момент времени /0 + г -1. Число /0 є А называется начальным моментом времени для цепи Цепь
: [1,и]ы -> и на графе СГ(Х,1!,/, т) является допустимой, если V/ є [і, «]ы ребро 7?[,о](0 є и активна в момент времени ґ0 + і -1.
Пример 1.3.3. Рассмотрим граф С5(Х,и,/,т), изображенный на рис.1.3.3 (рядом с дугой указан период активности, п = 1,2

ио=0, ит = {щ,и2,и3,и4}
/(н,)=(1,2) /(и2)=(1,3) /(«з) = (2,4)/(н4)=(3,4) т{их,і)~ 1 V/ є [і + 5н,3 + 5н] г(н2ц) = 1 V/є [8 + 5и,11 + 5н]
т{иг,і) = 1 Уґє[2 + 5и,4 + 5л] г(м4,г) = 1 V/ є [5 + 5и,7 + 5п]
п = 1,2,