Содержание к диссертации
Введение
Глава 1. Ориентированные графы с условиями магиитиости 14
1.1. Основные понятия и определения 14
1.2. Достижимость на графах с условиями магиитиости 1G
1.3. Сравнение сложности алгоритмов нахождения кратчайшего пути 32
1.4. Случайные процессы на орграфах с магнитной достижимостью 33
1.5. Туннельная проводимость твердокристаллической решетки . 44
1.6. Потоковая задача в сетях с магнитной достижимостью 46
Глава 2. Ориентированные графы с условиями вентильной достижимости 55
2.1. Достижимость на графах с условием вентильной достижимости 55
2.2. Случайные процессы на графах с условием вентильной достижимости 64
2.3. Потоки в сетях с вентильной достижимостью 69
Глава 3. Стационарное распределение на графах 73
3.1. Основные понятия и определения. 73
3.2. Устойчивость и стационарное распределение на графах 74
Глава 4. Ориентированные графы с условием механической достижимости 87
4.1. Достижимость на графах с условием механической достижимости 87
4.2. Случайные процессы на графах с механической достижимостью 90
4.3. Приложения условия механической достижимости 93
Глава 5. Задача о прибыли сети при заданной величине допустимого потока 95
5.1. Максимальная прибыль сети от прохождения по ней потока заданной величины 95
5.2. Случай сети с /с-источниками и т-стоками 97
5.3. Прибыль от потоков с обратной связью в орсетях с ограничениями па достижимость 99
5.4. Примеры назначения вероятностей для получения максимальной прибыли сети 105
Приложение 109
Литература 143
- Сравнение сложности алгоритмов нахождения кратчайшего пути
- Случайные процессы на графах с условием вентильной достижимости
- Устойчивость и стационарное распределение на графах
- Случайные процессы на графах с механической достижимостью
Введение к работе
"Существует несколько причин нарастания интереса к теории графов. Неоспорим тот факт, -что теория графом применяется м таких областях, как физика, химия, теория связи, проектирование ЭВМ, электроника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика".
(Харари Ф. Теория графов. Пер. с англ. М. Мир. 1973.)
Ориентированные графы оказались хорошей математической моделью широкого класса объектов и процессов. При этом, обычно на этом графе решаются задачи о достижимости (т.е. существует-ли путь из вершины в вершину? и если существует несколько путей, то какой из них кратчайший), задача о случайном блуждании частицы на орграфе с заданными на дугах вероятностями (Марковский процесс), а так же потоковая задача. Перечисленные задачи (в классической постановке, т.е. когда все дуги являются равноправными а пути допустимыми) хорошо изучены и являются широко применимыми в различных областях.
Приведем обзор наиболее существенных работ и результатов в них.
Так например в работах Басакера Р.Д, Саати Т.Л., Зыкова А.А., Крис-тофидеса Н., Оре О., Ерусалимского Я.М. (1], 6, 13, [14], [16] - [19], [24] -[26]) и др. рассматриваются задачи о достижимости и об ограниченной достижимости. В работах Замбицкого Д.К., Лозовану Д.Д., Форда Л.Р., Фал-керсона Д.Р., Свами М., Тхуласирамана К. ([12], [16] - [19], [22], [26]) и др. рассматриваются потоковые задачи в различных постановках, но во всех случаях без ограничения па достижимость по дугам выделенных подмножеств.
В настоящей работе фактически осуществляется уточнение самого самого понятия ориентированный граф. Суть уточнения состоит в том, что дуги графа не являются равноправными в формировании его путей. Такие графы мы называем орграфами с нестандартной достижимостью. Такое обобщение классического понятия позволяет расширить область применения графовых моделей и методов, в том числе к задачам маршрутизации в сетях с участками затухания и участками усиления сигнала, к нахождению кратчайших путей
выполиения технологических процессов, в которых имеются ограничения на
порядок (последовательность) выполнения некоторых операций к нахождению
вероятностей в задачах случайного блуждания, когда имеются переходы,
влияющие на свойства частицы.
Впервые вопрос о введении ограничения на прохождение по дугам выделенных подмножеств рассмотрен в работах Басаиговой Е. О., Ерусалимскогс Я. М. и Логвинова С. К). (2 - 5], [7, [8)). В работах (7 - 8) рассмотрено условие смешанной достижимости для орграфов, которое состоит в том, что множество дуг графа состоит из объединения непересекающихся подмножеств U — Щи Un и допустимыми путями являются только тс, которые пе содержат участков из двух подряд идущих дуг множества Щ. При этом, рассмотрены задача о достижимости и комбинированная задача о пути мак-симальной допустимости и минимальной длины (28]). В работах (2 - 5) рассмотрено условие смешанной достижимости для частично - ориентированных графов, которое состоит в том, что на графе кроме дуг существуют неориентированные звенья и ставится условие, что по звеньям запрещается проходить более одного раза подряд. При этом, рассмотрена задача о достижимости и потоковая задача на частично-ориентированных графах со смешанной достижимостью.
Данная работа посвящена разработке общего подхода для решения задач о достижимости и о случайном блуждании частицы по вершинам графа, а так же потоковой задачи на ориентированных графах с различными ограничениями на достижимость. Для этого изучены ориентированные графы с ограничением на прохождение по дугам выделенных подмножеств. Определено несколько видов ограничений на достижимость: магнитная достижимость, вентильная достижимость и механическая достижимость. Разработан универсальный для каждого из рассматриваемых условий подход (который состоит в том. что строится вспомогательный граф, количество вершин которого больше, чем у исходного, но на котором все дуги являются равноправными, а пути допустимыми).Это позволяет свести задачу о достижимости на исходно? графе с ограничением к задаче о достижимости на вспомогательном графе без ограничения. Данный подход исользован при решении задач не только
o достижимости, но и о случайном блуждании частицы по вершинам графа, а так же при решении потоковой задачи дли сети с ограничением на множество допустимых путей.
В первой главе рассмотрено понятие магнитной достижимости на ориентированном графе, у которого множество дуг U состоит из объединения непересекающихся непустых множеств U = UMUUH (множество UM называем множеством магнитных дуг, а /# - множеством немагнитных дуг) и задано одно из условий магнитной достижимости. Введеній три вида условий магнитной достижимости, определяющие множество допустимых путей:
1. Условие магнитной достижимости с накоплением неубывающей магмит-ности, при котором с каждым отрезком [1,г]дг пути ц связана величина накопленной магнитности пути А,,(г), равная количеству магнитных дуг пути її на этом отрезке, тогда если к г- тому шагу путь от своего начала накопил магнитность большую либо равную к (А/4(г) к) и среди дуг выходящих из концевой вершины г- той дуги хотя бы одна магнитная, то следующая (г + 1-я) дуга обязана быть дугой из множества UM,
2. Условие магнитной достижимости с накоплением-исчезапием магнитности, при котором с каждым отрезком [1, г]дг пути /І связана величина накопленной магнитности пути
АДО = max I Г ІМІ) П UM\ - к ]Г \fi(j) П UH\ \ ,
\j=m j=m J
тогда если к і- тому шагу путь от своего начала накопил магнитность большую либо равную к (А/4(г) к) и среди дуг выходящих из ко/щепой вершины г- той дуги хотя бы одна магнитная, то следующая (г + 1- я) дуга обязана быть дугой из множества UM- (Вторая сумма означает, что прохождение по дугам множества UJJ уменьшает накопленную магнитность),
3. Условие магнитной достижимости с возрастанием-убыванием магнитности, при котором с каждым отрезком [1, г]дг пути ц связана величина
накопленной магнитпости пути
Ъ(ЬР) = , тах с { zl М-?) п 1 zJ IA O(J) n UH\ } ,
тогда если к m- тому шагу путь от своего начала накопил магниччіость большую либо равную к ( max { min {г)ц{1,і) + л,,.(і + l,?n)}} /г) и
1=1,...,т i=l,...,m
среди дуг выходящих из концевой веі)шипьі пг- той дуги хотя бы одна магнитная, то следующая (т + 1-я) дуга обязана быть дугой из множества UM Ясно, что магнитная достижимость не обладает транзитивным свойством, т.е. если вершина /магнитно достижима из х, а вершина z магнитно достижима из у, то из этого не следует магнитная достижимость вершины z из вершины X.
Кратчайшие пути, в этом случае, не обладают и экстремальным свойством, состоящим в том, что любой отрезок кратчайшего пути является кратчайшим путем между своими граничными вершинами, а именно на нем основан алгоритм Э. Дейкстры нахождения кратчайших путей (см., например, [1, [13], [14})- Это означает, что для разработки алгоритма нахождения кратчайших путей на графе с такой достижимостью необходим другой подход.
Описан подход, сводящий магнитную достижимость (любого из перечисленных видов) вершин исходного графа G к.достижимости вершин на вспомогательном графе G , приведены правила построения вспомогательных графов для каждого условия магнитпости. Показано, что задача о достижимости вершин исходного графа G с условием магнитной достижимости сводится к задаче о достижимости на вспомогательном графе G :
Теорема 1.2.1 Любому пути р! па вспомогательном графе G соответствует магнитно-накопительный путь fi па исходном и вершина у магнитно-достижима при условии неубывающей магнитпости из вершины х на графе G тогда и только тогда, когда на G достижима из х, по крайней мере, одна из вершин множества Vy = {у, у1, ...,у }.
Проведено сравнение сложности алгоритмов нахождения кратчайшего пути из некоторой вершины в другую с использованием построения вспомогательного графа и без его использования, Показано, что задача о достижи мости на графе с условием магнитной достижимости без построения вспомогательного графа может быть решена только полным перебором путей графа, а значит алгоритм нахождения кратчайшего пути с построением вспомогательного графа более быстрый, чем алгоритм без построения вспомогательного графа.
Кроме этого, в. главе 1 рассмотрены задача о случайном блуждании частицы, а так же потоковая задача на графах с магнитной достижимостью. Показано, что описанный подход позволяет сводить процесс случайного блуждания частицы на графе G с магнитной достижимостью, который не является Марковским к Марковскому процессу на вспомогательном графе G .
В качестве приложения задачи случайного блуждания частицы на графе с магнитной достижимостью рассмотрена бомбардировка частицами кристаллической решетки, состоящей из двух слоев: магнитно- накопительного и туннельного. Показано, что вероятность прохождения частицы через решетку, в этой ситуации, больше, чем вероятность прохождения частицы через решетку без условия магнитности.
Рассмотрение задачи о максимальном потоке в сетях с нестандартной достижимостью потребовало обобщения самого понятия орсети и допустимого потока в ней. В работе дано определение орсети со связанными дугами, когда на графе имеются выделенные попарно непересекающиеся подмножества дуг. Для каждого из таких множеств определена не пропускная способность каждой из дуг,-а только суммарная пропускная способность дуг этого подмножества. Ясно, что это потребовало корректировки и определения допустимого потока в такой сети. Предложен алгоритм нахождения максимального потока в сетях со связанными дугами.
Показано, что потоковая задача на исходном графе G с магнитной достижимостью сводится к потоковой задаче в сети со связанными дугами, которой является вспомогательный грае}).
Во второй главе рассмотрено понятие вентильной достижимости на ориентированном графе, у которого множество дуг U состоит из объединения попарно непересекающихся непустых множеств U = UQ U • • • U Uk и задано одно из условий вентильной достижимости. Введены три вида условий вен 1. тильной достижимости, определяющие множество допустимых нугой на графе: Условие вептилыю-пакопителыюй достижимости, при котором если среди т дуг вентильного пути содержалась хотя бы одна дуга множества, Uj, то следующая дуга пути обязана быть дугой множества UQU ...\JU.+\, или, что то же самое, прохождение но дуге множества Uj "открываст"для прохождения дуги множества f/y+i,
2. Условие вентильной достижимости с возрастанием -убыванием доступа на пути, при котором множество вершин X так же состоит из объединения попарно непересекающихся множеств X = XQ U ... U Xj.- С каждым отрезком пути її связана характеристика ф {ъ) = j, где j такое, что (Р2° f °/-000 Є Xj тогда если фц(г) = j, то следующая дуга пути обязана быть дугой множества Щ U ... U Uj.
3. Условие вентильной достижимости с возрастанием-убыванием энергии на пути, при котором если среди т дуг вентильного пути /І содержалась хотя бы одна дуга множества Uj, то следующая дуга пути обязана быть
г
дугой множества W — \J Uj, где СДга) - величина накопленной
j=o 7 0 0 ) энергии (j -того типа) пути /г, a cr (j) - максимально возможное количество энергии (j -того типа).
Описан подход, сводящий вентильную достижимость (любого из перечисленных видов) вершин исходного графа G к достижимости вершин па вспомогательном графе G", приведены правила построения вспомогательных графов для каждого условия вентильной достижимости. Показано, что задача о достижимости вершин исходного графа G с условием вентильной достижимости сводится к задаче о достижимости на вспомогательном графе
а.
Кроме этого, так же, как и в главе 1 рассмотрены задача случайного блуждания частицы, а так же потоковая задача на графах с вентильной достижимостью. Показано, что описанный подход позволяет сводить задачу процесс случайного блуждания частицы на графе G с вентильной.достижимостью, который не является Марковским к Марковскому процессу на
вспомогательном графе G .
Показано, что потоковая задача па исходном графе G с вентильной достижимостью сводится к потоковой задаче в сети со связанными дугами, которой является вспомогательный граф.
Третья глава посвящена изучению устойчивых и неустойчивых циклов, и стационарного распределения па графах с нестандартной достижимостью.
Введены понятия устойчивых, нолуусгойчивых и неустойчивых режимов (циклов) графа. Приведены алгоритмы нахождения устойчивых и неустойчивых циклов. Показано, что на графе с ограничением на достижимость устойчивыми циклами могут стать неустойчивые циклы па этом же графе без ограничения па достижимость, а устойчивые циклы (в этом случае) могут исчезнуть.
Так же, введено понятие периодического устойчивого цикла: устойчивый режим будем называть периодическим, если при возведении матрицы переходных вероятностей в некоторую степень, все строки, соответствующие этому режиму вычисленной матрицы получаются некоторой перестановкой этих же строк исходной матрицы. Такая ситуация возникает лишь в том случае, когда устойчивый режим является компонентой сильной связности и из каждой вершины есть только одна дуга, ведущая в вершину данного режима с вероятностью перехода, по ней равной единице. Показано, что для цепи Маркова, в которой присутствует хотя бы один периодический режим не существует стационарного распределения.
Так же, известно, что для конечной цепи Маркова с дискретным временем существует единственное стационарное распределение тогда и только тогда, когда цепь является сжимающей. В диссертационной работе в терминах теории графов сформулировано и доказано следующее утверждение:
Теорема 3.2.2 Для того, чтобы конечная цепь Маркова G являлась сжимающей необходимо и достаточно, чтобы выполнялись следующие условия:
1. G не содержит периодических устойчивых режимов,
2. На G существует единственная изолированная компонента сильной связности Н,
3. D компоненте сильной связности Н существуют но крайней мере дна цикла щ и г/2, длины которых (\r]i\ и \г]2\) - взаимно простые числа.
Показано, что если без ограничения на достижимость для цепи Маркова существовало стационарное распределение, то при ограничении на достижимость стационарного распределения для этой же цепи может не существовать.
»
В четвертой главе рассмотрено понятие механической достижимости на ориентированном графе, которая состоит в том, что задано некоторое отображение g : U — Z ("паклои"дуги и), которое определяет разбиение множества дуг U на попарно непересекающиеся подмножества U+ = g-\Z+\{0}), U- = P_1(Z\Z+) и UH = g-l({0}) (т.е. U = U+ U UH U U-) и задано условие механической достижимости, состоящее в том, что с каждым отрезком [г,і]лг пути д связана числовая характеристика tyi(«,j) = ®4i{h3 - 1) +g(l (j)), при этом, ЗДг,г) = тт{0,#(д(г))}. Тогда если flfl(l1i)+g(/j,(i + l)) 0, из концевой вершины г-той дуги выходят дуги только множества U+ или г-той дуга была из множества U+, то следу іонная дуга пути должна быть из U+ (если такие выходят из текущей вершины).
Описан подход, сводящий механическую достижимость вершин исходного графа G к достижимости вершин на вспомогательном графе С, приведено правило построения соответствующего вспомогательного графа. Показано, что задача о достижимости вершин исходного графа G с условием механической достижимости сводится к задаче о достижимости на вспомогательном графе G .
Кроме этого, так же, как и в главе 1 показано, что процесс блуждания частицы па графе G с механической достижимостью сводится к Марковскому процессу на вспомогательном графе G .
В качестве приложения условия механической достижимости рассмотрены следующие задачи:
1. Некоторая функция задана своими значениями в узлах сетки произвольного вида (например прямоугольной). Требуется определить области локального минимума этой функции. Показано, что эта задача сводится к задаче поиска устойчивых циклов.
. На графе G(X, U, /) заданы отображения д : U - Z и М : X — {0,1} такие, что д - задает "наклон"дуги, а М - определяет области магнит-ности таким образом, что если М{х) = 1, то 0 (х) С UM V# Є X.
Рассмотрен случайный процесс блуждания некоторого объекта (произвольной природы) по вершинам графа G. При этом, объект может двигаться только но"4 возможным путям с соблюдением условия неубывающей магнитности. Требуется для произвольного начального положения объекта определить возможные точки его остановки (т.е. прекращения движения) или возможные точки его циклического движения (устойчивые циклы).
Пятая глава посвящена задачам о прибыли в сети. Рассмотрены задачи:
г
1. О максимальной прибыли в сети от прохождения по пей потока заданной величины, которая заключается в том, что для каждой дуги указаны пропускная способность, вероятность перехода по данной дуге (которая играет роль распределения потока) и величина прибыли от прохождения но пей единичного потока. Необходимо при заданной величине потока назначить вероятности перехода по дугам сети таким образом, чтобы прибыль от потока была максимальной.
2. О максимальной прибыли от потоков с обратной связью в сетях с ограничениями на достижимость, которая состоит в том, что пропускная способность каждой дуги задана как в прямом направлении, так и в обратном. В результате возникает пара потоков, которая образует поток с обратной связью. Ясно, что потоковая задача такого вида имеет смысл только в орсетях с ограничением на достижимость. Рассмотрена задача максимизации прибыли от потоков такого вида при условии связи и ограничениях на достижимость по дугам выделенных подмножеств.
В приложении приведены листинги программ для решения потоковой задачи и задачи о случайном блуждании па орграфах с магнитной достижимостью. Программы реализованы на языке С + + в среде ВигШегЗ.О.
Работа выполнена на кафедре алгебры и дискретной математики Рос -товского государственного университета. Особую благодарность автор выражает своему научному руководителю профессору Я. М. Ерусалимскому за постоянную заботу и помощь при работе над диссертацией.
Сравнение сложности алгоритмов нахождения кратчайшего пути
Рассмотрим путь 7 в виде последовательности вершин. Он не является магнитно-накопительным путем порядка (2,2) с возрастанием -убыванием магнитности, так как но удовлетворяет условию (1.2.9) (?77(6) = 2 и щ $. UM)- И действительно, на вспомогательном графе ему не соответствует ни одного пути.
Путь является магнитно-накопительным путем по- рядка (2,2) с возрастанием -убыванием магиитиости. На вспомогательном . графе ему соответствует путь Оцепим сложность алгоритмов нахождения кратчайшего пути для ор-графов с условием магнитной достижимости. В качестве условия достижимости будем рассматривать условие неубывающей магиитиости (для остальных условий магнитной достижимости все рассуждения аналогичны).
При наличии условия магнитной достижимости теряется свойство тран зитивности пути, т.е. не всегда выполняется следующее условие: если существует путь из вершины х в вершину у и существует путь из вер шины у в вершину 2, то существует путь из х в z через у. Действительно, эта ситуация показана в примере 1.2.2: существует магнитно накопительный путь из вершины 4 в вершину 2 (4 - 1 — 2)и существует магнитно накопительный путь из вершити 2 в 3 (2 — 3), но не существует магнитно накопительного пути из вершины 4 в вершину 3. 2. При наличии условия магнитной достижимости теряется свойство экс тремальности пути, т.е. отрезки кратчайших путей не обязательно яв ляются кратчайшими путями. Действительно, рассмотрим графа с условием неубывающей магиитиости при к = 2 на рис.1.14, дуги {щ,... ,щ} такие, что Кратчайшим путем из вершины 1 в вершину 6 является путь /л = {u2, гц, щ (для простоты длины 7, однако отрезок этого пути Ml = {щ щ} (1 — 2 =Ф 5) не является кратчайшим путем из вершины 1 в вершину 5. 3. Условие магнитной достижимости приводит к рассмотрению мультигра фов, поскольку кратные дуги могут быть различных типов. Если в клас -33-сической постановке щ и решении задачи о достижимости среди кратных дуг можно было выбрать одну меньшего веса, а остальные удалить, то при наличии условия магнитной достижимости такого сделать нельзя.
Исходя из этого, стандартные алгоритмы, такие;, как алгоритм Дейкетры или алгоритм Флойда, не могут быть применены из-за того, что они пред-полагают наличие свойств транзитивности и экстремальности пути графа. Более того, из фактов 1-3 следует, что задача нахождения кратчайшего пути на графе с условием магнитной достижимости без построения вспомогательного графа может быть решена только полным перебором путей графа. В этом случае сложность алгоритмов нахождения кратчайшего пути будет равна f(n) — О [ (iimx{deg+(x)})n ), где п = \Х\. Сложность алгоритма
Дейкетры для вспомогательного графа равна /i(n) = тО(ті), где m = [/, сложность алгоритма перестроения исходного графа во вспомогательный равна /2( 1) = 0(п2), значит сложность алгоритма с построением вспомогательного графа равна сумме
Многие реальные системы можно характеризовать, выделяя различные состояния, в которых они могут находиться, и задавая их реакции па поступление произвольных входных воздействий при нахождении систем в любом заданном состоянии. Как правило, реакция системы проявляется в форме перехода из одного состояния в другое и формирования соответствующего -выходного сигнала. Формализация данной идеи приводит к понятию математической машины (15). Определение 1.4.1. Машшш - есть математическая системм, которая состоит из: конечного .множества S = s\,...,sn элементов, называемых состоя-пиями; конечного .MHODicecmea X = х\, ...,хп элементов, пазываеммх входами; конечного множества Y = у\, ...,уп элементов, называемых выходами; функции перехода Т , которая отображает S х X на S; функции выхода Q, которая отображіает S xY на S. Если s Є S и х Є X, то s = T (s, х) интерпретируется как следующее состояние, в которое попадает машина из текущего состояния s при воздействии входного сигнала х. Аналогично, у = Q,(s,x) есть выходной сигнал машины, находящейся в состоянии s при воздействии входного сигнала х. Множества X и Y называются, соответственно, входным и выходным алфавитом. Машины, соответствующие данному определению, можно классифицировать по нескольким признакам. Во-первых, они являются детерминированными, так как их выходной сигнал и следующее состояние полностью определяется входным сигналом и текущим состоянием. Далее, такие машины являются последовательными, так как и дискретные моменты времени 1\,І2- Н-, а не непрерывно. Они являются полными, т.е. каждая комбинация состояния и входного сигнала имеет смысл и дает известный выходной сигнал и новое состояние. Они не имеют памяти в том смысле, что текущий выход и следующее состояние не зависят от прошлых входов, состояний и выходов. Наконец, они стационарны втом смысле, что функция переходов Т" и функция выхода Q не зависят от рассматриваемого момента времени.
Случайные процессы на графах с условием вентильной достижимости
Ясно, что магнитная достижимость не обладает транзитивным свойством, т.е. если вершина /магнитно достижима из х, а вершина z магнитно достижима из у, то из этого не следует магнитная достижимость вершины z из вершины X.
Кратчайшие пути, в этом случае, не обладают и экстремальным свойством, состоящим в том, что любой отрезок кратчайшего пути является кратчайшим путем между своими граничными вершинами, а именно на нем основан алгоритм Э. Дейкстры нахождения кратчайших путей (см., например, [1, [13], [14})- Это означает, что для разработки алгоритма нахождения кратчайших путей на графе с такой достижимостью необходим другой подход.
Описан подход, сводящий магнитную достижимость (любого из перечисленных видов) вершин исходного графа G к.достижимости вершин на вспомогательном графе G , приведены правила построения вспомогательных графов для каждого условия магнитпости. Показано, что задача о достижимости вершин исходного графа G с условием магнитной достижимости сводится к задаче о достижимости на вспомогательном графе G :
Теорема 1.2.1 Любому пути р! па вспомогательном графе G соответствует магнитно-накопительный путь fi па исходном и вершина у магнитно-достижима при условии неубывающей магнитпости из вершины х на графе G тогда и только тогда, когда на G достижима из х, по крайней мере, одна из вершин множества Vy = {у, у1, ...,у }.
Проведено сравнение сложности алгоритмов нахождения кратчайшего пути из некоторой вершины в другую с использованием построения вспомогательного графа и без его использования, Показано, что задача о достижимости на графе с условием магнитной достижимости без построения вспомогательного графа может быть решена только полным перебором путей графа, а значит алгоритм нахождения кратчайшего пути с построением вспомогательного графа более быстрый, чем алгоритм без построения вспомогательного графа.
Кроме этого, в. главе 1 рассмотрены задача о случайном блуждании частицы, а так же потоковая задача на графах с магнитной достижимостью. Показано, что описанный подход позволяет сводить процесс случайного блуждания частицы на графе G с магнитной достижимостью, который не является Марковским к Марковскому процессу на вспомогательном графе.
В качестве приложения задачи случайного блуждания частицы на графе с магнитной достижимостью рассмотрена бомбардировка частицами кристаллической решетки, состоящей из двух слоев: магнитно- накопительного и туннельного. Показано, что вероятность прохождения частицы через решетку, в этой ситуации, больше, чем вероятность прохождения частицы через решетку без условия магнитности.
Рассмотрение задачи о максимальном потоке в сетях с нестандартной достижимостью потребовало обобщения самого понятия орсети и допустимого потока в ней. В работе дано определение орсети со связанными дугами, когда на графе имеются выделенные попарно непересекающиеся подмножества дуг. Для каждого из таких множеств определена не пропускная способность каждой из дуг,-а только суммарная пропускная способность дуг этого подмножества. Ясно, что это потребовало корректировки и определения допустимого потока в такой сети. Предложен алгоритм нахождения максимального потока в сетях со связанными дугами.
Показано, что потоковая задача на исходном графе G с магнитной достижимостью сводится к потоковой задаче в сети со связанными дугами, которой является вспомогательный грае}). Во второй главе рассмотрено понятие вентильной достижимости на ориентированном графе, у которого множество дуг U состоит из объединения попарно непересекающихся непустых множеств и задано одно из условий вентильной достижимости. Введены три вида условий вентильной достижимости, определяющие множество допустимых нугой на графе: 1. Условие вептилыю-пакопителыюй достижимости, при котором если среди т дуг вентильного пути содержалась хотя бы одна дуга множества, Uj, то следующая дуга пути обязана быть дугой множества UQU ...\JU.+\, или, что то же самое, прохождение но дуге множества Uj "открываст"для прохождения дуги множества f/y+i, 2. Условие вентильной достижимости с возрастанием -убыванием доступа на пути, при котором множество вершин X так же состоит из объединения попарно непересекающихся множеств X = XQ U ... U Xj.- С каждым отрезком пути її связана характеристика ф {ъ) = j, где j такое, что (Р2 f /-000 Є Xj тогда если фц(г) = j, то следующая дуга пути обязана быть дугой множества Щ U ... U Uj. 3. Условие вентильной достижимости с возрастанием-убыванием энергии на пути, при котором если среди т дуг вентильного пути /І содержалась хотя бы одна дуга множества Uj, то следующая дуга пути обязана быть дугой множества - величина накопленной энергии (j -того типа) пути /г, a cr (j) - максимально возможное количество энергии (j -того типа). Описан подход, сводящий вентильную достижимость (любого из перечисленных видов) вершин исходного графа G к достижимости вершин па вспомогательном графе G", приведены правила построения вспомогательных графов для каждого условия вентильной достижимости. Показано, что задача о достижимости вершин исходного графа G с условием вентильной достижимости сводится к задаче о достижимости на вспомогательном графе.
Устойчивость и стационарное распределение на графах
Показано, что если без ограничения на достижимость для цепи Маркова существовало стационарное распределение, то при ограничении на достижимость стационарного распределения для этой же цепи может не существовать.
В четвертой главе рассмотрено понятие механической достижимости на ориентированном графе, которая состоит в том, что задано некоторое отображение g : U — Z ("паклои"дуги и), которое определяет разбиение множества дуг U на попарно непересекающиеся подмножества U+ = g-\Z+\{0}), U- = P_1(Z\Z+) и UH = g-l({0}) (т.е. U = U+ U UH U U-) и задано условие механической достижимости, состоящее в том, что с каждым отрезком [г,і]лг пути д связана числовая характеристика tyi(«,j) = 4i{h3 - 1) +g(l (j)), при этом, ЗДг,г) = тт{0,#(д(г))}. Тогда если flfl(l1i)+g(/j,(i + l)) 0, из концевой вершины г-той дуги выходят дуги только множества U+ или г-той дуга была из множества U+, то следу іонная дуга пути должна быть из U+ (если такие выходят из текущей вершины).
Описан подход, сводящий механическую достижимость вершин исходного графа G к достижимости вершин на вспомогательном графе С, приведено правило построения соответствующего вспомогательного графа. Показано, что задача о достижимости вершин исходного графа G с условием механической достижимости сводится к задаче о достижимости на вспомогательном графе G .
Кроме этого, так же, как и в главе 1 показано, что процесс блуждания частицы па графе G с механической достижимостью сводится к Марковскому процессу на вспомогательном графе G . В качестве приложения условия механической достижимости рассмотрены следующие задачи: 1. Некоторая функция задана своими значениями в узлах сетки произвольного вида (например прямоугольной). Требуется определить области локального минимума этой функции. Показано, что эта задача сводится к задаче поиска устойчивых циклов. 2. На графе G(X, U, /) заданы отображения д : U - Z и М : X — {0,1} такие, что д - задает "наклон"дуги, а М - определяет области магнит-ности таким образом, что если М{х) = 1, то 0 (х) С UM V# Є X. Рассмотрен случайный процесс блуждания некоторого объекта (произвольной природы) по вершинам графа G. При этом, объект может двигаться только но"4 возможным путям с соблюдением условия неубывающей магнитности. Требуется для произвольного начального положения объекта определить возможные точки его остановки (т.е. прекращения движения) или возможные точки его циклического движения (устойчивые циклы). Пятая глава посвящена задачам о прибыли в сети. Рассмотрены задачи: 1. О максимальной прибыли в сети от прохождения по пей потока заданной величины, которая заключается в том, что для каждой дуги указаны пропускная способность, вероятность перехода по данной дуге (которая играет роль распределения потока) и величина прибыли от прохождения но пей единичного потока. Необходимо при заданной величине потока назначить вероятности перехода по дугам сети таким образом, чтобы прибыль от потока была максимальной. 2. О максимальной прибыли от потоков с обратной связью в сетях с ограничениями на достижимость, которая состоит в том, что пропускная способность каждой дуги задана как в прямом направлении, так и в обратном. В результате возникает пара потоков, которая образует поток с обратной связью. Ясно, что потоковая задача такого вида имеет смысл только в орсетях с ограничением на достижимость. Рассмотрена задача максимизации прибыли от потоков такого вида при условии связи и ограничениях на достижимость по дугам выделенных подмножеств. В приложении приведены листинги программ для решения потоковой задачи и задачи о случайном блуждании па орграфах с магнитной достижимостью. Программы реализованы на языке С + + в среде ВигШегЗ.О. Работа выполнена на кафедре алгебры и дискретной математики Ростовского государственного университета. Особую благодарность автор выражает своему научному руководителю профессору Я. М. Ерусалимскому за постоянную заботу и помощь при работе над диссертацией.
Случайные процессы на графах с механической достижимостью
Многие реальные системы можно характеризовать, выделяя различные состояния, в которых они могут находиться, и задавая их реакции па поступление произвольных входных воздействий при нахождении систем в любом заданном состоянии. Как правило, реакция системы проявляется в форме перехода из одного состояния в другое и формирования соответствующего выходного сигнала. Формализация данной идеи приводит к понятию математической машины (15).
Определение 1.4.1. Машшш - есть математическая системм, которая состоит из: конечного .множества S = s\,...,sn элементов, называемых состоя-пиями; конечного .MHODicecmea X = х\, ...,хп элементов, пазываеммх входами; конечного множества Y = у\, ...,уп элементов, называемых выходами; функции перехода Т , которая отображает S х X на S; функции выхода Q, которая отображіает S xY на S. Если s Є S и х Є X, то s = T (s, х) интерпретируется как следующее состояние, в которое попадает машина из текущего состояния s при воздействии входного сигнала х. Аналогично, у = Q,(s,x) есть выходной сигнал машины, находящейся в состоянии s при воздействии входного сигнала х. Множества X и Y называются, соответственно, входным и выходным алфавитом. Машины, соответствующие данному определению, можно классифицировать по нескольким признакам. Во-первых, они являются детерминированными, так как их выходной сигнал и следующее состояние полностью определяется входным сигналом и текущим состоянием. Далее, такие машины являются последовательными, так как и дискретные моменты времени 1\,І2- Н-, а не непрерывно. Они являются полными, т.е. каждая комбинация состояния и входного сигнала имеет смысл и дает известный выходной сигнал и новое состояние. Они не имеют памяти в том смысле, что текущий выход и следующее состояние не зависят от прошлых входов, состояний и выходов. Наконец, они стационарны втом смысле, что функция переходов Т" и функция выхода Q не зависят от рассматриваемого момента времени. Иногда машину удобно изображать ориентированным графом, вершины которого соответствуют состояниям, а дуги характеризуют X,Y,T и Q. Идея Марковской цепи в некотором смысле является вероятностным аналогом абстрактных детерминированных машин. Приведем некоторые необходимые определения (15, 23). Определение 1.4.2. Набор = {()/ Є Т} случайных величии (), определенных на одном, и том оісе вероятностном, пространстве (Q,S,T), называется случайной функцией. Если параметр t играет роль времени, т.е. Т С R, то такую случайную величину называют случайным процессом. Определение 1.4.3. Процесс = {(01 } У которого множество Т не более чем счетно, называют процессом, с дискретным, временем. Как правило, в этом, случае множество Т совпадает с мнооїсеством целых чисел, или частью этого множества. Рассмотрим последовательность {„} случайных величии, которая представляет собой случайный процесс с дискретным временем. Предположим, что каждая случайная величина п принимает значения из множества Е — {0,1,2,...}, и рассмотрим следующий простой вид зависимости случайной величины из последовательности {in} - распределение случайной величины п может зависеть от значения, которое принимает случайная величина n_i, и не зависит от значений, принимаемых предшествующими случайными величинами. Образно ічшоря, при фиксированном настоящем, будущее не зависит от прошлого. Формально это означает следующее: Определение 1.4.4. Последовательность {„} случайных величин, удовлетворяющих (1.4-1) называется цепью Маркова с дискретным, временем,. Такая цепь называется однородной (относительно времени), ec.nuMi,j Є Е вероятность P{n+i = j\n = г } — Pij tie зависит о времени. Эволюция однородной цепи Маркова {„} определяется: а) начальным распределением случайной величины і, т.е. набором чисел, б) матрицей {pij} переходных вероятностей за один шаг. При этом множество Е называется множеством состояний (фазовым пространством) цепи, а вероятность - вероятностью перехода из состояния г Є Е в состояние j Є Е за п шагов. В частности, р ц = p.jj. Из (1.4.1) следует, что выполняется соотношение:
