Математические модели и алгоритмы на графах с нестандартной достижимостью тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Скороходов, Владимир Александрович

• Скороходов, Владимир Александрович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Скороходов, Владимир Александрович

Содержание.

Введение

Глава 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. О максимальной прибыли от потоков с обратной связью в сетях с ограничениями на достижимость, которая состоит в том, что пропускная способность каждой дуги задана как в прямом направлении, так и в обратном. В результате возникает пара потоков, которая образует поток с обратной связью. Ясно, что потоковая задача такого вида имеет смысл только в орсетях с ограничением на достижимость. Рассмотрена задача максимизации прибыли от потоков 'такого вида при условии связи и ограничениях на достижимость по дугам выделенных подмножеств.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Скороходов, Владимир Александрович, 2004 год

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.