автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математические модели и алгоритмы на графах с нестандартной достижимостью

На правах рукописи

Скороходов Владимир Александрович

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ НАГРАФАХС НЕСТАНДАРТНОЙДОСТИЖИМОСТЬЮ

05.13.18 -Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Ростов-на-Дону 2004

Работа выполнена на кафедре алгебры и дискретной математики механико-математического факультета Ростовского госуниверситета

Научный руководитель

кандидат физико-математических наук, профессор Ерусалимский Яков Михайлович

Официальные оппоненты

заслуженный деятель науки доктор физико-математических наук, профессор Покорный Юлий Витальевич

доктор технических наук,

профессор Белявский Григорий Исакович

Ведущая организация

НИИ прикладной математики и автоматизации Кабардино-Балкарского научного центра РАН

заседании диссертационного совета К 212.208.04 по физико-математическим и техническим наукам в Ростовском Государственном Университете по адресу: 344090, г. Ростов-на-Дону, пр. Стачки 200/1, корпус 2, ЮГИНФО РГУ, к. 206.

С диссертацией можно ознакомиться в Зональной научной библиотеке РГУ по адресу: г. Ростов-на Дону, ул. Пушкинская, 148.

Зашита диссертации состоится 2004 г. в 1100 часов на

Автореферат разослан

2004г.

Ученый секретарь

диссертационного совета

Муратова Г.В.

1 Общая характеристика работы

"Существует несколько причин нарастания интереса к теории графов. Неоспорим тот факт, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электроника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика".

(Харари Ф. Теория графов. Пер. с англ. М. Мир. 1973.)

Актуальность темы. Ориентированные графы оказались хорошей математической моделью широкого класса объектов и процессов, например, они применяются для решения таких задач, как маршрутизация (навигация) в информационных сетях, сетевое планирование и многих других. При этом, обычно на графе решаются задачи о достижимости (т.е. существует-ли путь из вершины в вершину? и если существует несколько путей, то какой из них кратчайший), задача о случайном блуждании частицы на орграфе с заданными на дугах вероятностями (Марковский процесс), а так же потоковая задача. Перечисленные задачи (в классической постановке, т.е. когда все дуги являются равноправными, а все пути допустимыми) хорошо изучены и являются широко применимыми в различных областях (см. работы Зыкова А.А., Оре О., Свами М., Тхуласирамана К., Форда Л.Р., Фалкерсона Д.Р., Харари Ф., Яблонского СВ. и др.).

В настоящей работе фактически осуществляется уточнение самого понятия ориентированный граф. Суть уточнения состоит в том, что дуги графа не являются равноправными в формировании его путей. Такие графы мы называем орграфами с нестандартной достижимостью. Такое обобщение классического понятия позволяет расширить область применения графовых моделей и методов, в том числе к задачам маршрутизации в сетях с участками затухания и участками усиления сигнала, к нахождению кратчайших путей выполнения технологических процессов, в которых имеются ограничения на порядок (последовательность) выполнения некоторых операций или их совместимость, к нахождению вероятностей в задачах случайного блуждания частицы, когда

Впервые вопрос о введении ограничения на прохождение по дугам выделенных подмножеств рассмотрен в работах Басанговой Е. О., Еруса-лимского Я. М. и Логвинова С. Ю. В работах Ерусалимского Я. М. и Логвинова С. Ю. рассмотрено условие смешанной достижимости для ориентированных и неориентированных графов, которое состоит в том, что множество дуг графа состоит из объединения непересекающихся подмножеств и — иьии„ и допустимыми путями являются только те, которые не содержат участков из двух подряд идущих дуг множества Щ. При этом, рассмотрена задача о достижимости и комбинированная задача о пути максимальной допустимости и минимальной длины. В работах Басанговой Е. О. и Еруса-лимского Я. М. рассмотрено условие смешанной достижимости для частично-ориентированных графов, которое состоит в том, что на графе кроме дуг существуют неориентированные звенья и ставится условие, что по звеньям запрещается проходить более одного раза подряд. При этом, рассмотрена задача о достижимости и потоковая задача на частично-ориентированных графах с такой достижимостью.

Цель работы состоит в разработке общего подхода к решению задач о достижимости и о случайном блуждании, а так же потоковой задачи на ориентированных графах с нестандартной достижимостью, что приводит к уточнению самого понятия ориентированный граф и расширению возможности использования этой математической модели.

В работе рассмотрены и решены следующие задачи:

1. Определены и исследованы новые виды достижимости на орграфах.

2. Разработаны алгоритмы для решения задач о достижимости и о случайном блуждании, а так же потоковой задачи на графах с рассмотренными ограничениями на достижимость.

3. Рассмотрен новый класс задач о потоках с обратной связью в ориентированных сетях и о максимизации прибыли от потоков с обратной связью.

Методы диссертационного исследования основываются на использовании аппарата теории графов, теории вероятностей, теории случайных процессов и теории чисел.

Научная новизна диссертационной работы состоит в следующих результатах, полученных автором:

1. Определены и изучены три вида условий ограничения на достижимость: магнитная достижимость, вентильная достижимость и механическая достижимость.

2. Разработан общий подход для решения задач на ориентированных графах с различными ограничениями на достижимость, состоящий в построении вспомогательного графа большего размера, но на котором все пути соответствуют допустимым путям на исходном графе.

3. Рассмотрены орсети, у которых пропускная способность каждой дуга задана как в прямом направлении, так и в противоположном. В результате возникает пара потоков, которые образуют поток с обратной связью.

Практическая ценность работы состоит в том, что полученные результаты могут быть использованы при исследовании новых дискретных математических моделей, имеющих в своей основе графы с ограничениями на достижимость, а так же при разработке спецкурсов по теории графов.

Апробация работы.

1. Результаты диссертации докладывались и обсуждались на международной конференции "Математическое моделирование и вычислительный эксперимент в механике и физике" (Ростов-на-Дону, 2001 г,)

2. По результатам работы сделан доклад на научном семинаре по финансовой математике и стохастическим процессам в университете города Халл (Великобритания).

3. По тематике исследования была подана заявка в конкурсный центр Минобразования РФ в области естественных наук, заявка получила положительную оценку и поддержана грантом Минобразования РФ по фундаментальным исследованиям в области естественных наук (грант Е02-1.0-231)

Публикации. По материалам диссертации опубликовано 5 работ [1]-[5]. Работы [1]-[2] выполнены совместно с научным руководителем. В этих работах Ерусалимскому Я.М. принадлежит постановка задачи и определение общих методов, проведение подробных доказательств и разработка алгоритмов принадлежит автору диссертации.

Структура и объем работы. Диссертация состоит из введения, пяти глав, приложения и списка литературы. Объем диссертационной работы составляет 145 страниц, в работе содержатся 65 рисунков, библиографический список содержит 30 наименований.

2 Содержание работы

Во введении обоснована актуальность темы исследования, проведен обзор публикаций по рассматриваемой теме, сформулированы цели работы и дана краткая аннотация всех глав диссертации.

В первой главе рассмотрено понятие магнитной достижимости на ориентированном графе, у которого множество дуг и состоит из объединения непересекающихся непустых множеств и ~ им01/н (множество 1!м называем множеством магнитных дуг, а - множеством немагнитных дуг) и задано одно из условий магнитной достижимости. Введены три вида условий магнитной достижимости, определяющие множество допустимых путей: -

1. Условие магнитной достижимости с накоплением неубывающей магнит-ности, при котором с каждым отрезком пути связана величина накопленной магнитности пути равная количеству магнитных дуг пути /х на этом отрезке, тогда если к »- тому шагу путь от своего начала накопил магнитность большую либо равную к (АДг) > к) и среди дуг выходящих из концевой вершины той дуги хотя бы одна магнитная, то следующая (» + 1-я) дуга обязана быть дугой из множества 11м,

2. Условие магнитной достижимости с накоплением-исчезанием магнит-ности, при котором с каждым отрезком пути связана величина накопленной магнитности пути

тогда если к тому шагу путь от своего начала накопил магнитность

вершины той дуги хотя бы одна магнитная, то следующая

дуга обязана быть дугой из множества и м- (Вторая сумма означает, что

большую либо равную и среди дуг выходящих из концевой

прохождение по дугам множества 1}ц уменьшает накопленную магнит -ность),

3. Условие магнитной достижимости с возрастанием-убыванием магнит-ности, при котором с каждым отрезком [1,г]лг пути /х связана величина накопленной магнитности пути

тогда если к т- тому шагу путь от своего начала накопил магнитность большую либо равную к ( шах { min {^(М) + f]n(i + l,m)}} > к) и

i=lr..,m i—l.....m

среди дуг выходящих из концевой вершины т- той дуги хотя бы одна магнитная, то следующая (т+ 1-я) дуга обязана быть дугой из множества

Ясно, что магнитная достижимость не обладает транзитивным свойством, т.е. если вершина у магнитно достижима из х, а вершина z магнитно достижима из у, то из этого не следует магнитная достижимость вершины из вершины

Кратчайшие пути, в этом случае, не обладают и экстремальным свойством, состоящим в том, что любой отрезок кратчайшего пути является кратчайшим путем между своими граничными вершинами, а именно на нем основан алгоритм Э. Дейкстры нахождения кратчайших путей. Это означает, что для разработки алгоритма нахождения кратчайших путей на графе с такой достижимостью необходим другой подход.

Описан подход, сводящий магнитную достижимость (любого из перечисленных видов) вершин исходного графа G к достижимости вершин на вспомогательном графе G', приведены правила построения вспомогательных графов для каждого условия магнитности. Показано, что задача о достижимости вершин исходного графа G с условием магнитной достижимости сводится к задаче о достижимости на вспомогательном графе G':

Теорема 1.2.1 Любому пути /л' на вспомогательном графе (соответствует магнитно-накопительный путь на исходном и вершина у магнитно-достижима при условии неубывающей магнитности из вершины х на графе G тогда и только тогда, когда на G' достижима из!, по крайней мере, одна

из вершин множества Уу =

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

Кроме этого, в главе 1 рассмотрены задача о случайном блуждании частицы, а так же потоковая задача на графах с магнитной достижимостью. Показано, что описанный подход позволяет сводить процесс случайного блуждания частицы на графе О с магнитной достижимостью, который не является Марковским к Марковскому процессу на вспомогательном графе С.

