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

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

Содержание
Содержание.
Введение.

Глава 1. Ориентированные графы с условиями магнитности .

1.1. Основные понятия и определения

1.2. Достижимость на графах с условиями магнитности

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

1.4. Случайные процессы на орграфах с магнитной достижимостью

1.5. Туннельная проводимость твердокристаллической решетки

1.6. Потоковая задача в сетях с магнитной достижимостью

Глава 2. Ориентированные графы с условиями вентильной достижимости .

2.1. Достижимость па графах с условием вентильной достижимости
2.2. Случайные процессы на графах с условием вентильной дости
жимости
2.3. Потоки в сетях с вентильной достижимостью.
Глава 3. Стационарное распределение на графах.
3.1. Основные понятия и определения 7
3.2. Устойчивость и стационарное распределение на графах.
Глава 4. Ориентированные графы с условием механической достижимости .
4.1. Достижимость на графах с условием механической достижимости
4.2. Случайные процессы на графах с механической достижимостью
4.3. Приложения условия механической достижимости .
Глава 5. Задача о прибыли сети при заданной величине допустимого
потока.
5.1. Максимальная прибыль сети от прохождения но ней потока заданной величины
5.2. Случай сети с кисточникам и и тстоками
5.3. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость
5.4. Примеры назначения вероятностей для получения максималь
ной прибыли сети.
Приложение
Литература


Так же, введено понятие периодического устойчивого цикла: устойчивый режим будем называть периодическим, если при возведении матрицы переходных вероятностей в некоторую степень, все строки, соответствующие этому режиму вычисленной матрицы получаются некоторой перестановкой этих же; строк исходной матрицы. Такая ситуация возникает лишь в том случае, когда устойчивый режим является компонентой сильной связности и из каждой вершины есть только одна дуга, ведущая в вершину данного режима с вероятностью перехода, по пей равной единице. Показано, что для цепи Маркова, в которой присутствует хотя бы один периодический режим не существует стационарного распределения. Так же, известно, что для конечной цепи Мар кони с дискретным иремепем существует единственное стационарное распределение тогда и то/п>ко тогда, когда цепь является сжимающей. Теорема 3. В компоненте сильной сиялюсти Н сущестуют по крайней мере дни цикля и ? Показано, ч то если без ограничения па достижимость для цени Маркова существовало стационарное распределение, то при ограничении на достижимость стационарного расп]>еделопия для этой же цени может по существовать. В четвертой главе рассмотрено понятие механической достижимости па ориентированном графе, которая состоит в том, что задано некоторое отображен ж; g : U —> Z ("наклон "дуги и), которое определяет разбиение множества дуг U на попарно непересекающиеся подмножества U+ = p-4Z+{0}), и- = <гЧZz+) и и„ = <г‘({0}) (т. N пути р. ЦДЛ = %(hi - 1) + при этом, Ц<(г,г) = min{0,$(//(*))}. Тогда если Г2^(1,г)+^(/л(г + 1)) < 0, из концевой вершины і-той дуги выходят дуги только множества U+ или г-той дуга была из множества U+, 'го следующая дуга пути должна быть из U+ (если такие выходят из текущей вершины). Описан подход, сводящий механическую достижимость вершин исходного графа G к достижимости вершин на вспомогательном графе G приведено правило построения соответствующего вспомогательного графа. Показано, что задача о достижимости вершин исходного графа G с условием механической достижимости сводится к задаче о достижимости на вспомогательном графе G'. Кроме этого, так же, как и в главе 1 показано, что процесс блуждания частицы па графе G с механической достижимостью сводится к Марковскому процессу на вспомогательном графе G'. Некоторая функция задана своими значениями в узлах сетки произвольного вида (например прямоугольной). Требуется определить области локального минимума этой функции. Показано, что эта задача сводится к задаче поиска устойчивых циклов. На графе С(Х, ? У Z и М : Л” -э {0,1} такие, что д - задаст "наклон "дуги, а М - ом оделяет области магиит-ности таким образом, что если М(х) = 1, то Э~(х) С V# 6 X. Рассмотрен случайный процесс блуждании некоторого объекта (произвольной природы) но вершинам графа С. При этом, объект может двигаться ТОЛЬКО 1КГ возможным путям с соблюдением условия неубывающей магнитности. Требуется дли произвольного начального положения объекта определить возможные точки его остановки (т. С1Ч) циклическош движения (устойчивые циклы). Пятая глава посвящена задачам о прибыли в сети. О максимальной прибыли в сети от прохождения по ней потока заданной величины, которая заключается в том, что для каждой дуги указаны пропускная способность, вероятность перехода по данной дуге (которая играет роль распределения потока) и величина прибыли от прохождения но пей единичного потока. Необходимо при заданной величине потока назначить вероятности перехода но дугам сети таким образом, чтобы прибыль от потока была максимальной. О максимальной прибыли от потоков с обратной связью в сетях с ограничениями на достижимость, которая состоит в том, что пропускная способность каждой дуги задана как в прямом направлении, так и в обратном. В результате возникает пара потоков, которая образует ноток с обратной связью. Ясно, что потоковая задача такого вида имеет смысл только в орсетях с ограничением на достижимость. Рассмотрена задача максимизации прибыли от потоков такого вида при условии связи и ограничениях на достижимость по дугам выделенных подмножеств. В приложении приведены листинги программ для решения потоковой задачи и задачи о случайном блуждании на орграфах с магнитной достижимостью. Программы реализованы на языке С-Ь + в среде ВиИЛсг'З.