On the synthesis of flow networks minimizing the sum of edge capacities

A flow network is a graph with a positive capacity for each edge. It can be used as a model for communication networks. Between a pair of vertices, the maximum flow in a flow network represents the communication capacity in the communication network. A terminal capacity matrix is defined for a flow network such that the (i,j) element is the maximum flow between vertex i and vertex j. For undirected networks, some synthesis methods have been proposed which do not only realize a given terminal capacity matrix but also minimize the sum of the edge capacities. Note that there are many flow networks for a terminal capacity matrix with the minimum edge capacities. The methods so far do not cover all of them. That is, there exist some networks which none of the known methods can construct. This paper proposes a new synthesis method which can construct any such an undirected flow network. [In Japanese.]