В качестве приложения задачи случайного блуждания частицы на графе с магнитной достижимостью рассмотрена бомбардировка частицами кристаллической решетки, состоящей из двух слоев: магнитно- накопительного и туннельного. Показано, что вероятность прохождения частицы через решетку, в этой ситуации, больше, чем вероятность прохождения частицы через решетку без условия магнитности.

Рассмотрение задачи о максимальном потоке в сетях с нестандартной достижимостью потребовало обобщения самого понятия орсети и допустимого потока в ней. В работе дано определение орсети со связанными дугами, когда на графе имеются выделенные попарно непересекающиеся подмножества дуг. Для каждого из таких множеств определена не пропускная способность каждой из дуг, а только суммарная пропускная способность дуг этого подмножества. Ясно, что это потребовало корректировки и определения допустимого потока в такой сети. Предложен алгоритм нахождения максимального потока в сетях со связанными дугами.

Показано, что потоковая задача на исходном графе О с магнитной достижимостью сводится к потоковой задаче в сети со связанными дугами, которой является вспомогательный граф.

Во второй главе рассмотрено понятие вентильной достижимости на ориентированном графе, у которого множество дуг и состоит из объединения попарно непересекающихся непустых множеств и задано

одно из условий вентильной достижимости. Введены три вида условий вентильной достижимости, определяющие множество допустимых путей на графе:

1. Условие вентильно-накопительной достижимости, при котором если среди т дуг вентильного пути содержалась хотя бы одна дуга множества 1/}, то следующая дуга пути обязана быть дугой множества или, что то же самое, прохождение по дуге множества "открывает"для прохождения дуги множества

2. Условие вентильной достижимости с возрастанием -убыванием доступа на пути, при котором множество вершин X так же состоит из объединения попарно непересекающихся множеств X = Хо и ... и XС каждым отрезком пути ц связана характеристика ») = где ] такое, что

тогда если то следующая дуга пути обязана

быть дугой множества

3. Условие вентильной достижимости с возрастанием-убыванием энергии на пути, при котором если среди т дуг вентильного пути содержалась хотя бы одна дуга множества то следующая дуга пути обязана быть дугой множества - величина накопленной

энергии (,; -того типа) пути (х, а ст*^') - максимально возможное количество энергии -того типа).

Описан подход, сводящий вентильную достижимость (любого из перечисленных видов) вершин исходного графа О к достижимости вершин на вспомогательном графе приведены правила построения вспомогательных графов для каждого условия вентильной достижимости. Показано, что задача о достижимости вершин исходного графа О с условием вентильной достижимости сводится к задаче о достижимости на вспомогательном графе

С.

Кроме этого, так же, как и в главе 1 рассмотрены задача случайного

блуждания частицы, а так же потоковая задача на графах с вентильной достижимостью. Показано, что описанный подход позволяет сводить задачу процесс случайного блуждания частицы на графе О с вентильной достижимостью, который не является Марковским к Марковскому процессу на вспомогательном графе

Показано, что потоковая задача на исходном графе О с вентильной достижимостью сводится к потоковой задаче в сети со связанными дугами, которой является вспомогательный граф.

Третья глава посвящена изучению устойчивых и неустойчивых циклов, и стационарного распределения на графах с нестандартной достижимостью.

Введены понятия устойчивых, полуустойчивых и неустойчивых режимов (циклов) графа. Приведены алгоритмы нахождения устойчивых и неустойчивых циклов. Показано, что на графе с ограничением на достижимость устойчивыми циклами могут стать неустойчивые циклы на этом же графе без ограничения на достижимость, а устойчивые циклы (в этом случае) могут исчезнуть.

Так же, введено понятие периодического устойчивого цикла: устойчивый режим будем называть периодическим, если при возведении матрицы переходных вероятностей в некоторую степень, все строки, соответствующие этому режиму вычисленной матрицы получаются некоторой перестановкой этих же строк исходной матрицы. Такая ситуация возникает лишь в том случае, когда устойчивый режим является компонентой сильной связности и из каждой вершины есть только одна дуга, ведущая в вершину данного режима с вероятностью перехода, по ней равной единице. Показано, что для цепи Маркова, в которой присутствует хотя бы один периодический режим не существует стационарного распределения.

Так же, известно, что для конечной цепи Маркова с дискретным временем существует единственное стационарноераспределение тогда и только тогда, когда цепь является сжимающей, В диссертационной работе в терминах теории графов сформулировано и доказано следующее утверждение:

Теорема 3.2.2 Для того, чтобы конечная цепь Маркова О являлась сжимающей необходимо и достаточно, чтобы выполнялись следующие усло-

вия:

1. G не содержит периодическихустойчивыхрежимов,

2. На О существует единственная изолированная компонента сильной связности Н,

3. В компоненте сильной связности Н существуют по крайней мере два цикла щ И »72, длины кот о^яЫчХ) - взаимно простые числа.

Показано, что если без ограничения на достижимость для цепи Маркова существовало стационарное распределение, то при ограничении на достижимость стационарного распределения для этой же цепи может не существовать.

В четвертой главе рассмотрено понятие механической достижимости на ориентированном графе, которая состоит в том, что задано некоторое отображение ("наклон"дуги и), которое определяет разбиение

множества дуг и на попарно непересекающиеся подмножества и

