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

Ориентированные графы широко используются для моделирования различных классов объектов и процессов. Наиболее часто на графах рассматриваются задача о достижимости (т.е. существовании пути между двумя вершинами), Марковские процессы (т.е. задача о случайном блуждании частицы на графе с заданными на дугах вероятностями) и задача построения максимального потока в ориентированной сети. В классической постановке все вышеперечисленные задачи хорошо изучено и широко применяются в различных областях. Наиболее существенными в этой области являются работы Басакера Р. Д., Ерусалимского Я. М., Замбицкого Д. К., Зыкова А. А., Лозовану Д. Д., Кристофидеса Н., Оре О., Саати Т. Л., Свами М., Тхуласирамана К., Фалкерсона Д. Р., Форда Л.Р.([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 (< п) пути Ц связана числовая характеристика 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 также рассмотрена задача о случайном блуждании частицы на графе с условием барьерной достижимости. Ясно, что процесс случайного блуждания на таком графе не является Марковским, так как переходы определяются не только вероятностями переходов, но и значением величины барьерного показателя. Для сведения данного процесса к Марковскому предлагается следующий подход: производится построение вспомогательного графа GXUf%). На вспомогательном графе специальным образом задаются вероятности перехода: и • Р (и') = Р (и)<~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.

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

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

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

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

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

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с..