Balancing network objects

I. M. Erusalimskyi^a, H. N. Abdulrahman^b, V. A. Skorokhodov<sup>a

a</sup> Southern Federal University, Rostov-on-Don
^b Rostov State Transport University

Abstract: The paper considers network objects - finite oriented graphs $G(X,U,f,\rho)$, on the arcs of which the capacity defined - positive real numbers $p(u)$. Each vertex $x$ of the network graph is assigned three local characteristics $\rho_{-}(x)$, $\rho_{+}(x)$ and $\delta_{\rho}(x)$. $\rho_{-}(x)$ is the total capacity of arcs coming to the vertex $x$, $\rho_{+}(x)$ is the total capacity of arcs coming out of vertex $x$, $\delta_{\rho}(x)=|\rho_{+}(x)-\rho_{-}(x)|$. They divide the set of graph vertices into three subsets: the set of balanced vertices $X_{b}$ i.e. $x\in X_{b} \Leftrightarrow \delta_{\rho} (x)=0$, the set of deficient vertices $X_d$ i.e. $x\in X_d \Leftrightarrow \rho_{-} (x)<\rho_{+} (x)$, the set of surplus vertices $X_p$ i.e. $x\in X_p \Leftrightarrow \rho_{-}(x)> \rho_{+} (x)$.
The properties of these characteristics are studied. For example, it is proved that for any network graph is valid the next equality: $\sum_ {x \in {X_d}} {{\delta_\rho}(x )} = \sum_{x \in {X_p} }{\delta_\rho(x)}$. In the next part of the paper, the concept of a balanced network graph is introduced, in which all vertices are balanced $(X= X_b)$. This concept is transferred to classical Ford–Fulkerson networks — it is called balanced if it is balanced in all intermediate vertices, and to Kuznetsov–Zhilyakova resource networks. Such networks are optimal in their design, for example, in a balanced Ford–Fulkerson network the maximum flow is unique, and its value on each arc of the network is equal to its capacity. For an unbalanced Kuznetsov–Zhilyakova resource network, the problem of minimal balancing is considered and solved. For unbalanced Ford–Fulkerson networks, the balancing problem is considered and solved in terms of maximizing the flow in the resulting balanced Ford–Fulkerson network.

Keywords: graph, capacity, network, resource network, network flow.

UDC: 519.1

MSC: 05C90, 05C82