Балансировка сетевых объектов

Я. М. Ерусалимский^a, Х. Н. Абдулрахман^b, В. А. Скороходов<sup>a

a</sup> Южный федеральный университет, Институт математики, механики и компьютерных наук им. И. И. Воровича, ул. Мильчакова, 8А, Ростов-на-Дону, 344090, Российская Федерация
^b Ростовский государственный университет путей сообщения, факультет управления процессами перевозок, пл. им. Ростовского стрелкового полка народного ополчения, д.2., Ростов-на-Дону, 344038, Российская Федерация

Аннотация: В статье рассматриваются сетевые объекты - конечные ориентированные графы $G(X,U,f,\rho)$, на дугах которых задана пропускная способность - положительные вещественные числа $p(u)$. Каждой вершине $x$ сопоставляются три локальные характеристики: $\rho_{-}(x)$ - суммарная пропускная способность дуг, входящих в вершину $x$; $\rho_{+}(x)$ - суммарная пропускная способность дуг, исходящих из вершины $x$; $\delta_{\rho}(x) = |\rho_{+}(x) - \rho_{-}(x)|$. Множество вершин графа делится на три подмножества: множество сбалансированных вершин $X_b$, для которых $\delta_{\rho}(x) = 0$; множество дефицитных вершин $X_d$, для которых $\rho_{-}(x) < \rho_{+}(x)$; и множество профицитных вершин $X_p$, для которых $\rho_{-}(x) > \rho_{+}(x)$. Изучаются свойства этих характеристик, в частности, доказывается равенство $\sum_{x \in X_d} \delta_{\rho}(x) = \sum_{x \in X_p} \delta_{\rho}(x)$. Далее вводится понятие сбалансированного сетевого графа, в котором все вершины сбалансированы ($X = X_b$). Это понятие распространяется на классические сети Форда-Фалкерсона (граф сбалансирован, если сбалансированы все промежуточные вершины) и на ресурсные сети Кузнецова-Жиляковой. Показано, что такие сети обладают оптимальными свойствами: например, в сбалансированной сети Форда-Фалкерсона максимальный поток единственен и равен пропускной способности каждой дуги. Для несбалансированных ресурсных сетей Кузнецова-Жиляковой рассматривается и решается задача минимального балансирования. Для несбалансированных сетей Форда-Фалкерсона задача балансирования формулируется и решается с позиций максимизации потока в результирующей сбалансированной сети.

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

УДК: 519.1

MSC: 05C90, 05C82