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

л

п

■-ч-и-ч гаавз

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

Х1Цд

Кузьминова Марина Валерьевна

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

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

1 5 ОКТ?

АВТОРЕФЕРАТ

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

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

003479865

Работа выполнена

на кафедре алгебры и дискретной математики факультета математики, механики и компьютерных наук Южного Федерального Университета в г.Ростове-на-Дону.

Научный руководитель: кандидат физико-математических наук,

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

Официальные оппоненты: доктор физико-математических наук,

профессор Соколов Валерий Анатольевич

кандидат физико-математических наук, доцент Басангова Елена Одляевна

Ведущая организация: Воронежский Государственный Университет, г. Воронеж.

Защита диссертации состоится " М_2009 года в ч. мин, на

заседании диссертационного совета Д212.208.22 Южного Федерального Университета по адресу: Таганрог, пер. Некрасовский, 44, ауд. Д-406.

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

Автореферат разослан " " ^_2009 года.

Просим Вас прислать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу: 347928, Таганрог, пер. Некрасовский, 44, диссертационный совет Д212.208.22.

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

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

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. В последние годы наряду с традиционными континуальными математическими моделями, в основе которых лежат дифференциальные и интегральные уравнения, стали широко использоваться дискретные модели. Их широкое распространение связано и с прогрессом вычислительной техники, поскольку существует ряд дискретных задач, для решения которых не существует алгоритмов, отличных от полного перебора вариантов. Среди дискретных математических моделей графовые модели занимают заметное место. Абстрактный математический объект - граф, при использовании его в качестве средства математического моделирования, подвергся серьезной модернизации. В качестве инструмента математического моделирования используются, как правило, ориентированные взвешенные графы. В различных задачах веса заданные на дугах и вершинах могут иметь различное истолкование: стоимость, длина, вес, время прохождения сигнала, вероятность перехода, и т.д. Дискретные графовые математические модели стали эффективным средством формализации задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управления производством, сетевого и календарного планирования, информационных систем, и многих других. Эффективные алгоритмы, разработанные для решения задач о кратчайших путях, максимальных потоках в сетях, задач о случайных блужданиях стали мощным инструментом решения различных задач маршрутизации, анализа и расчета электрических сетей. Все более активно графовые математические модели применяются для анализа и синтеза коммуникационных сетей и навигации в них. Маршрутизация в Интернете осуществляется с помощью эффективного графового алгоритма нахождения кратчайшего пути между заданными узлами этой глобальной сети. Широкая применимость графовых методов и математических моделей, основанных на использовании ориентированных взвешенных графов привела к формированию класса алгоритмов, который сегодня имеет свое собственное название «Алгоритмы на графах». Классическими задачами решаемым с помощью этих алгоритмов являются задачи о достижимости (т.е. о существовании пути, связывающем две заданные вершины), о нахождении путей, обладающих какой-либо экстремальной характеристикой (например, кратчайший, или наиболее надежный путь), о случайных блужданиях, потоковая задача. Все они хорошо изучены и разработаны эффективные алгоритмы их решения. При этом предполагается, что все пути на графе являются допустимыми, т.е. не накладывается никаких ограничений на достижимость. Наиболее известные работы в этой области принадлежат Кристофидесу Н., Басакеру Р.Д., Харари Ф., Бержу К., Дейкстре Э., Флойду Р., Замбицкому Д.К., Ope О., Саати Т., Фалксрсону Д.Р., Форду JI.P.

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

В работах Ерусалимского Я.М., Басанговой Е.О., Логвинова С.Ю., Скороходова В.А., Петросяна А.Г. описапы различные виды ограничений на достижимость. Так, Ерусалимским Я.М. и Басанговой Е.О. рассмотрено несколько видов достижимости на частично-ориентированных графах, на которых присутствуют ориентированные и неориентированные ребра. Введено понятие смешанной цепи, на дуги и звенья которой накладываются различные условия, в зависимости от вида ограничений. Например, рассмотрены случаи, когда в смешанной цепи два неориентированных ребра не могут следовать непосредственно друг за другом, или дуги и звенья строго чередуются.

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

орграфах с накоплением неубывающей мапштности * - го уровня. На таких графах

допустимым является магнитно-накопительный путь порядка * с неубывающей

магнитностью, т.е. такой путь, что если на т - м шаге величина накопленной

магнитности не меньше * и среди выходящих дуг есть хотя бы одна магнитная, то т + ^ -

я дуга пути должна быть магнитной. Другой вид достижимости — вентильно-

накопительная. В этом случае множество дуг графа представляется в виде

и -Ur.vjU.Kj...и [Л „

0 1 *. В допустимом пути прохождение по дуге множества

и, У = 1,2,...)

■> ' делает доступными для прохождения дуги множества

и ^{¡ = \,2,.:,к-1) т

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

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

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

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

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

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

достижимости: на начальном и конечном отрезках пути с параметром на отрезке

п\>пг\а и магнитная достижимость, возникающая после "о шагов. Описана монотонная достижимость, которая является обобщением магнитной. Кроме того, описаны динамические и периодические динамические графы, т.е. такие ориентированные графы, для которых вводится дискретное время и задается функция активности дуг - дуги на графе существуют не в любой момент времени, а только в свои промежутки активности. Ясно, что такие задачи могут рассматриваться как математические модели транспортных или информационных сетей, в которых в определенные моменты времени функционируют не все участки сети. Для каждого вида ограничений на достижимость построены графовые математические модели, которые позволяют свести решение

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

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

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

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

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

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

4. Для периодической динамической сети введены определения максимального динамического потока, исходящего из источника в момент времени е N, и максимального динамического потока из источника, приходящего в сток в момент времени ^е N и разработаны алгоритмы их нахождения.

5. Полученные алгоритмы реализованы в виде комплекса программ.

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

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

1. Определены и изучены магнитная и монотонная достижимости с четырьмя видами ограничений: на начальном и конечном отрезках пути, ограничения, возникающие после п0 6 N шагов и на отрезке \пх, и, ]4..

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

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

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

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

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

6. Алгоритмы, предложенные в работе, реализованы в виде комплекса программ, приведенного в приложении.

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

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

1. Результаты диссертации докладывались на Воронежской весенней математической школе «Понтрягинские чтения XVIII» (г. Воронеж, 2007).

2. По результатам работы сделан доклад на III всероссийской школе-семинаре «Математическое моделирование и биомеханика в современном университете» (пос. Дивноморское, 2007).

3. Сделан доклад на 5-й всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь XXI века — будущее российской науки» (г. Ростов-на-Дону, 2007).

4. Результаты работы неоднократно обсуждались на научном семинаре кафедры алгебры и дискретной математики факультета математики, механики и компьютерных наук ЮФУ.

5. Результаты работы вошли в отчеты по проектам «Нестандартная достижимость на ориентировагашх графах» (Грант конкурсного центра

Минобразования РФ по разделу естественные науки, проект Е02-01-231) и «Графы и сети с нестандартной достижимостью» (Ведомственная программа Минобрнауки РФ «Развитие научного потенциала высшей школы», подпрограмма №3, раздел З.З.- поддержка исследований проводимых молодыми учеными, проект 7857).

6. По материалам диссертации опубликовано 8 печатных работ, в том числе, монография [8].

Публикации. По материалам диссертации опубликовано 8 работ [1]-[8].

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, приложения и списка литературы. Объем основного текста диссертационной работы составляет 114 стршшц, включая 47 рисунков, библиографический список изложен на 5 страницах и содержит 52 наименования, приложение содержит 16 страниц.

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы, сделан обзор существующих видов нестандартной достижимости, сформулированы цели работы, выделена ее научная новизна и дана краткая аннотация всех глав диссертации.

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

Динамический граф - это ориентированный граф вида с(Х,11,/, г), множество дуг которого представляет собой объединение двух непустых непересекающихся подмножеств, которые называются множеством обычных и множеством временных дуг, т - функция активности. Временные дуги графа доступны для прохождения не в любой момент времени, а только в периоды активности. Путь на динамическом графе является допустимым, если все его дуги активны в момент прохождения их путем. Также рассмотрены периодические динамические графы Ог(Х,1/,/, г), для дуг которых промежутки активности отличаются на некоторое натуральное число Т, называемое периодом.

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

Теорема 1.1.1. Пусть С(Х,и,/,т) - динамический граф, х,у,геХ- Пусть :[!,«,]„ - путь из вершины * в вершину у, //[,2]:[1,п2]м -»С/ - путь из вершины у в вершину 2. Тогда для того, чтобы существовал путь из вершины х в вершину 2, достаточно выполнения условия ?2 = tx + И,.

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

Пусть С(Х,и,/, г) ~ периодический динамический граф с периодом Т. Построим для него вспомогательный граф С(Х', £/', Пусть

V«,. е и(/ = 1,2,...) М„ = и[а,+п-Т,Ь1+п-Т\ Пайдем ¿>тах = тах {Ь,}- Пусть ' я=0.1.2,... 1-1,2,...

существует целое число к > 0, такое, что Ьтах е[&-Г + 1,(А: + 1),7']- Назовем число к

характеристикой графа Су. Тогда для вспомогательного графа С | = {к + \)-Т -\Х\, а

множество дуг £/' строится по следующим правилам: для всех дуг и е. II, таких, что /(м) = (/,у)

• V« = 1 ..{к-+1)-Т-1, если г(«,т)=1, то £/'= [/'у {„-,}, где Г{и\)={1+{т-\)Щ] + т-\Х\)-,

• Если г(м,(А; + 1)-7,) = 1>то [/'= [/'у{м'}, где

Сложность построения графа G{X,U,f) равна о{п2 ), где п — |Х| ■

Получена теорема о соответствии между дугами на исходном и вспомогательном графах:

Теорема 1.2.1. На вспомогательном графе G'{X',U',f) дуге ueU: f(u)=(i,j) в момент времени t е N: r(u,t)= 1 соответствует дуга и'е {/', такая, что . /(«')=(' + (' - l)X\,j+t\X\), если\<t<kT-

• /(и') = (i + (i0 -'./ +101.А'|), если 3 л g Z": t = t0 + n T, kT < t0 < {k + l)r-1;

• f{u')=(i + ((k + \)r-ilX\,j + kT\X\),<icnK 3m eZ+ :t = {k+\)T + mT. Справедливость теоремы следует из правила построения вспомогательного графа

G'(X',U',f).

Из алгоритма построения вспомогательного графа следует, что в случае периодических динамических графов дискретное время N можно разделить на два промежутка: конечный «подготовительный», и бесконечный периодический.

Введены определения периодической динамической сети и динамического потока. Определена величина динамического потока, исходящего из источника в момент времени t0 6 N и величина динамического потока, приходящего в сток к моменту времени f, eJV.

Определение 1.3.6. В периодической динамической сети GT(X,U,f, г,с) величиной динамического потока, исходящего из источника s' в момент времени t0 е N, в сток /' называется j - ~^fl(uJQ)- Максимальным динамическим потоком,

т(„,10Н

исходящим из источника s' в момент времени /0 е N, в сток f называется динамический поток, для которого величина ^ ^ _ t ) максимальиа (обозначим

Vl/et/: и, (и )=л1

ее ^Лгоах)-

Определение 1.3.7. В периодической динамической сети GT(X,U,f, г,с) величиной динамического потока из источника приходящего в сток t' в момент

времени ^ eN, называется ¿/Ы _ Максимальным динамическим потоком

Vu&iPl (")=<' r(u,r,)--l

из источника д'1, приходящим в сток t' в момент времени tx £ N, называется

динамический поток, для которого величина ^Ы _ /,) максимальна (обозначим

г/Ы"1™).

Различие между этими величинами заключается в том, что в первом случае источник рассматривается в одно и то же время ?0, тогда как в сток динамический поток может «прийти» в любой момент времени ^ > (0. Во втором случае, наоборот, известен момент , в который динамический поток «приходит» в сток, но начальные моменты времени при этом могут быть различными.

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

Теорема 1.3.2. Пусть СТ{Х,1/,/, т,с) - периодическая динамическая сеть с характеристикой к, - источник и сток в сети . Тогда \/т = 1,2,...,Г

^[¡Г+ет^пих = ^[ИЧя+лГ].тк >" = 1,2,... .

Теорема 1.3.3. Пусть выполняются условия теоремы 1.3.3. Тогда

\/т = 1,2,..„Г = = 1,2.....

Введено понятие суммарных максимальных потоков и формулируются теоремы о постоянстве этих величин на периодическом участке.

Сформулировано и доказано достаточное условие экстремальности кратчайшего пути па периодическом динамическом графе:

Теорема 1.4.1. Пусть : [1,«]ы —> 1} (¿0 е /V) - кратчайший путь из некоторой

вершины х1 е X в некоторую вершину х2 еХ с началом в момент времени ?0 е N на периодическом динамическом графе От(Х,1/,/, г,/). Рассмотрим отрезок этого пути '[Я1 >п2]ы ~~> ^ (/] 6 N), соединяющий вершины ух и у2. Для того, чтобы отрезок //[([] являлся кратчайшим путем из ух в у2, достаточно выполните условия ='о +И1

Введены понятия кратчайшего пути из вершины х в вершину у с началом в момент времени (0 Е N и кратчайшего пути из вершины X в момент времени в

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

Теорема 1.4.3. На графе С для всех -значений =1а+пТи0 е[£Г+1,(£ + 1)г]м,п = 0,1,2,... длина кратчайшего пути с начальным моментом времени 1п между любыми двумя вершинами есть величина постоянная.

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

Во второй главе определены и исследованы ограниченные магнитные и монотонные достижимости. Введены четыре типа магнитной достижимости (на начальном и конечном отрезках пути с параметром и0, на отрезке натурального ряда [п],л2]у, магнитная достижимость, возникающая после п0 шагов). Показано, что магнитная достижимость на начальном отрезке пути, а также достижимость, возникающая после п0 шагов, являются частными случаями достижимости на отрезке [я,, пг ]Л,.

В отличие от магнитных достижимостей, описанных в работах Ерусалимского Я.М., Басанговой Е.О., Скороходова В.А. и Петросяна А.Г., в настоящей работе рассмотрены случаи, когда магнитные ограничения действуют не на всем протяжении пути, а лишь на некотором его отрезке. Такие достижимости названы ограниченными магнитными достижимостями. Построена математическая модель задачи о достижимости для введенных типов ограничений на основе вспомогательных графов. Построение вспомогательного графа является методом сведения достижимости на графах с ограничениями к достижимости на обыкновенных ориентированных графах. Вспомогательный граф имеет больше вершин и дуг, но его можно рассматривать как обычный орграф со стандартной достижимостью.

Пусть - граф с одним из видов ограниченной магнитной достижимости.

Построим вспомогательный граф 0(Х*, С/,/*), такой что = 2 • |Х\, а множество V строится следующим образом:

• если /(и) = (г, у), и е Vн, к множеству V добавляются дуги , У2, такие, что

• если /(м) = (|,у), и е Vм, к множеству [/' добавляются дуги такие, что

/■(^М/, )я /•(»>)= (/+14 ]+\Х\);

• если для дуги /(м) = («, _/'), и е ¡7^ нет ни одной исходящей магнитной дуги, то к

множеству V добавляется дуга V,такая,что (у _/)•

Сложность построения графа С}(Х',и,/') равна где п = .

Доказана теорема о взаимнооднозначном соответствии между допустимыми путями на исходном графе с ограничениями и путями на вспомогательном графе:

Теорема 2.2.1. Пусть - граф с магнитной достижимостью,

С(Х\и',/') - граф, построенный по графу СЛ;. На графе Ом существует допустимый пугь из вершины х е X в вершину у е X тогда, и только тогда, когда на графе С существует путь из вершины х е X' в одну из вершин уеХ' или

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

Теорема 2.3.1. Величина максимального потока в сети Ом(Х,1!,/,с) равна

пропускной способности минимального магнитного разреза, т.е. существует поток А , такой что £?(/7*)=тахс?(/7)=ттс(р).

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

Теорема 2.4.1. Кратчайшему пути длины п < па на графе (X, ¡7,/,/) из вершины е X в вершину / е X соответствует кратчайший путь из вершины ^ в подмножество вершин + |Х|} на вспомогательном графе С(Х\ {/У').

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

В третьей главе введены четыре типа монотонной достижимости (на начальном и конечном отрезках пути с параметром п0, на отрезке натурального ряда [«¡,«2]Л,, магнитная достижимость, возникающая после и0 шагов).

Монотонная достижимость является обобщением магнитной достижимости на случай, когда множество дуг графа разбивается на Л +1 попарно непересекающихся

Л

подмножеств и = ио £/,•)■ Путь на графе с монотонной достижимостью является

ы

допустимым, если подпоследовательность индексов дуг пути (не учитывая дуги множества С/0) не убывает (индекс дуги - номер подмножества дуг, которому она принадлежит).

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

Доказана теорема о взаимнооднозначном соответствии между допустимыми путями на исходном графе с ограничениями и путями на вспомогательном графе:

Теорема 2.2.1. На графе С(Х,и,/) с монотонной достижимостью существует допустимый путь из вершины хеХ в вершину у е X тогда, и только тогда, когда на графе С{/',/') существует путь из вершины х в подмножество вершин

у + к-\х\,к = 0,\.....Я-1.

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

Теорема 3.3.1. Величина максимального потока в сети 0Моп(Х,и,/,с) равна

пропускной способности минимального монотонного разреза, т.е. существует поток А*, такой что £/(/7*)= тах ¿(/1)-пуп с(р).

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

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

В заключении приведены основные результаты диссертационной работы.

В приложении приведены листинги программы и описание работы программного комплекса.

Положения, выносимые на защиту

1. Определены и исследованы новые виды нестандартной достижимости: ограниченные магнитные и монотонные достижимости.

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

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

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

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

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

1. Кузьминова MB. Ограниченные магнитные достижимости на ориентированных графах.// Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2006, №6, -с. 12-26.

2. Ерусалимский Я.М., Кузьминова М.В. Динамические периодические графы.// В сб. Математическое моделирование и биомеханика в современном университете. Труды III всероссийской школы-семинара, (2007г.)

3. Кузьминова М.В. Динамические периодические графы.// В сб. Современные методы теории краевых задач. Материалы Воронежской весенней математической школы «Понтрягинские чтения XVIII». (Воронеж, 2007г.)

4. Кузьминов Р.Н., Кузьминова М.В. Ограниченные магнитные достижимости на ориентированных графах.// В сб. Современные методы теории краевых задач. Материалы Воронежской весенней математической школы «Понтрягинские чтения XVIII». (Воронеж, 2007г.)

5. Кузьминова М.В. Динамические периодические графы. Задача о максимальном потоке.// В сб. материалов докладов 5-й всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь XXI века -будущее российской науки». (Ростов-на-Дону, 2007г.)

6. Кузьминова М.В. Периодические динамические графы. Задача о максимальном потоке.// Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2008, №1, -с. 14-20.

7. Кузьминова М.В. Динамические графы. Задачи о случайных блужданиях и кратчайших путях.// Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2008, №2, -с. 16-20.

8. Ерусалимский Я.М., Скороходов В.А., Кузьминова М.В., Петросян А.Г. Графы с нестандартной достижимостью: задачи, приложения. - Ростов н/Д.: Южный Федеральный Университет, 2009 - 195 с.

В работе [2] Ерусалимскому Я.М. принадлежит постановка задачи. Проведение подробных доказательств всех теоретических результатов и разработка алгоритмов принадлежит автору диссертации. Работа [4] выполнена совместно с Кузьминовым Р.Н., который является соразработчиком программкой реализации предложенных автором алгоритмов. В монографии [8] автору диссертации принадлежат результаты, изложенные в §2.3, §2.4, §3.2, §4.7 и §6.6. Работы [6] и [7] опубликованы в изданиях, входящих в «Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утвержденный ВАК.

Сдано в набор 01.10.2009 г. Подписано в печать 01.10.2009 г. Формат 60x84 V,e. Бумага офсетная. Гарнитура Times. Оперативная печать. Усл. печ. л 1,0. Уч-изд..л. 1,0.

Тираж 120 экз. Заказ № 649. Типография Южного федерального университета 344090, г. Ростов-на-Дону, пр. Стачки, 200/1, тел (863) 247-80-51.