1/+ и С/я и Ш) и задано условие механической достижимости, состоящее в том, что с каждым отрезком пути связана числовая характеристика = ЦЛм ~ +5(/х0'))| при этом, Пр(г,г) = ппп{О,0(^(г))}. Тогда из концевой вершины дуги выходят дуги только множества дуга была из множества то следующая

дуга пути должна быть из (если такие выходят из текущей вершины).

Описан подход, сводящий механическую достижимость вершин исходного графа О к достижимости вершин на вспомогательном графе С, приведено правило построения соответствующего вспомогательного графа. Показано, что задача о достижимости вершин исходного графа О с условием механической достижимости сводится к задаче о достижимости на вспомогательном графе

Кроме этого, так же, как и в главе 1 показано, что процесс блуждания частицы на графе О с механической достижимостью сводится к Марковскому процессу на вспомогательном графе

В качестве приложения условия механической достижимости рассмотрены следующие задачи:

1. Некоторая функция задана своими значениями в узлах сетки произвольного вида (например прямоугольной). Требуется определить области локального минимума этой функции. Показано, что эта задача сводится к задаче поиска устойчивых циклов.

2. На графе /) заданы отображения J:{/-^ZиЛÍ:X-^ {ОД} такие, что д - задает "наклон"дуги, а М - определяет области магнит-ности таким образом, что если

Рассмотрен случайный процесс блуждания некоторого объекта (произвольной природы) по вершинам графа О. При этом, объект может двигаться только по возможным путям с соблюдением условия неубывающей магнитности. Требуется для произвольного начального положения объекта определить возможные точки его остановки (т.е. прекращения движения) или возможные точки его циклического движения (устойчивые циклы).

Пятая глава посвящена задачам о прибыли в сети. Рассмотрены задачи:

1. О максимальной прибыли в сети от прохождения по ней потока заданной величины, которая заключается в том, что для каждой дуги указаны пропускная способность, вероятность перехода по данной дуге (которая играет роль распределения потока) и величина прибыли от прохождения по ней единичного потока. Необходимо при заданной величине потока назначить вероятности перехода по дугам сети таким образом, чтобы прибыль от потока была максимальной.

2. О максимальной прибыли от потоков с обратной связью в сетях с ограничениями на достижимость, которая состоит в том, что пропускная способность каждой дуги задана как в прямом направлении, так и в обратном. В результате возникает пара потоков, которая образует поток с обратной связью. Ясно, что потоковая задача такого вида имеет смысл только в орсетях с ограничением на достижимость. Рассмотрена задача максимизации прибыли от потоков такого вида при условии связи и ограничениях на достижимость по дугам выделенных подмножеств.

В приложении приведены листинги программ для решения потоковой

задачи и задачи о случайного блуждании на орграфах с магнитной достижимостью. Программы реализованы на языке С + + в среде БшШвгЗ.О.

3 К защите представлены следующие результаты

1. Введены и изучены три вида условий ограничения достижимости на графах: магнитная достижимость, вентильная достижимость и механическая достижимость.

2. Разработан общий подход для решения различных задач на ориентированных графах с ограничениями на достижимость, состоящий в построении вспомогательного графа большего размера, но на котором все пути соответствуют допустимым путям на исходном графе.

3. Разработаны алгоритмы построения вспомогательных графов для всех видов достижимости, позволяющие решать задачи о достижимости и о случайных блужданиях в таких графах.

4. Модернизирован алгоритм Форда-Фалкерсона нахождения максимального потока для всех видов достижимости.

5. Показано, что при ограничении на прохождение по дугам выделенных множеств неустойчивые режимы могут стать устойчивыми, устойчивые режимы - исчезнуть, а так же,что если без ограничения на достижимость для цепи Маркова существовало стационарное распределение, то при ограничении на достижимость стационарного распределения для этой же цепи может не существовать.

6. Решена задача максимизации прибыли от потоков с обратной связью в орсетях с ограничениями на достижимость по дугам выделенных множеств.

4 Список работ, опубликованных по теме диссертации

1. Ерусалимский Я.М., Скороходов В.А. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях.// Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2003, №2, -с. 3-5.

2. Ерусалимский Я.М., Скороходов В.А. Потоки в сетях со связанными дугами.// Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2003, №8 , -с. 3-8.

3. Ерусалимский Я.М., Скороходов В.А. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость.// Известия ВУЗов. Северо-Кавказский регион. Естественные науки: Приложение. 2003, №8, -с. 9-12.

4. Скороходов В.А. Случайные блуждания и потоки в сетях с магнитной достижимостью.//в сб. Модели и дискретные структуры. Элиста, 2002. - с. 93-100.

5. Скороходов В .А. Графы с магнитной достижимостью. Марковские процессы и потоки в сетях.//Деп в ВИНИТИ., 2003, №410-В2003.

Издательство ООО «ЦВВР». Лицензия ЛР № 65-36 от 05.08 99 г. Подл, в печать 22.07.04 г. За>. №511. Тир. 100 эи. Печ. лист. 1,0. Усл. дал. 1,0. Типография: Издательско-полиграфический комплекс « Биос» РГУ. 344091, г. Ростов-на-Дону, ул. Зорге, 28/2, корп. 5 «В», тел. 929-516,659-532. Лицензия на полиграфическую деятельность №65-125 от 09.02.98 г.

р 16033

Содержание.

Введение

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

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

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

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

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

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

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

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

2.1. Достижимость на графах с условием вентильной достижимости

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

2.3. Потоки в сетях с вентильной достижимостью.

Глава 3. Стационарное распределение на графах.

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

3.2. Устойчивость и стационарное распределение на графах.

Глава 4. Ориентированные графы с условием механической достижимости

4.1. Достижимость на графах с условием механической достижимости

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

Существует несколько причин нарастания интереса к теории графов. Неоспорим тот факт, что теория графой применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электроника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика".

Харари Ф. Теория графов. Пер. с англ. М. Мир. 1973.)

