О заполнении вершин ориентированного графа

Размещено на http://www.allbest.ru/

О заполнении вершин ориентированного графа

В.В. Орлов

Аннотация

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

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

В последнее время наметился переход от собственно теории графов к изучению процессов на графах, когда объектом изучения является не сам граф и его свойства, а процесс, рассматриваемый на нем, т.е. сам граф выступает "основой", на которой развивается процесс. Началом такого подхода следует считать работы Форда Д., Фалкерсона по теории потоков в сетях ([1]). Сегодняшний этап развития такого подхода связан с рассмотрением ресурсных сетей (О.П. Кузнецов, Л.Ю. Жилякова [2]-[6]), графов с ограничениями на достижимость (Ерусалимский Я.М., Скороходов В.А. [7]-[11], дифференциальных уравнений на графах ([12]-[19]). Обзор последних результатов по динамическим графовым моделям и процессам сделан в [20].

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

Насколько нам известно, подобные задачи ранее не рассматривались, поэтому нам придется давать определения, вводить новые понятия и т.п. Мы постарались свести их объем к минимуму, а везде где возможно использовать общепринятую терминологию из теории графов и сетей (см. [1]).

Пусть - граф, - множество вершин, - множество дуг, - отображение инцидентности (см.[2]). Мы будем рассматривать задачи о заполнении потоком вершин графа.

На графе заданы пропускные способности дуг , ёмкости вершин - .

Время дискретно . Обозначим через - количество вещества потребленного вершиной за время .

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

.

Таким образом, - множество дуг, заканчивающихся в вершине .

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

.

Таким образом, - множество дуг, начинающихся в вершине .

Определение 1. Вершина называется источником, если

, а .

Определение 2. Вершина ориентированного графа называется стоком, если

и .

Определение 3. Пусть - вершина графа, , Добавим вершину на граф, соединив её дугой с вершиной (с началом в ). В этом случае будем говорить, что она подключена к вершине .

Ясно, что подключаемая вершина ориентированного графа является источником.

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

Возможное обозначение Здесь через обозначено множество подключенных вершин, а - расширение на .

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

Определение 5. Вершина называется потребителем в момент времени , если , т.е. если её максимальная ёмкость ещё не достигнута.

Определение 6. Вершина называется транзитёром с момента , если

.

Будем считать, что - время. Определим множество источников на графе - , множество стоков обозначим (оно может быть и пустым. Множество будем называть множеством промежуточных вершин.

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

1. .

2. Для любой промежуточной вершины и любого выполнено

1. ,

где - количество потреблённого вещества в момент времени .

Обозначим через - количество вещества потребленного вершиной за время , т.е.

.

3. Для любой вершины и любого .

В рассматриваемой задаче будем дополнительно считать, что выполнено условие 4 - "жадности вершин":

То есть потребление в вершине становится равным нулю

(),

когда вершина заполнена и превратилась в транзитёра. Ясно, что с этого момента

.

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

.

Пример 1.

Рис. 1

Пусть - подключаемая вершина, ёмкость вершин и дуг равна 1, тогда динамический поток можно определить следующей таблицей:

Время ()
0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	1	0	0	0	0
2	1	0	0	0	0	0	1	0	0	0	0
3	1	0	0	0	0	0	1	1	0	0	0
4	1	1	0	0	0	0	1	1	0	0	0
5	1	1	0	0	0	0	1	1	1	0	0
6	1	1	1	0	0	0	1	1	1	0	0
7	1	1	1	0	0	0	1	1	1	1	0
8	1	1	1	1	0	0	1	1	1	1	0
9	1	1	1	1	1	0	1	1	1	1	0
10	1	1	1	1	1	0	1	1	1	1	1
11	1	1	1	1	1	1	1	1	1	1	1

Из таблицы видно, что процесс заполнения графа является пошаговым: процесс начинается с заполнения самого источника и далее, поочерёдно, заполняются все вершины графа. После определения потока на шагах 0, . . ., k можно определить значение потока и на k+1 шаге.

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

Сформулируем потоковые задачи.

Задача №1.

Как назначить источников и какой максимальной мощности они должны быть, чтобы все вершины полностью заполнились за наименьшее время?

Рассмотрим случай с одним источником: . Пусть граф является корневым ориентированным деревом. Ёмкости вершин заданы.

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

Определение 9. Висячая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой ордерева. Расстояние от корня до некоторой вершины называется уровнем вершины. Сам корень имеет уровень 0. Вершины одного уровня образуют ярус дерева.

Определение 10. Большой веткой дерева называется единственный путь до конечной "висячей" вершины дерева, которая не имеет исходящих дуг.

Определение 11. Ветка называется заполненной, если все её вершины заполнены.

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

При таком подключении рассмотрим следующие случаи.

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

Теорема 1. В указанных выше предположениях (Случай 1) время заполнения дерева равно сумме емкостей всех его вершин плюс количество дуг, то есть n-1:

(1)

Пример 2.

Рис. 3

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

.

Случай 2.

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

Теорема 2. В сформулированных выше условиях имеет место:

, (2)

где - время заполнения графа, - время заполнения ветки графа.

Теорема 3.

 (3)

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

.

Случай 3.

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

Определение 12.

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

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

Теорема 4.

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

Случай 4.

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

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

Пример 3.

Пусть дерево имеет вид:

Рис. 4

Если бы мы считали время заполнения дерева с учётом вершин нулевой ёмкости, то . Хотя на самом деле - , а само дерево следует рассматривать в таком виде:

Рис. 5

Заметим, что в Примере 3 нам не удалось убрать одну нулевую вершину так она не являлась висячей ни на одном из этапов "обрезки".

Определение 13.

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

Для деревьев с внутренними вершинами нулевой ёмкости также справедлива формула (1).

Случай 5.

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

В таком случае мы можем получить ориентированное растущее покрывающее дерево с висячими вершинами, ёмкости которых равны 0. Каждая такая вершина увеличивает время заполнения дерева на 1. Поэтому, в алгоритм поиска покрывающего дерева необходимо добавить шаг - исключение всех нулевых висячих вершин по аналогии со Случаем 4.

Пример 4.

Пусть сильно связный граф имеет вид:

Рис. 6

Ёмкости вершин равны:

.

Тогда, покрывающее дерево растущее из вершины имеет вид:

Рис. 7

Если бы мы считали время заполнения дерева с учётом висячей нулевой вершины, то . Хотя на самом деле - , а само дерево следует рассматривать в таком виде:

Рис. 8

Если покрывающее дерево имеет корень в вершине ,то оно имеет вид:

Рис. 9

В этом случае и уменьшить данное время мы уже не можем.

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

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

Задача о решена.

Литература

1. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. - Москва: Мир, 1966, 276 c.

2. Жилякова Л.Ю., Кузнецов О.П. Теория ресурсных сетей: монография // М.: РИОР: ИНФРА-М, 2017. - 283 с.

3. Жилякова Л.Ю. Эргодические циклические ресурсные сети. I. Колебания и равновесные состояния при малых ресурсах // Управление большими системами. Выпуск 43, М.: ИПУ РАН, 2013. С. 34 - 54.

4. Жилякова Л.Ю. Эргодические циклические ресурсные сети. II. Большие ресурсы // Управление большими системами. Выпуск 45, М.: ИПУ РАН, 2013, С. 6 -29.

5. Oleg P. Kuznetsov, Ludmila Yu. Zhilyakova. Nonsymmetric resource networks. The study of limit states. // Management and Production Engineering Review. Volume 2, Number 3, September 2011. - pp. 33-39

6. Теория ресурсных сетей: монография / Л.Ю. Жилякова, О.П. Кузнецов. - М. : РИОР : ИНФРА-М, 2017. - 283 с. - (Научная мысль). - URL: doi.org/10.12737/21451.

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

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

9. Ерусалимский Я.М. Случайные блуждания по графу-решётке и комбинаторные тождества// Инженерный вестник Дона, 2015, №2 ч.2 URL: ivdon.ru/ru/magazine/archive/n2p2y2015/2964.

10. Erusalimskiy, I. On the Dynamic Flows in Networks//Universal J. of Communications and Network, 2014, v2, #6, - pp. 101 - 105, DOI: 10.13189

11. Ерусалимский Я.М. Графы с затуханием на дугах и усилением в вершинах и маршрутизация в информационных сетях// Инженерный вестник Дона, 2015, №1 URL: ivdon.ru/ru/magazine/archive/n1y2015/2782

12. Покорный Ю.В. Дифференциальные уравнения на геометрических графах/ Ю.В. Покорный, О.М. Пенкин, А.В. Боровских и др./ - М.: Физматлит, 2004. --272 с.

13. V.S. Rabinovich, S. Roch, Essential spectra of difference operators on Z?-periodic graphs, J. of Physics A: Math. Theor. ISSN 1751-8113, 40 (2007) pp.10109--10128

14. V. Rabinovich, S. Roch, Pseudodifferential Operators on Periodic Graphs, Integral Equations and Operator Theory, Volume 72, Number 2 (2012), 197-217, DOI: 10.1007/s00020-011-1924-x DOI 10.1007/s00020-011-1924-xc, Springer Basel AG, 2011, pp. 1-22

15. V. Rabinovich, Diffraction by periodic graphs, Complex Variables and Elliptic Equations, http://dx.doi.org/10.1080/17476933.2013.767801, 2013,Volume 59, Issue 4, April 2014, pp. 578-598

16. V. Rabinovich, On Boundary Integral Operators for Diffraction Problems on Graphs with Finitely Many Exits at Infinity, ISSN 1061-9208, Russian Journal of Mathematical Physics, Vol. 20, No. 4, 2013, pp. 508-522.

17. V. Rabinovich, Acoustic Diffraction Problems on Periodic Graphs, Functional Analysis and Its Applications, Vol. 48, No. 4,, 2014, Translated from Funktsionanyi Analiz i Ego Prilozheniya, Vol. 48, No. 4, pp. 70-74, 2014

18. Провоторов В.В. Собственные функции задачи Штурма-Лиувилля на графе-звезде / В.В. Провоторов // Математический сборник. - 2008. - Т. 199, № 10. - С. 105-126.

19. Провоторов В.В. Собственные функции краевых задач на графах и приложения: монография/ В.В. Провоторов. - Воронеж: Научная книга, 2008. - 247 с.

20. Жилякова Л.Ю. Графовые динамические модели и их свойства // Автоматика и телемеханика, 2015, № 8, с.115-139.

21. Ерусалимский Я.М., Степовой Д.В. Потенциальный оператор, функция Грина на ориенти- рованных графах и некоторые их приложения в квантовой механике // Известия вузов. Северо- Кавказский регион. Естестественные науки. - 2001, спецвыпуск. - pp. 67-71.

22. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. - 3-е издание изд. - Москва: Вузовская книга, 2000. - 288 c.

23. Байрактаров Б.Р., Кудаев В.Ч., "Алгоритм "веерной" оптимизации параметров разветвленных трубопроводных сетей", Известия Высших учебных заведений. Северо-Кавказский регион. Естественные науки Ростов-на-Дону, 2005, № 2, pp. 2-5.

24. Байрактаров Б.Р., "Задача распределения потоков в кольцевых трубопроводных сетях". Известия Высших учебных заведений. Северо-Кавказский регион. Естественные науки. Приложение 1-05. Ростов-на-Дону, 2005, № 1'05, pp. 3-9.

25. Кудаев В.Ч. Задачи оптимального проектирования сетей Киргхофа: автореферат диссертации кандидата физико-математических наук: 05.13.16.- Ростов-на-Дону, 1993.- 18 с.

References

1. Ford L.R., Falkerson D.R. Potoki v setyakh [Streams in networks]. Moskva: Mir, 1966, p. 276.

2. Zhilyakova L. Yu., Kuznetsov O.P. Teoriya resursnykh setey: monografiya [Theory of resource networks: monograph] // M.: RIOR: INFRA-M, 2017. 283 p.

3. Zhilyakova L. Yu. Upravlenie bol'shimi sistemami. Vypusk 43, M.: IPU RAN, 2013. pp. 34 - 54.

4. Zhilyakova L. Yu. Upravlenie bol'shimi sistemami. Vypusk 45, M.: IPU RAN, 2013, pp. 6 -29.

5. Oleg P. Kuznetsov, Ludmila Yu. Zhilyakova. Management and Production Engineering Review. Volume 2, Number 3, September 2011. - pp. 33-39

6. Teoriya resursnykh setey: monografiya [Theory of resource networks: monograph] L. Yu. Zhilyakova, O.P. Kuznetsov. M.: RIOR: INFRA M, 2017. 283 p. (Nauchnaya mysl'). URL: doi.org/10.12737/21451.

7. Erusalimskiy Ya.M. Izvestiya vuzov. Severo-Kavkazskiy region. Estestvennye nauki, 2003, №2. pp. 3 -5.

8. Erusalimskiy Ya.M. Grafy s nestandartnoy dostizhimost'yu. Zadachi, prilozheniya: monogr. [Graphs with non-standard attainability. Tasks, applications: monogr.] Ya.M. Erusalimskiy, V.A. Skorokhodov, M.V. Kuz'minova, A.G. Petrosyan. Rostov-na-Donu: YuFU, 2009. 195p.

9. Erusalimskiy Ya.M. Inћenernyj vestnik Dona (Rus), 2015, №2 part 2. URL: ivdon.ru/ru/magazine/archive/n2p2y2015/2964.

10. Erusalimskiy, Ya.M. Universal J. of Communications and Network, 2014, v2, #6, pp. 101 - 105, DOI: 10.13189

11. Erusalimskiy Ya.M. Inћenernyj vestnik Dona (Rus), 2015, №1. URL: ivdon.ru/ru/magazine/archive/n1y2015/2782

12. Pokornyy Yu.V. Differentsial'nye uravneniya na geometricheskikh grafakh [Differential equations on geometric graphs]. Yu. V. Pokornyy, O. M. Penkin, A. V. Borovskikh i dr. M.: Fizmatlit, 2004. 272 p.

13. V.S. Rabinovich, S. Roch, Essential spectra of difference operators on Z?-periodic graphs, J. of Physics A: Math. Theor. ISSN 1751-8113, 40 (2007) pp.10109--10128

14. V. Rabinovich, S. Roch, Pseudodifferential Operators on Periodic Graphs, Integral Equations and Operator Theory, Volume 72, Number 2 (2012), 197-217, DOI: 10.1007/s00020-011-1924-x DOI 10.1007/s00020-011-1924-xc, Springer Basel AG, 2011, pp. 1-22

15. V. Rabinovich, Diffraction by periodic graphs, Complex Variables and Elliptic Equations, http://dx.doi.org/10.1080/17476933.2013.767801, 2013,Volume 59, Issue 4, April 2014, pp. 578-598

16. V. Rabinovich, On Boundary Integral Operators for Diffraction Problems on Graphs with Finitely Many Exits at Infinity, ISSN 1061-9208, Russian Journal of Mathematical Physics, Vol. 20, No. 4, 2013, pp. 508-522.

17. V. Rabinovich, Acoustic Diffraction Problems on Periodic Graphs, Functional Analysis and Its Applications, Vol. 48, No. 4, 2014, Translated from Funktsionanyi Analiz i Ego Prilozheniya, Vol. 48, No. 4, pp. 70-74, 2014

18. Provotorov V.V. Matematicheskiy sbornik. 2008. T. 199, № 10. pp. 105-126.

19. Provotorov V.V. Sobstvennye funktsii kraevykh zadach na grafakh i prilozheniya: monografiya [The eigenfunctions of boundary value problems on graphs and applications: monograph] Voronezh: Nauchnaya kniga, 2008. 247 p.

20. Zhilyakova L. Yu. Avtomatika i telemekhanika, 2015, № 8, pp.115-139.

21. Erusalimskiy Ya.M., Stepovoy D.V. Izvestiya vuzov. Severo- Kavkazskiy region. Estestestvennye nauki. 2001, spetsvypusk. pp. 67-71.

22. Erusalimskiy Ya.M. Diskretnaya matematika: teoriya, zadachi, prilozheniya [Discrete mathematics: theory, problems, and applications]. 3-e izdanie izd. Moskva: Vuzovskaya kniga, 2000. 288 p.

23. Bayraktarov B.R., Kudaev V. Ch. Izvestiya Vysshikh uchebnykh zavedeniy. Severo-Kavkazskiy region. Estestvennye nauki Rostov-na-Donu, 2005, № 2, pp. 2-5.

24. Bayraktarov B.R. Izvestiya Vysshikh uchebnykh zavedeniy. Severo-Kavkazskiy region. Estestvennye nauki. Prilozhenie 1-05. Rostov-na-Donu, 2005, № 1'05, pp. 3-9.

25. Kudaev V. Ch. Zadachi optimal'nogo proektirovaniya setey Kirgkhofa: avtoreferat dissertatsii kandidata fiziko-matematicheskikh nauk: 05.13.16 [Problems of the optimal design of Kirghof's networks: the abstract of the dissertations the candidate of physical and mathematical sciences: 05.13.16]. Rostov-na-Donu, 1993. 18 p.

Размещено на Allbest.ru

...