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

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

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

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

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

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

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

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

003458155

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

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

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

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

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

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

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

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

Защита диссертации состоится ® ^ 2008^ года в ^ ч.^Чшн. на заседании диссертационного совета Д212.208.22 Южного Федерального Университета по адресу: Таганрог, пер. Некрасовский, 44, ауд. Д-406.

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

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

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

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

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

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

А Н. Целых

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

В работах Скороходова В.А. рассмотрены орграфы с накоплением неубывающей магнитности ^ - го уровня. На таких графах допустимым является магнитно-накопительный путь порядка ^ с неубывающей магнитностью, т.е. такой путь, что если на - м шаге величииа накопленной магнитности не меньше ^ и среди выходящих дуг

есть хотя бы одна магнитная, то т + 1 - я дуга пути должна быть магнитной. Другой вид достижимости - вентилыю-накопительная. В этом случае множество дуг графа

представляется в виде ^ - ^ ^ ^ ^ . В допустимом пути прохождение по дуге V, 0 = 1,2,...)

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

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

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

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

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. По материалам диссертации опубликовано 7 печатных работ.

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

В настоящей работе рассмотрены случаи, когда магнитные ограничения действуют не на всем протяжении пути, а лишь на некотором его отрезке. Такие достижимости названы ограниченными магнитными достижимостями. Рассмотрены три вида достижимостей - на начальном отрезке пути длины па, на конечном отрезке пути длины па, магнитная достижимость, возникающая после й0 шагов и магнитная достижимость на отрезке натурального ряда [«, ,пг\. Соответствующие графы обозначаются

с%(ХДЛ, о^хдЛп о^редл.

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

я

на Л + 1 попарно непересекающихся подмножеств Г/ = Г/0 и С/,). Путь на графе с

ы

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

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

достижимости обозначаются (Ц&Ш С>Ь^0,(ХДЛ и

,]• Сформулирована теорема о связи достижимости на графах и

^^юг-

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

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

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

Теорема 1.4,1. Пусть 0{Х,1]г) - динамический граф, х,у,г е X. Пусть /¿^]:Р,л,^ ->¿7 - путь из вершины х в вершину у, /лЬ1: ->11 - путь из

вершины у в вершину г. Тогда для того, чтобы существовал путь из вершины х в вершину 2, необходимо и достаточно выполнения условия = + п].

Также рассмотрены периодические динамические графы СТ(Х ,и, /, г), для дуг которых промежутки активности отличаются на некоторое натуральное число Т, называемое периодом.

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

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

граф с магнитной достижимостью,

Ст (3

- граф, построенный по графу м. На графе м существует

О,

у (= У у е X

■* = л и веошину '

тогда, и только тогда, когда на в одну из вершин У ^ или

Теорема 2.2.1. На графе с монотонной достижимостью существует

допустимый путь из вершины х е X в верцщну

х е X в ветчину У е ^

тогда, и только тогда, когда на

гчг ГГI п

графе ' ^ ' '■> ' существует путь из вершины х в подмножество вершин

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

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

Теорема 2.3.1. На вспомогательном графе С\Х',и\/'~) дуге иеС/: /(и) = 0,/) в момент времени / <е N: г(и,()= 1 соответствует дуга м'е V, такая, что

• /(м')=С + (<-1]|х|,7 + /|х|),если \<1<кТ;

• /(»-)= 0 + «„ -1)|4 j + 'о М)> если Зл е : / = /0 + пТ,кТ < 10 < (к +1 у -1;

• /(«■)= С + № +1)7" -1^1, у + если Зт е 2*: / = (£ + 1)Г + «Г. Справедливость теоремы следует из правила построения вспомогательного графа

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

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

Доказаны теоремы, являющиеся аналогами теоремы Форда-Фалкерсона для графов с ограниченными магнитными и монотонными достижимостями:

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

пропускной способности минимального магнитного разреза, т.е. существует поток // ,