Ориентированные графы оказались хорошей математической моделью широкого класса объектов и процессов. При этом, обычно на этом графе решаются задачи о достижимости (т.е. существует-ли путь из вершины в вершину? и если существует несколько путей, то какой из них кратчайший), задача о случайном блуждании частицы на орграфе с заданными па дугах вероятностями (Марковский процесс), а так же потоковая задача. Перечисленные задачи (в классической постановке, т.е. когда, все дуги являются равноправными а пути допустимыми) хорошо изучены и являются широко применимыми в различных областях.

Приведем обзор наиболее существенных работ и результатов в них.

Так например в работах Басакера Р.Д, Саати Т.Л., Зыкова A.A., Крис-тофидеса H., Ope О., Ерусалимского Я.М. (|1], |6|, |13|, [14], [16] - [19], [24] -[2G]) и др. рассматриваются задачи о достижимости и об ограниченной достижимости. В работах Замбицкого Д.К., Лозовану Д.Д., Форда Л.Р., Фал-керсона Д.Р., Свами М., Тхуласирамана К. ([12], [16] - [19], [22], [26]) и др. рассматриваются потоковые задачи в различных постановках, но во всех случаях без ограничения на достижимость по дугам выделенных подмножеств.

В настоящей работе фактически осуществляется уточнение самого самого понятия ориентированный граф. Суть уточнения состоит в том, что дуги графа не являются равноправными в формировании его путей. Такие графы мы называем орграфами с нестандартной достижимостью. Такое обобщение классического понятия позволяет расширить область применения графовых моделей и методов, в том числе к задачам маршрутизации в сетях с участками затухания и участками усиления сигнала, к нахождению кратчайших путей выполиения технологических процессов, в которых имеются ограничения на порядок (последовательность) выполнения некоторых операций к нахождению вероятностей в задачах случайного блуждания, когда имеются переходы, влияющие на свойства частицы.

Впервые вопрос о введении ограничения на прохождение по дугам выделенных подмножеств рассмотрен в работах Басапговой Е. О., Ерусалимскогс Я. М. и Логвинова С. Ю. (|2| - |5], [7|, |8|). В работах (|7| - |8|) рассмотрено условие смешанной достижимости для орграфов, которое состоит в том, что множество дуг графа состоит из объединения непересекающихся подмножеств U = Щ U Un и допустимыми путями являются только тс, которые пе содержат участков из двух подряд идущих дуг множества Ui,. При этом, рассмотрены задача о достижимости и комбинированная задача о пути макг симальной допустимости и минимальной длины (|28]). В работах (|2| - |5|) рассмотрено условие смешанной достижимости для частично - ориентированных графов, которое состоит в том, что на графе кроме дуг существуют неориентированные звенья и ставится условие, что по звеньям запрещается проходить более одного раза подряд. При этом, рассмотрена задача о достижимости и потоковая задача на частично-ориентированных графах со смешанной достижимостью.

Данная работа посвящена разработке общего подхода для решения задач о достижимости и о случайном блуждании частицы по вершинам графа, а так же потоковой задачи на ориентированных графах с различными ограничениями на достижимость. Для этого изучены ориентированные графы с ограничением на прохождение по дугам выделенных подмножеств. Определено несколько видов ограничений на достижимость: магнитная достижимость, вентильная достижимость и механическая достижимость. Разработан универсальный для каждого из рассматриваемых условий подход (который состоит в том. что строится вспомогательный граф, количество вершин которого больше, чем у исходного, но на котором все дуги являются равноправными, а пути допустимыми).Это позволяет свести задачу о достижимости на исходно? графе с ограничением к задаче о достижимости на вспомогательном графе без ограничения. Данный подход исользован при решении задач не только о достижимости, мо и о случайном блуждании частицы по вершинам графа, а так же при решении потоковой задачи для сети с ограничением на множество допустимых путей.

