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

• Петросян, Артем Георгиевич
• кандидат физико-математических наук
• 2006

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

Содержание.

Введение.

Глава 1. Ориентированные графы с барьерной достижимостью.

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

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

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

1.3.1. Случайные процессы, классическая постановка.

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

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

1.4.1. Основные понятия, определения и утверждения.

1.4.2. Потоки в сетях с барьерной достижимостью.

Глава 2. Ориентированные графы с биполярной магнитностью.

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

2.2. Случайные процессы на графах с биполярной магнитностью.

2.3. Потоковая задача в сетях с биполярной магнитностью.

Глава 3. Многопродуктовые потоки мультисетях.

3.1. Постановка задачи.

3.2. Алгоритм построения максимального потока в многопродуктовой мультисети.

3.3 Теорема Форда-Фалкерсона для мнопродуктовых мультисетей.

Введение диссертации (часть автореферата) на тему «Новые виды достижимости и математические модели многопродуктовых потоков в мультисетях»

Ориентированные графы широко используются для моделирования различных классов объектов и процессов. Наиболее часто на графах рассматриваются задача о достижимости (т.е. существовании пути между двумя вершинами), Марковские процессы (т.е. задача о случайном блуждании частицы на графе с заданными на дугах вероятностями) и задача построения максимального потока в ориентированной сети. В классической постановке все вышеперечисленные задачи хорошо изучено и широко применяются в различных областях. Наиболее существенными в этой области являются работы Басакера Р.Д., Ерусалимского Я.М., Замбицкого Д.К., Зыкова А.А., Лозовану Д.Д., Кристофидеса Н., Оре О., Саати Т.Л., Свами М., Тхуласирамана К., Фалкерсона Д.Р., Форда Л.Р.([1],[7],[15],[16],[17],[19],[21],[25],[28]).

В отличии от классической постановки в работах [2]-[5],[8],[9],[12]-[14], [26], [27] перечисленные задачи рассматриваются на графах с ограничениями на достижимость. Это такие графы, в которых не все пути являются допустимыми, а, следовательно, известные алгоритмы для решения этих задач неприменимы. Такие графы мы называем орграфами с нестандартной достижимостью. Такое обобщение классического понятия позволяет расширить область применения графовых моделей и методов, в том числе к задачам маршрутизации в сетях с участками затухания и участками усиления сигнала, к нахождению кратчайших путей выполнения технологических процессов, в которых имеются ограничения на порядок (последовательность) выполнения некоторых операций или их совместимость, к нахождению вероятностей в задачах случайного блуждания частицы, когда имеются переходы, влияющие на ее свойства.

Впервые графы с ограничениями на достижимость рассматривались в работах Басанговой Е.О. и Ерусалимского Я.М. ([2]-[5]). Подход к решению подобных задач очень подробно описан в работах Я.М. и Скороходова В.А. ([12]-[14],[26],[27]), который заключается в построении вспомогательного графа, который взаимнооднозначно связан с исходным, но при этом на нем нет ограничений на достижимость. Алгоритм построения вспомогательного графа определяется конкретным видом ограничений на достижимость. Дальнейшее решение задач ведется на этом вспомогательном графе. Следует отметить, что в результате перестроения на вспомогательном графе возникают так называемые «связанные дуги», в результате чего для построения максимального потока в сети необходимо было существенно модернизировать алгоритм Форда-Фалкерсона. Полученный алгоритм (алгоритм «Прорыва») подробно описан в дипломной работе автора.

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

В первой главе вводится понятие барьерной достижимости на ориентированном графе, у которого множество дуг U = Un U VJ , причем множества попарно непересекающиеся. Множество Uи

- множество нейтральных дуг, т.е. множество, дуги которого подчиняются свойствам стандартной достижимости. Множество U+ - множество дуг, увеличивающих барьерный показатель. Множество UE - множество дуг барьерного перехода. Для удобства дальнейшего описания ограничений, накладываемых на рассматриваемые пути, будем считать, что по дугам графа движется частица, перемещаясь между вершинами графа. С каждым отрезком [i,j]N(\<i< j < п) пути Ц связана числовая характеристика j fi j) = M(m) П t/+ барьерный показатель частицы, m=i тогда если к /-тому шагу путь Ц от своего начала накопил величину барьерного показателя большую либо равную к, то становятся допустимыми для прохождения в последующем этим путем дуги из множества UБ. Пути, удовлетворяющие этому условию мы называем путями длины n(ns N) на графе, допускающими барьерный переход уровня к(к > 1) Существенное отличие данного вида ограничений на достижимость от рассмотренных ранее в [12],[27] заключается в следующем. В отличие от магнитной и вентильной достижимости в случае барьерной достижимости у множества путей имеется транзитивное свойство, т.е. если существует путь из вершины X в вершину у, допускающий барьерный переход, и существует путь из вершины у в вершину Z, допускающий барьерный переход, то существует путь из вершины х в вершину z, допускающий барьерный переход. Кроме этого в условии барьерной достижимости отсутствует директивность при поиске пути, а именно, накопив необходимую для выполнения условия перехода величину барьерного показателя, не обязательно продолжать путь по дугам из множества UБ.