такой что ¿(/7*)= тах*/(/?)= ттс(Р).

ц Р

Теорема 3.3.1. Величина максимального потока в сети СМоп(,Х,и,/,с^) равна пропускной способности минимального монотонного разреза, т.е. существует поток _/7 ,

такой что ¿(/7*3= шах<^(/?)= ттс(Р).

А р

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

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

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

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

Для периодических динамических графов введены определения периодической динамической сети и динамического потока. Определена величина динамического потока, исходящего из источника в момент времени /0 6 Л' и величина динамического потока, приходящего в сток к моменту времени N.

Определение 3.4.3. В периодической динамической сети От(Х,11,/, Г,с) величиной динамического потока, исходящего из источника в момент времени ¡0 в N, в сток /' называется с1[: ] = ^_//(«,/„)■ Максимальным динамическим потоком,

исходящим из источника в момент времени 10 е N, в сток называется

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

!(»,<» >1

(обозначим ее ¿Мтш()

Определение 3.4.4. В периодической динамической сети СТ(Х,11, г,с) величиной динамического потока из источника л', приходящего в сток /' в момент времени ^ 6 Л^, называется г/1'1' = ^ //(г/,?,). Максимальным динамическим потоком

Уие'У/ь („>/'

1<И.1|Я

из источника У, приходящим в сток /' в момент времени ^ £ /V, называется

динамический поток, для которого величина с?1'1 = ^//(м,/,) максимальна

УмбУ »(»,',>=1

(обозначим

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

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

Теорема 3.4.1. Пусть Су (X, ГУ, т, с) - периодическая динамическая сеть с характеристикой к, 51,?' - источник и сток в сети Ст. Тогда V/» = 1,2,...,Т

^ЦТннЫж = ^[«Чт+иПтач'" = ^.....

Теорема 3.4.2. Пусть выполняются условия теоремы 3.4.1. Тогда V»! = 12 Т £/'НЧ",1т"' = п = 1 2

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

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

Теорема 4.1.1. Кратчайшему пути длины п<п0 на графе С,''{X,II,_/",/) из вершины ж е X в вершину / е X соответствует кратчайший путь из вершины « в подмножество вершин + |^"|}на вспомогательном графе С'(Х',[Г,/').

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

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

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

Теорема 4.2.1. Пусть /лы: —» 11 е ¿V) - кратчайший путь из некоторой

вершины х1 е X в некоторую вершину х2 е X с началом в момент времени е N на периодическом динамическом графе Ст(Х,и,/, Т",/). Рассмотрим отрезок этого пути ]: [«,,и2^ —»II (/[ € Л'), соединяющий вершины у1 и уг. Для того, чтобы отрезок ц^ являлся кратчайшим путем из у1 в у2, необходимо и достаточно выполнение условия = /0 + и, -1.

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

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

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

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

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

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

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

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

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

2. Описан и изучен новый класс динамических графов.

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

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

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

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

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

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

современном университете. Труды Ш всероссийской школы-семинара. (2007г.)

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

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

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

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

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

Издательство «ЦВВР» Лицензия ЛР № 65-36 от 05 0S 99 г Сдано в набор 20 11,08 г. Подписано в печать 20 11 08 г Формат 60*84 1/16 Заказ Ха 996 Бумага офсетная Гарнитура «Тайме» Оперативная печать Тираж 100 экз Печ Лист 1,0 Усл.печл 1,0 Типография Издательско-полиграфическая лаборатория УНИН Валеологии

«Южный федеральный университет» 344091, г. Ростов-на-Дону, ул Зорге, 28/2, корн 5 «В», тел (863) 247-80-51 Лицензия на полиграфическую деятельность Кз 65-125 от 09 02 98 г

Содержание.

Введение.

Глава 1. Динамические графы.

1.1. Определение и свойства динамических графов.

1.2. Построение вспомогательного графа.

1.3. Математическая модель потока в периодической динамической сети.^.

1.4. Задача о кратчайшем пути.

1.5. Задача о случайных блужданиях.

Глава 2. Ограниченные магнитные достижимости.

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

2.2. Построение вспомогательного графа.

2.3. Потоки в сетях с ограниченными магнитными достижимостями

2.4 Кратчайшие пути на графах с ограниченными магнитными достижимостями.

2.5 Задача о случайных блужданиях.

Глава 3. Ограниченные монотонные достижимости.

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

3.2. Построение вспомогательного графа.

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

3.4 Графовые модели в логистике.

Теория графов предоставляет эффективные средства формализации задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управления производством, сетевого и календарного планирования, информационных систем, и многих других. Одним из таких средств является ориентированный граф. Существует большое количество задач, решаемых на орграфах. Чаще всего рассматриваются задачи о достижимости (т.е. о существовании пути, связывающем две заданные вершины), о нахождении путей, обладающих какой-либо экстремальной характеристикой (например, кратчайший, или наиболее надежный путь), о случайных блужданиях, потоковая задача. Все они хорошо изучены и разработаны эффективные алгоритмы их решения. При этом предполагается, что все пути на графе являются допустимыми, т.е. не накладывается никаких ограничений на достижимость. Наиболее известные работы в этой области принадлежат Кристофидесу Н., Басакеру Р.Д., Харари Ф., Бержу К., Дейкстре Э., Флойду Р., Замбицкому Д.К., Оре О., Саати Т., Ерусалимскому Я.М., Фалкерсону Д.Р., Форду J1.P.([2, 11-20, 24, 35, 43, 46-47]).

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

В работах Ерусалимского Я.М., Басанговой Е.О., Логвинова С.Ю., Скороходова В.А., Петросяна А.Г. ([3-6, 12-19, 36-38, 40-42]) описаны различные виды ограничений на достижимость. Так, Ерусалимским Я.М. и Басанговой Е.О.([3-6, 12]) рассмотрено несколько видов достижимости на частично-ориентированных графах, на которых присутствуют ориентированные и неориентированные ребра. Введено понятие смешанной цепи, на .пути и звенья которой накладываются различные условия, в зависимости от вида ограничений. Например, рассмотрены случаи, когда в смешанной цепи два неориентированных ребра не могут следовать непосредственно друг за другом, или дуги и звенья строго чередуются.

В работах Скороходова В.А. рассмотрены орграфы с накоплением неубывающей магнитности к - го уровня ([41-42]). На таких графах допустимым является магнитно-накопительный путь порядка к с неубывающей магнитностью, т.е. такой путь, что если на т - м шаге величина накопленной магнитности не меньше к и среди выходящих дуг есть хотя бы одна магнитная, то т +1 - я дуга пути должна быть магнитной. Другой вид достижимости — вентильно-накопительная. В этом случае множество дуг графа представляется в виде U = £/0u£/1u.uUk. В допустимом пути прохождение по дуге множества U-(j = 1,2,.) делает, доступными для прохождения дуги множества UJ+l(j = l,2,.,k-i). Также рассмотрены условия накопления-исчезания и возрастания-убывания магнитности, вентильная достижимость с возрастанием-убыванием доступа и энергии на пути, механическая достижимость.

Петросяном А.Г. определена барьерная достижимость, при которой множество дуг разбивается на три попарно непересекающихся подмножества: дуг, увеличивающих барьерный показатель, дуг барьерного перехода и нейтральных дут ([36-38]). С каждым отрезком пути связана числовая характеристика - барьерный показатель частицы. Путь допускает барьерный переход уровня к> 1, если к некоторому шагу он накопил величину барьерного показателя, не меньшую к. Еще один вид ограничений — биполярная магнитность. В этом случае определяется величина накопления биполярной магнитности. Путь считается допустимым, если он удовлетворяет условию биполярной магнитности уровня к.

Общим подходом к решению задач на орграфах с ограничениями на достижимость является построение вспомогательного графа, имеющего большее количество вершин, и обладающего следующим свойством: допустимому пути на исходном графе с ограничениями соответствует некоторый путь на вспомогательном графе, а недопустимому пути не соответствует ни один путь ([3-6, 12—19, 36-38, 40—42]). Алгоритм построения такого графа зависит от вида вводимых ограничений. На вспомогательном графе, таким образом, все пути являются допустимыми, а дуги — равноправными, и его можно рассматривать как обычный ориентированный граф. Для графов с нестандартными достижимостями описанных видов рассмотрены классические задачи о кратчайшем пути из вершины в вершину, о максимальном потоке в сети с нестандартной достижимостью и о случайных блужданиях на таких графах. Наибольшую сложность вызывают две последние задачи, так как при построении вспомогательного графа увеличивается не только количество вершин, но и количество дуг. При этом необходимо правильно распорядится весами дуг, по которым строится несколько дуг на вспомогательном графе. Серьезного осмысления каждый раз требует и перенос соответствующего результата с вспомогательного графа на основной граф.

В настоящей работе рассмотрены ориентированные графы с различными типами ограничений на достижимость и решаются задачи о случайных блужданиях, о кратчайших путях и о максимальном потоке на таких графах. В частности, введено четыре типа магнитной достижимости: на начальном и конечном отрезках пути с параметром п0, на отрезке [w,,w2]N и магнитная достижимость, возникающая после п0 шагов. Описаны орграфы с монотонной достижимостью, которая является обобщением магнитной. Кроме того, рассмотрены динамические и периодические динамические графы, т.е. такие ориентированные графы, для которых вводится дискретное время и задается функция активности дуг — дуги на графе существуют не в любой момент времени, а только в свои промежутки активности. Ясно, что такие задачи могут рассматриваться как математические модели транспортных или информационных сетей, в которых в определенные моменты времени функционируют не все участки сети. Для каждого вида ограничений разработаны алгоритмы построения вспомогательного графа, что позволяет свести решение указанных выше задач на исходном графе к задачам на вспомогательном графе без ограничений на достижимость. Доказаны теоремы о взаимнооднозначном соответствии между исходным и вспомогательным графами.

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

Динамическим графом называется ориентированный граф вида G(X,U,f, г), множество дуг которых представляет собой объединение двух непустых непересекающихся подмножеств, которые называются множеством обычных и множеством временных дуг, т — функция активности. Временные дуги графа доступны для прохождения не в любой момент времени, а только в периоды активности. Путь на динамическом графе является допустимым, если все его дуги активны в момент прохождения их путем. Также рассмотрены периодические, динамические графы GT{X,U,f,r), для дуг которых промежутки активности отличаются на некоторое натуральное число Т, называемое периодом.

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

Теорема 1.1.1. Пусть G{X,U,f,z) — динамический граф, x,y,z е X.

Пусть : [l,Wj]N —>U — путь из вершины х в вершину у, ju^ : [l, п2 ]N —> U — путь из вершины у в вершину z. Тогда для того, чтобы существовал путь из вершины х в вершину z, достаточно выполнения условия t2=tx+nx.

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

Теорема 1.2.1. На вспомогательном графе G'{x\U\f) дуге u&U:f(u)=(i,j) в момент времени t&N:r{u,t)=\ соответствует дуга w'et/', такая, что

• если 1 £t<Kr\

• /И = (i + {t0 - l)X\, J +10\X\), если 3n 6 Z+ : t = t0 + nT, kT < t0 < (к + l)T -1; ((к +1 )Г - 1)|ЛГ|, j + кТ\Х|), если 3m е Z+ : t = (к + l)T + mT.

Справедливость теоремы следует из правила построения вспомогательного графа G'(X',U',f]).

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

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

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

ПМоИ

Максимальным динамическим потоком, исходящим из источника s' в момент времени /0 е N, в сток называется динамический поток, для которого величина d^j = ^fl(u,t0) максимальна (обозначим ее <i[fjmax )•

Vi/eC/ip, («)=*' °

T(u,t0)=l

Определение 1.3.7. В периодической динамической сети GT (X, U, /, г, с) величиной динамического потока из источника я', приходящего в сток ? в момент времени tx е N, называется ^ЬЛ - ХАМ- Максимальным динамическим потоком из источника s',

VueU:p2(u)=f riu,t,)=1 приходящим в сток ? в момент времени tx е N, называется динамический поток, для которого величина d^ = максимальна (обозначим

VueU:p2(u)=t' T(u,ti)=l d[hlm аХ).

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

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

Теорема 1.3.2. Пусть GT(X,U,f, г,с) — периодическая динамическая сеть с характеристикой к, s\t' — источник и сток в сети GT. Тогда

V/W = 1, 2,., Г ^[w+m],max = ^[кТ+т+пТ\тзх ' П ~ 1»^,---

Теорема 1.3.3. Пусть выполняются условия теоремы 1.3.3. Тогда Vm = 1,2,.,Г d[kT+m]-m" = d[kr+a+nT]-'m ,п = 1,2,.

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

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

Теорема 1.4.1. Пусть /^j :[l,«]N —>U (t0 еЖ) — кратчайший путь из некоторой вершины ххеХ в некоторую вершину х2 е X с началом в момент времени t0 е N на периодическом динамическом графе GT(X,U,f,r,l). Рассмотрим отрезок этого пути :[w,,w2]N->С/eiV), соединяющий вершины у1 и у2. Для того, чтобы отрезок являлся кратчайшим путем из ух в у2, достаточно выполнение условия tx=tQ+nx-1.

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

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

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

Во второй главе определены и исследованы ориентированные графы с ограниченными достижимостями. Введены четыре типа магнитной достижимости (на начальном и конечном отрезках пути с параметром п0, на отрезке натурального ряда (wl5«2L> магнитная достижимость, возникающая ; после я0 шагов). Показано, что магнитная достижимость на начальном отрезке пути, а также достижимость, возникающая после п0 шагов, являются частными случаями достижимости на отрезке \пх,п2]N.

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

В отличие от магнитных достижимостей, описанных в [3-6, 12—19, 38— 39, 41-42], в настоящей работе рассмотрены случаи, когда магнитные ограничения действуют не на всем протяжении пути, а лишь на некотором его отрезке. Такие достижимости названы ограниченными магнитными достижимостями. Рассмотрены три вида достижимостей - на начальном отрезке пути длины и0, на конечном отрезке пути длины п0, магнитная достижимость, возникающая после п0 шагов и магнитная достижимость на отрезке натурального ряда [и,,и2]N. Соответствующие графы обозначаются

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

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

Теорема 2.2.1. Пусть GM(X,U,f) — граф с магнитной достижимостью, G4{X\U%\f*) — граф, построенный по графу GM. На графе GM существует допустимый путь из вершины х еХ в вершину у еX тогда, и только тогда, когда на графе G' существует путь из вершины х е Xх в одну из вершин у е X' или у + \Х\ е Х\

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

Теорема 2.3.1. Величина максимального потока в сети GM(X,U,f,c) равна пропускной способности минимального магнитного разреза, т.е. существует поток fl*, такой что d(fl*)j= maxd(/7) = rmnс{Р).

На графах с ограниченными магнитными достижимостями не все пути являются допустимыми, поэтому классические алгоритмы поиска максимального потока ([2, 11, 20-22]) к таким графам неприменимы. Для решения потоковой задачи на таких графах предлагается искать максимальный поток на вспомогательном графе. Для каждого вида достижимости приведены соответствующие алгоритмы.

В процессе построение вспомогательного графа возникает вопрос о переносе пропускной способности дуги исходного графа на порожденные ею дуги вспомогательного графа. Если положить пропускную способность каждой порожденной дуги равной пропускной способности исходной дуги, то возможна ситуация, когда по дуге исходного графа проходит поток, величина которого больше, чем пропускная способность данной дуги. Для решения этой проблемы в [37] введено понятие множества связанный дуг (т.е. дуг, порожденных одной и той же дугой исходного графа), и вместо пропускных способностей отдельных дуг рассматривается суммарная пропускная способность множества связанных дуг. Для решения задачи о максимальном потоке для графов со связанными дугами в [37—38] описан алгоритм прорыва.

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

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

Теорема 2.4.1. Кратчайшему пути длины п < п0 на графе G^{X,U,f,l) из вершины s&X в вершину /еХ соответствует кратчайший путь из вершины s в подмножество вершин [t,t + |.АГ)} на вспомогательном графе

G(X\U\f).

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

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

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

Монотонная достижимость является обобщением магнитной достижимости на случай, когда множество дуг графа разбивается на R + 1 R попарно непересекающихся подмножеств U = U0 U((Jt/,). Путь на графе с

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

Рассмотрено четыре типа монотонной достижимости: на начальном и конечном отрезках пути длины п0, монотонная достижимость, возникающая после и0 шагов, и монотонная достижимость на отрезке [пх,п2]N. Графы с соответствующим типом достижимости обозначаются ^^яоХ^^У),

G^molXMf) и QwlmolX'U'f). Сформулирована теорема о связи достижимости на графах ^\ топ и G^ mon.

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

Теорема 2.2.1. На графе G(X,U,f) с монотонной достижимостью существует допустимый путь из вершины х е X в вершину у е X тогда, и только тогда, когда на графе G\X\U\f) существует путь из вершины х в подмножество вершин у + к- \Х\,к = 0,l,.,i? -1.

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

Теорема 3.3.1. Величина максимального потока в сети GMon(X,U,f,c) равна пропускной способности минимального монотонного разреза, т.е. существует поток fl*, такой что d{fl*}= maxd{fl) — nunc{P).

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

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

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

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

Выход

После выбора типа монотонной достижимости открывается окно для заполнения информации об исходном графе: fe^r'.I.JfSW.Ijj^^J.^i^jllilsiJUi; 1 начальном отрезке с параметром гЮ ЩР^М пС 1

Начдуги Кон дуги Тип Длина Проп. спос Вероятн

Ввести Вспомогательный граф

Кратч. пути Макс поток Вер перехода

Назад

Нажав кнопку «Вспомогательный граф», можно получить список дуг графа G':

-.' - .j J J nO n1 n2 3

Начдуги Кон дуги Тип Длина Проп спос Вероягн

Кратч пути Макс поток Вер. перехода

G"

11 6)391 (2, 7) 6 4 0,5 [2,8)6 7 0,5 (1 12)972 (13,14)391 (14 15)64 05 (14 16)6 7 0,5

Назад

Заключение

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

Для описанных видов ограничений разработаны алгоритмы решения задач о кратчайших путях, максимальном потоке и случайных блужданиях. Построена математическая модель периодической динамической сети, введены понятия максимального динамического потока, исходящего из t gN источника в момент времени 0 и максимального динамического потока из источника, приходящего в сток в момент времени ^ е ^ и разработаны алгоритмы их нахождения. Алгоритмы, предложенные в работе, реализованы в виде комплекса программ, приведенного в приложении.

1. Андерсон, Джеймс А. Дискретная математика и комбинаторика: пер. с англ./ Джеймс А. Андерсон. - М.: Издательский дом «Вильяме», 2003.- 960с.

2. Басакер Р.Д., Саати Т.Л. Конечные графы и сети: Пер. с англ. — М.: Наука, 1974. -366с.

3. Басангова Е.О., Ерусалимский Я.М. Смешанная достижимость на частично ориентированных графах.//В сб. Вычислительные системы и алгоритмы. Ростов-на-Дону, РГУ. 1983. -с. 135-140.

4. Басангова Е.О., Ерусалимский Я.М. Различные виды смешанной достижимости.//В сб. Алгебра и дискретная математика. Элиста, КГУ. 1985. —с.70-75.

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

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

7. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения. — М: Наука, 1991. -384с.

8. Гаджинский A.M. Основы логистики. — М. Маркетинг, 1995.

9. Дейтел Х.М., Дейтел П.Дж. Как программировать на С++: Пер. с англ.- М.: ЗАО «Издательство БИНОМ», 2000г. 1024с.

10. Ерусалимский Я.М. Эйлеровость графов со смешанной достижимостью.// в сб. Модели, графы и алгебраические структуры. Элиста, 1989. -с. 45-48.

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

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

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

14. Ерусалимский Я.М., Петросян А.Г. Случайные процессы в сетях с биполярной магнитностью.//Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2005, №11, -с. 10-16.

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

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

17. Зыков А.А. Теория конечных графов. — Новосибирск: Наука, 1969. -543с.22.3ыков А.А. Основы теории графов. М: Наука, 1987. -384с.23 .Климов Г.П. Теория вероятностей и математическая статистика. М.: МГУ, 1983. -394с.

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

19. Круглински Д., Уингоу С., Шеферд Дж. Программирование на Microsoft Visual С++ 6.0 для профессионалов. Пер. с англ. — СПб: Питер; М.: Издательско-торговый дом «Русская Редакция», 2001. — 864с.: ил.

20. Кузьминова М.В. Динамические периодические графы.// в сб. Современные методы теории краевых задач. Материалы Воронежской весенней математической школы «Понтрягинские чтения ХУШ». Воронеж, 2007. -с. 97-98.

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

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

23. Миротин Л.Б., Ташбаев Ы.Э. Логистические системы в технологии перевозочного процесса на транспорте, основанные на лошстике/ЛГранспорт: наука, техника, управление. — №2. — 1993.

24. Николайчук В.Е. Логистика. — СПб: Питер, 2002. 160с.

25. Новиков, Ф.А. Дискретная математика для программистов: учебник . для вузов / Ф.А. Новиков. — 2-е изд. — СПб.: Питер, 2005. — 364 с.35.0ре О. Теория графов. Пер: с англ. М: Наука, 1980: -334с.----

26. Петросян А.Г. Многопродуктовые потоки в сетях с ограничениями на достижимость//в сб. Математические методы в современных и классических моделях экономики и естествознания. Ростов-на-Дону,2005, -с.136-138.

27. Петросян А.Г. Потоковая задача в многопродуктовых сетях с нестандартной достижимостью.//В сб. Современные проблемы математического моделирования. Ростов-на-Дону, 2005, -с.334-340.

28. Петросян А.Г. Потоки в сетях с биполярной достижимостью./ТИзвестия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение.2006, №3, -с.32-37.

29. Промыслов В.Д., Жученко И.А. Логистические основы управления материальными и денежными потоками. Нефтегаз, 1994.

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

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

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

33. Форд JI.P., Фалкерсон Д.Р. Потоки в сетях. Пер. с англ. М.: Мир, 1996. -334с.

34. Федотов В.Н. Методы оптимизации потоков информации в управлении производством. — М.: Экономика, 1970.

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

36. Харари Ф. Теория графов. Пер. с англ. — М.: Мир, 1973. -300с.

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

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

39. Е. A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Math. Dokl., 11:1277-1280, 1970.

40. A. V. Goldberg and R. E. Taijan. A New Approach to the Maximum Flow Problem. J. Assoc. Comput. Mach., 35:921-940, 1988.

41. J. C. Picard and H. D. Ratliff. Minimum Cuts and Related Problems. Networks, 5:357-370, 1975.

42. R. Burioni and D. Cassi. Random Walks on Graphs: Ideas, Techniques and Results.