В первой главе рассмотрено понятие магнитной достижимости на ориентированном графе, у которого множество дуг II состоит из объединения непересекающихся непустых множеств и = 1/м^иц (множество называем множеством магнитных дуг, а £/# - множеством немагнитных дуг) и задано одно из условий магнитной достижимости. Введены три вида условий магнитной достижимости, определяющие множество допустимых путей:

1. Условие магнитной достижимости с накоплением неубывающей магмит-ности, при котором с каждым отрезком [1,г]дг пути ¡1 связана величина накопленной магнитности пути Л/г(г), равная количеству магнитных дуг пути /х на этом отрезке, тогда если к г- тому шагу путь от своего начала накопил магнитноегь большую либо равную к (А/((г) > к) и среди дуг выходящих из концевой вершины г- той дуги хотя бы одна магнитная, то следующая (г + 1-я) дуга обязана быть дугой из множества 1/м,

2. Условие магнитной достижимости с накоплением-исчезапием магнитности, при котором с каждым отрезком [1,г]дг пути ¡л, связана величина накопленной магнитности пути

АД») = тах | |/10") П IIм\ - к |/х(Я П IIн\ 1 , тогда если к г- тому шагу путь от своего начала накопил магиитность большую либо равную к (АДг) > к) и среди дуг выходящих из ко/щевой вершины г- той дуги хотя бы одна магнитная, то следующая (г + 1- я) дуга обязана быть дугой из множества Vм- (Вторая сумма означает, что прохождение по дугам множества 11ц уменьшает накопленную магиитность),

3. Условие магнитной достижимости с возрастанием-убыванием магнитности, при котором с каждым отрезком [1,г]дг пути /1 связана величина накопленной магнитпости пути i к v^ ) , max { V I fio(j) П Um I - - V | Mf) n UH\ ? , л+ö i z—' s *—' i j=l :i=l J тогда если к in- тому шагу путь от ei son го начала накопил магпитность большую либо равную к ( max { min {г}ц{1,г) + rj,t(i + l,?n)}} > к) и среди дуг выходящих из концевой вершины т- той дуги хотя бы одна магнитная, то следующая (т + 1-я) дуга обязана быть дугой из множества Um

Ясно, что магнитная достижимость ие обладает транзитивным свойством, т.е. если вершина умагпитно достижима из х, а вершина z магнитно достижима из у, то из этого не следует магнитная достижимость вершины z из вершины х.

Кратчайшие пути, в этом случае, не обладают и экстремальным свойством, состоящим в том, что любой отрезок кратчайшего пути является кратчайшим путем между своими граничными вершинами, а именно на нем основан алгоритм Э. Дейкстры нахождения кратчайших путей (см., например, [1|, [13], [14j). Это означает, что для разработки алгоритма нахождения кратчайших путей на графе с такой достижимостью необходим другой подход.

Описан подход, сводящий магнитную достижимость (любого из перечисленных видов) вершин исходного графа G к достижимости вершин на вспомогательном графе G', приведены правила построения вспомогательных графов для каждого условия магнитпости. Показано, что задача о достижимости вершин исходного графа G с условием магнитной достижимости сводится к задаче о достижимости на вспомогательном графе G':

Теорема 1.2.1 Любому пути ц' и а вспомогательном графе G' соответствует магнитно-накопительный путь ß па исходном и вершина у магнитно-достижима при условии неубывающей магнитпости из вершины х на графе G тогда и только тогда, когда на G' достижима из х, но крайней мере, одна из вершин множества Vy = {у, у1,

Проведено сравнение сложности алгоритмов нахождения кратчайшего пути из некоторой вершины в другую с использованием построения вспомогательного графа и без его использования, Показано, что задача о достижимости на графе с условием магнитной достижимости бег? построения вспомогательного графа может быть решена только полным перебором путей графа, а значит алгоритм нахождения кратчайшего пути с построением вспомогательного графа более быстрый, чем алгоритм без построения вспомогательного графа.

Кроме этого, в. главе 1 рассмотрены задача о случайном блуждании » частицы, а так же потоковая задача на графах с магнитной достижимостью. Показано, что описанный подход позволяет сводить процесс случайного блуждания частицы на графе С с магнитной достижимостью, который не является Марковским к Марковскому процессу на вспомогательном графе С.

В качестве приложения задачи случайного блуждания частицы на графе с магнитной достижимостью рассмотрена бомбардировка частицами кристаллической решетки, состоящей из двух слоев: магнитно- накопительного и туннельного. Показано, что вероятность прохождения частицы через решетку, в этой ситуации, больше, чем вероятность прохождения частицы через решетку без условия магнитности.

Рассмотрение задачи о максимальном потоке в сетях с нестандартной достижимостью потребовало обобщения самого понятия орсети и допустимого потока в ней. В работе дано определение орсети со связанными дугами, когда на графе имеются выделенные попарно непересекающиеся подмножества дуг. Для каждого из таких множеств определена не пропускная способность каждой из дуг, а только суммарная пропускная способность дуг этого подмножества. Ясно, что это потребовало корректировки и определения допустимого потока в такой сети. Предложен алгоритм нахождения максимального потока в сетях со связанными дугами.

Показано, что потоковая задача на исходном графе с магнитной достижимостью сводится к потоковой задаче в сети со связанными дугами, которой является вспомогательный грае}).

Во второй главе рассмотрено понятие вентильной достижимости на ориентированном графе, у которого множество дуг V состоит из объединения попарно непересекающихся непустых множеств V = и • • • и Щ и задано одно из условий вентильной достижимости. Введены три вида условий вентильной достижимости, определяющие множество допустимых путей па графе:

1. Условие вептилыю-пакопительпой достижимости, при котором если среди т дуг вентильного пути содержалась хотя бы одна дуга множества, IIто следующая дуга пути обязана быть дугой множества £/() и. и и.-)+\, или, что то же самое,'прохождение но дуге множества II^ "открываст"для прохождения дуги множества С/7-+г,

