<p>This paper presents concepts of balanced graph objects such as balanced classical networks (in the sense of Ford–Fulkerson networks) and balanced resource networks. The classical balanced networks are a subset of classical networks whose sums of capacities by incoming and outgoing arcs are equal for each intermediate vertex. It is shown that the maximum flow problem is trivially solvable for these networks. Balanced resource networks are tightly coupled with balanced classical networks because they could be obtained from the last ones and vice versa. Exploration of the resource networks along with classical networks is performed to uncover similarity between specific theorems of described balanced graph objects. Resource networks are considered while functioning in discrete time. Theorems on the existence of a stationary functioning mode are proved for balanced and partially balanced resource networks.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

BALANCED NETWORKS AND GRAPHS

  • Iakov M. Erusalimskiy,
  • Vladimir A. Skorokhodov,
  • Vladislav A. Rusakov

摘要

This paper presents concepts of balanced graph objects such as balanced classical networks (in the sense of Ford–Fulkerson networks) and balanced resource networks. The classical balanced networks are a subset of classical networks whose sums of capacities by incoming and outgoing arcs are equal for each intermediate vertex. It is shown that the maximum flow problem is trivially solvable for these networks. Balanced resource networks are tightly coupled with balanced classical networks because they could be obtained from the last ones and vice versa. Exploration of the resource networks along with classical networks is performed to uncover similarity between specific theorems of described balanced graph objects. Resource networks are considered while functioning in discrete time. Theorems on the existence of a stationary functioning mode are proved for balanced and partially balanced resource networks.