Нестандартная достижимость на ориентированных графах и сетях

• Автор: Ерусалимский, Яков Михайлович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2012
• Место защиты: Ярославль
• Количество страниц: 144 с.

ОГЛАВЛЕНИЕ
Введение

Глава I. Нестандартная достижимость различных видов.

Кратчайшие пути на графах с нестандартной

достижимостью

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

§ 1.2. Смешанная достижимость на орграфах

§ 1.3. Магнитная достижимость на орграфах

§ 1.4. Барьерная достижимость на графах

Заключение к главе I

Г лава II. Случайные блуждания на графах с нестандартной
достижимостью
§2.1. Случайные блуждания на графах со смешанной
достижимостью
§2.2. Случайные блуждания на графах с монотонной
достижимостью
§ 2.3. Случайные блуждания на графах с вентильной
достижимостью
Заключение к главе II
Глава III. Потоки в сетях с нестандартной достижимостью
§ 3.1. Примеры потоков в сетях с нестандартной
достижимостью
§ 3.2. Основные определения теории потоков в сетях с
нестандартной достижимостью
§ 3.3. Семейство сетей с барьерной достижимостью
Заключение к главе III
Глава IV. Динамические потоки в сетях
§4.1. Основные определения
§4.2. Ограничения на величину динамического потока

§ 4.3. Временная развертка графа
§ 4.4. Всплеск динамического потока, ёмкость сети
Заключение к главе IV
Глава V Динамические графы и сети
§5.1. Динамические графы. Определение и примеры
§ 5.2. Временная развертка динамического графа
§5.3. Периодические динамические графы
§ 5.4. Построение развёртки периодического динамического
графа
§ 5.5. О потоках в динамических сетях
Заключение к главе V
Г лава VI. Функции на графах
§6.1. Семейство функций Гранди ориентированного графа
§ 6.2. Семейство функций Гранди неориентированного графа
Заключение к главе VI
Библиографический список использованной литературы
Приложение 1. Некоторые сведения о конечных множествах в

Настоящая работа посвящена ориентированным графам с нестандартной достижимостью и некоторым смежным вопросам дискретной математики. Ключевых слов в этом предложении несколько. Во-первых, «ориентированным» - автор не разделяет как-то высказанного суждения о том, что по-настоящему математическими объектами являются неориентированные графы. Действительно, если к графам подходить как к объектам, изучаемым методами алгебраической топологии, то этот так и есть. Но в приложениях чаще встречаются и более естественны для использования именно ориентированные графы. Автор настоящей работы считает, что класс ориентированных графов более широк и интересен. В большинстве случаев неориентированный граф можно считать симметрическим ориентированным графом. Вторым ключевым словом или фразой в первом предложении является «граф с нестандартной достижимостью». Именно эти объекты мы и будем рассматривать в нашей работе.
В прикладных задачах, как правило, изучается не сам граф, а процессы на нем. Большинство из них связано с перемещениями по графу по его путям. В классическом определении путь это последовательность дуг графа, в которой каждая следующая дуга начинается в вершине, в которой заканчивается предыдущая дуга пути. Соединимость одной вершины путём, ведущим из другой вершины, называется достижимостью одной вершины из другой. Три основных задачи прикладной теории графов и не только прикладной, а точнее сказать, алгоритмической теории графов связаны с достижимостью. Это сама задача о достижимости и нахождении кратчайшего пути, задача о случайных блужданиях по вершинам графа и задачи о потоках в сетях, поскольку поток можно считать перемещением (транспортировкой) вещества (материи, товаров, жидкости, энергии и т.п.) из источника в сток по путям, ведущим из источника в сток.
Когда мы говорим о графе с нестандартной достижимость, то это означает, что допустимыми к рассмотрению на нём являются не все пути, а пути, удовлетворяющие определенному условию (это условие называется типом

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

р'(и) =
I]р(и) ие.и+ (х)
(2.3)
Ясно, что для графа рис. 2.2. //((1,2))= //((1,8')) = //((1,7)) = -^,
р%5\)) = -р%',1)) = р%',2))Л.
Описанное в главе I построение развёртки (вспомогательного графа) и указанный выше перенос на неё переходных вероятностей с исходного графа делает справедливой следующую теорему.