2. Условие вентильной достижимости с возрастанием -убыванием доступа на пути, при котором множество вершин X так же состоит из объединения попарно непересекающихся множеств X = Хо и . и Х[:. С каждым отрезком пути ц связана характеристика фц(г) = э, где ? такое, что (Р2°/°/-0(0 ^ тогда если фц(г) = то следующая дуга пути обязана быть дугой множества Щ и . и Ну

3. Условие вентильной достижимости с возрастанием-убыванием энергии на пути, при котором если среди т дуг вентильного пути /х содержалась хотя бы одна дуга множества Uj, то следующая дуга пути обязана быть г дугой множества = У и^, где С/((гп) ~ величина накопленной

С?! (»»)>** О') энергии {'] -того типа) пути а сг*{з) - максимально возможное количество энергии -то['о типа).

Описан подход, сводящий вентильную достижимость (любого из перечисленных видов) вершин исходного графа (7 к достижимости вершин па вспомогательном графе С, приведены правила построения вспомогательных графов для каждого условия вентильной достижимости. Показано, что задача о достижимости вершин исходного графа G с условием вентильной достижимости сводится к задаче о достижимости на вспомогательном графе

С.

Кроме этого, так же, как и в главе 1 рассмотрены задача случайного блуждания частицы, а так же потоковая задача на графах с вентильной достижимостью. Показано, что описанный подход позволяет сводить задачу процесс случайного блуждания частицы на графе с вентильной достижимостью, который не является Марковским к Марковскому процессу на вспомогательном графе G'.

Показано, что потоковая задача па исходном графе G с вентильной достижимостью сводится к потоковой задаче в сети со связанными дугами, которой является вспомогательный граф.

Третья глава посвящена изучению устойчивых и неустойчивых циклов, и стационарного распределения па графах с нестандартной достижимостью.

Введены понятия устойчивых, полуустойчивых и неустойчивых режимов (циклов) графа. Приведены алгоритмы нахождения устойчивых и неустойчивых циклов. Показано, что на графе с ограничением на достижимость устойчивыми циклами могут стать неустойчивые циклы па этом же графе без ограничения на достижимость, а устойчивые циклы (в этом случае) могут исчезнуть.

Так же, введено понятие периодического устойчивого цикла: устойчивый режим будем называть периодическим, если при возведении матрицы переходных вероятностей в некоторую степень, все строки, соответствующие этому режиму вычисленной матрицы получаются некоторой перестановкой этих же строк исходной матрицы. Такая ситуация возникнет лишь г, том случае, когда устойчивый режим является компонентой сильной связности и из каждой вершины есть только одна дуга, ведущая в вершину данного режима с вероятностью перехода, по ней равной единице. Показано, что для цепи Маркова, в которой присутствует хотя бы один периодический режим не существует стационарного распределения.

Так же, известно, что для конечной цени Маркова с дискретным временем существует единственное стационарное распределение тогда и только toi да, когда цепь является сжимающей. В диссертационной работе в терминах теории графов сформулировано и доказано следующее утверждение:

Теорема 3.2.2 Для того, чтобы конечная цепь Маркова G являлась сжимающей необходимо и достаточно, чтобы выполнялись следующие условия:

1. G не содержит периодических устойчивых режимов,

2. На G существует единственная изолированная компонента сильной связности H,

3. В компоненте сильной связности Н сущсстнуют но к]мннсй мере два цикла щ и г]2, длины которых (|т71| и \щ\) - взаимно и\юстые числа.

Показано, что если без ограничения на. достижимость для цепи Маркова существовало стационарное распределение, то при ограничении на достижимость стационарного распределения для этой же цени может не существовать.

В четвертой главе рассмотрено понятие механической достижимости на ориентированном графе, которая состоит в том, что задано некоторое отображение д : II —»■ Z ("паклоп"дуги и), которое определяет разбиение множества дуг II на попарно непересекающиеся подмножества и+ = гЧМт и. = д-\ъ\г+) и ин = (гЧОТ) (т.е. и = и+ и ин и II-) и задано условие механической достижимости, состоящее в том, г что с каждым отрезком пути ¡1 связана числовая характеристика ®чх{ьэ ~ 1) +д(1*(з)), ПРИ этом, = тт{0,^(д(г))}. Тогда если ЦД1, г) + #(/¿(¿ + 1)) < 0, из концевой вершины г-той дуги выходят дуги только множества 11+ или г-той дуга была из множества 11+, то следующая дуга пути должна быть из 11+ (если такие выходят из текущей вершины).

Описан подход, сводящий механическую достижимость вершин исходного графа О к достижимости вершин на вспомогательном графе С, приведено правило построения соответствующего вспомогательного графа. Показано, что задача о достижимости вершин исходного графа С с условием механической достижимости сводится к задаче о достижимости на вспомогательном графе С.

Кроме этого, так же, как и в главе 1 показано, что процесс блуждания частицы па графе С с механической достижимостью сводится к Марковскому процессу на вспомогательном графе С.

В качестве приложения условия механической достижимости рассмотрены следующие задачи:

1. Некоторая функция задана своими значениями в узлах сетки произвольного вида (например прямоугольной). Требуется определить области локального минимума этой функции. Показано, что эта задача сводится к задаче поиска устойчивых циклов.

2. На графе С/,/) заданы отображения д : 17 2 и М : I 4 {0,1} такие, что д - задает "наклон"дуги, а М - определяет области магнит-ности таким образом, что если М{х) = 1, то ©"(ж) С Им \/х £ X.

