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

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

Введение

Глава 1. Динамические графы

Определение и свойства динамических графов

Построение вспомогательного графа

Математическая модель потока в периодической динамической сети

Задача о кратчайшем пути

Задача о случайных блужданиях

Глава 2. Ограниченные магнитные достижимости

Определение и свойства ограниченных магнитных достижимостей

Построение вспомогательного графа

Потоки в сетях с ограниченными магнитными достижимостями

Кратчайшие пути на графах с ограниченными магнитными достижимостями
Задача о случайных блужданиях
Глава 3. Ограниченные монотонные достижимости
Определение и свойства ограниченных монотонных достижимостей
Построение вспомогательного графа
Задачи о максимальном потоке, кратчайших путях и случайных блужданиях
Графовые модели в логистике
Заключение
Приложение
Литература


Глава 1. Глава 2. Глава 3. Чаще всего рассматриваются задачи о достижимости т. Кристофидесу Н. Басакеру Р. Д., Харари Ф. Бержу К. Дейкстре Э. Флойду Р. Замбицкому Д. К., Оре О. Саати Т. Ерусалимскому Я. Фалкерсону Д. Р., Форду Л. Р.2, , , , , . В отличие от классического подхода, Басанговой Е. О. и Ерусалимским Я. В работах Ерусалимского Я. М., Басанговой Е. О., Логвинова С. В.Л. Петросяна А. Так, Ерусалимским Я. Е.О. В работах Скороходова В. Другой вид достижимости вентильнонакопительная. II С0 и их и. IIк. Су1 у 1,2,. Петросяном А. Алгоритм построения такого графа зависит от вида вводимых ораничений. Г, называемое периодом. Теорема 1. Пусть СЛГ,,, т динамический граф, х,у,геХ. Теорема 1. И, x0, если з г . ГЛу АГ,если Зтг к Г тТ. СХиГ. Введены определения периодической динамической сети и динамического потока. Определение 1. Vиеи. Определение 1. Теорема 1. V 1,2,. ТтпТ. П ,. Теорема 1. Пусть выполняются условия теоремы 1. Тогда Уи 1,2,. Теорема 1. СтХ,и,,т,1. У, соединяющий вершины у И у2. Теорема 1.