In the present paper, a universal approach for determining the maximum flow problem in directed graph for solving different problems is applied. It can be considered as a heuristic and it can be used as a denomination for analyzing an arbitrary system with a mathematical description as a directed graph. The physical nature of the flows passing through the arcs of the system considered can be energy, information, transportation, or material. Then the studied system will be power, communication, transport, or manufacturing, respectively. In the present article five types of maximum flow problems are considered. Each of them is solved analytically by the universal heuristic method. The common between these problems is expressed in the fact that its behavior can be presented with the same mathematical model in the form of a directed graph including one initial (pending) vertex and one final (blocked) vertex, respectively. These vertexes are called either real (if they exist) or fictive (if they are introduced additionally) source and receiver depending on the topology of the associated directed graph’s model. The final solution obtained with this approach for Problem 1 is compared with the similar one found through Ford-Fulkerson’s, Edmonds-Karp’s and Dinic’s algorithms and it has been shown to be better than those determined by them.
展开▼