Рассмотрен случайный процесс блуждания некоторого объекта (произвольной природы) но нершинам графа С. При этом, объект может двигаться только по",возможным путям с соблюдением условия неубывающей магнитности. Требуется для произвольного начального положения объекта определить возможные точки его остановки (т.е. прекращения движения) или возможные точки его циклического движения (устойчивые циклы).

Пятая глава посвящена задачам о прибыли в сети. Рассмотрены задачи: г

1. О максимальной прибыли в сети от прохождения по пей потока заданной величины, которая заключается в том, что для каждой дуги указаны пропускная способность, вероятность перехода по данной дуге (которая играет роль распределения потока) и величина прибыли от прохождения по пей единичного потока. Необходимо при заданной величине потока назначить вероятности перехода по дугам сети таким образом, чтобы прибыль от потока была максимальной.

2. О максимальной прибыли от потоков с обратной связью в сетях с ограничениями на достижимость, которая состоит в том, что пропускная способность каждой дуги задана как в прямом направлении, так и в обратном. В результате возникает пара потоков, которая образует поток с обратной связью. Ясно, что потоковая задача такого вида имеет смысл только в орсетях с ограничением на достижимость. Рассмотрена задача максимизации прибыли от потоков 'такого вида при условии связи и ограничениях на достижимость по дугам выделенных подмножеств.

В приложении приведены листинги программ для решения потоковой задачи и задачи о случайном блуждании па орграфах с магнитной достижимостью. Программы реализованы на языке С + + в среде ВшМегЗ.О.

Работа выполнена на кафедре алгебры и дискретной математики Ростовского государственного университета. Особую благодарность автор выражает своему научному руководителю профессору Я. М. Ерусалимскому за постоянную заботу и помощь при работе над диссертацией. г

1. Басаигова Е.О., Ерусалимский Я.М. Смешанная достижимость на частично ориентированных графах.//Деп в ВИНИТИ., 1982, №5892-82.

2. Басаигова Е.О., Ерусалимский Я.М. Алгоритм нахождения максимального потока в частично ориентированной сети.//Дискретные структуры и их приложения.Элиста, КГУ. 1988. -с. 23-28.

3. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. -М.: Вузовская книга. 2001. -279с.7| Ерусалимский Я.М. Эйлеровость графов со смешанной достижимостью.// сб. Модели, графы и алгебраические структуры. Элиста, 1989. с. 45-48.

4. Ерусалимский Я.М., Логвинов С.К). Некоторые задачи достижимости на графах с ограничениями.// Извести я ВУЗов. Северо-Кавказский регисл Естественные науки. 1996, №2, -с. 14-17.

5. Ерусалимский Я.М., Скороходов В.А. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях.// Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2003, №2, -с. 3-5.

6. Ерусалимский Я.М., Скороходов В.А. Потоки в сетях со связанными дугами.// Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2003, -с. 3-8.

7. Ерусалимский Я.M., Скороходов В.А. Прибыль от потоков с обратной связью в орсстях с ограничениями па достижимость.// Известия ВУЗов. Северо-Кавказский регион. Естественные пауки. Приложение. 2003,-с. 9-12.

8. Замбицкий Д.К., Лозовапу Д.Д. Алгоритмы решения оптимизационных задач на сетях. -Кишинев: Штиипца, 1983. -171с.

9. Зыков A.A. Теория конечных графов. -Новосибирск: Наука, 1969. -543с.

10. Зыков A.A. Основы теории графов. -М: Наука, 1987. -384с.

11. Климов Г.П. Теория вероятностей и математическая статистика. -М.:МГУ 1983. 394с.г

12. Кристофидес Н. Теория графов. Алгоритмический подход. Пер. с анг. -М.: Наука, 1978. -432с.

13. Курош А.Г. Курс высшей алгебры. -М: Наука, 197G. -436с.

14. Ope О. Теория графов. Пер. с апг. -М: Наука, 1980. -334с.

15. Свами М., Тхуласирамап К. Графы, сети и алгоритмы. Пер. с апг. -М: Мир, 1984. -454с.

16. Скороходов В.А. Случайные блуждания и потоки в сетях с магнитной достижимостью.//в сб. Модели и дискретные структуры. Элиста, 2002. с. 93-100.

17. Скороходов В.А. Графы с магнитной достижимостью. Марковские процессы и потоки в сетях.//Деп в ВИНИТИ, 2003, JVM10-B2003.

18. Форд Л.Р, Фалксрсон Д.Р. Потоки в сетях. Пер. с апг. -М: Мир, 1966. -с.

19. Феллер В. Введение в теорию вероятностей и её приложения. т1, т2. -М.: 1967. с.

20. Харари Ф. Теория графов. Пер.с апг. -М: Мир, 1973. -300с.

21. Харари Ф., Пал мор Е. Перечисление графов. Пор. с ям г. -М.: Мир, 1977. -324с.

22. Цой С., Цхай С.М. Прикладная теория графои. -Алма-Ата: Наука, 1971. -500с.

23. Яблонский С.В. Введение и дискретную математику. -М: Наука, 1979. -272с.

24. Hansen P. Bieriterion path problems.// Lect. Notes Econ. and Math. Sypt. 1980. -177. -109-127.

25. Harary F. Conditional conectivity.//Networks. 1983. -13, №3. -347-357.

26. Ihm Heuug-Soou, Nfcafcos Simeon C. On legal paths problems on digraphs.// Inf. Process Lttt. -1984. -18 №. -83-93.