Описан алгоритм перестроения исходного графа, сводящий достижимость вершин исходного графа к достижимости на вспомогательном графе и доказана теорема:

Теорема 1.2.1. Любому пути // на вспомогательном графе G' соответствует путь //, допускающий барьерный переход исходном графе G, и вершина у достижима при условии барьерного перехода уровня к из вершины х на графе G тогда и только тогда, когда на G' достижима из х, по крайней мере, одна из вершин множества Vy = {y,yw•у{к)}.

В главе 1 также рассмотрена задача о случайном блуждании частицы на графе с условием барьерной достижимости. Ясно, что процесс случайного блуждания на таком графе не является Марковским, так как переходы определяются не только вероятностями переходов, но и значением величины барьерного показателя. Для сведения данного процесса к Марковскому предлагается следующий подход: производится построение вспомогательного графа G\X\U\f%). На вспомогательном графе специальным образом задаются вероятности перехода: и • Р(и') = Р(и)<~1-^ , ч)

1. Для wet) (xwj i = 0,k-l: 1- \p(vj)

VjeQ+(x)n(Uc)

2. Для м'е0+(х№): p(u') = p(u).

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

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

Во второй главе вводится понятие биполярной магнитности на ориентированном графе, у которого множество дуг yjU m+\jU м , причем все эти множества попарно не пересекаются. Множество Uн - называется множеством нейтральных дуг, т.е. множеством, дуги которого подчиняются свойствам стандартной достижимости. Множество U+ - называется множеством дуг, увеличивающих положительную магнитность, a U - множеством дуг, увеличивающих отрицательную магнитность. Множество Uи+ - называется множеством дуг положительной магнитности, a UM - множеством дуг отрицательной магнитности. С каждым отрезком [i,j]N(l<i< j<n) пути /л связана числовая характеристика яди)=Zi n u+i" Ei ^ w n 1 величина m=i m=i накопленной биполярной магнитности, тогда , если к / - тому шагу путь // от своего начала накопил магнитность ЯД/) большую либо равную к и среди дуг, выходящих из концевой вершины / - той дуги есть хотя бы одна дуга из множества отрицательной магнитности, то следующая (/ +1 - я) дуга биполярного магнитного пути уровня к обязана быть дугой из множества UM, а если к i - тому шагу путь Ц от своего начала накопил магнитность ЯД0 меньшую либо равную -к и среди дуг, выходящих из концевой вершины / - той дуги есть хотя бы одна дуга из множества положительной магнитности, то следующая (/ + 1 - я) дуга биполярного магнитного пути уровня к обязана быть дугой из множества Uм+. Такое условие называется условием биполярной магнитности уровня к. Задача о биполярной магнитности является существенным уточнением модели, рассмотренной в [26],[27]. Биполярная магнитность, с нашей точки зрения, является более «физичной», так как в нашей задаче частица, которая движется по дугам графа, накопив положительную магнитность, притягивается дугами с отрицательной магнитностью, а дугами с положительной магнитностью -отталкивается и наоборот.

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

Рассмотрена задача о случайном блуждании частицы на графе с условием биполярной магнитности. Такой процесс случайного блуждания не является Марковским. Для сведения данного процесса к Марковскому предлагается следующий подход: производится построение вспомогательного графа G' (X' ,£/',/'). На вспомогательном графе специальным образом задаются вероятности перехода.

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

Теорема 2.3.1. Для любой ориентированной сети с биполярной магнитностью с источником s и стоком t величина максимального потока равна пропускной способности минимального магнитного разреза.

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

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

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

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

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

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

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

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

7. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. -М.: Вузовская книга. 2001. -279с.

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

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

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

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

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

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

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

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

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

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

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

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

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

21. Оре О. Теория графов. Пер. с англ. -М: Наука, 1980. -334с.

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

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

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

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

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

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

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

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

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

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

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

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