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

В статье рассматриваются сетевые объекты -- конечные ориентированные графы $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$). Это понятие распространяется на классические сети Форда--Фалкерсона (граф сбалансирован, если сбалансированы все промежуточные вершины) и на ресурсные сети Кузнецова--Жиляковой. Показано, что такие сети обладают оптимальными свойствами: например, в сбалансированной сети Форда--Фалкерсона максимальный поток единственен и равен пропускной способности каждой дуги. Для несбалансированных ресурсных сетей Кузнецова--Жиляковой рассматривается и решается задача минимального балансирования. Для несбалансированных сетей Форда--Фалкерсона задача балансирования формулируется и решается с позиций максимизации потока в результирующей сбалансированной сети.