Practical Realization of Algorithm of Oriented Graph Paths Decomposition

This study aims to clarify the methodological status program realization of oriented graph paths decomposition. Algorithms of matrix formulation of decomposition table M from multitude of paths, table sorting by NΣ and balance computing explored. On the basis of those algorithms and original algorithm of oriented graph paths decomposition realized Python 3 program. Results for random-generated graph size of 100 vertices computed and time measured. The results obtained can be used to solve the problem of organizing freight rail transportation at the stage of assignment and movement of locomotives. The scientifi c and practical novelty of the work lies in a signifi cant reduction in the dimension of the original problem, which is especially important in the conditions of transport networks of complex topology.

1. Gainanov D.N., Konygin A.V., Rasskazova V.A. Modelling railway freight traffi c using the methods of graph theory and combinatorial optimization. Automation and Remote Control, 2016 vol. 77, no. 11, pp. 1928–1943.
2. Gainanov D.N., Kibzun A.I., Rasskazova V.A. Theoretical-graph algorithm in the problem on the assignments and transportations of locomotives. Herald of computer and information technologies, 2017, no. 5, pp. 51–56.
3. Gainanov D.N., Kibzun A.I., Rasskazova V.A. The Decomposition Problem for the Set of Paths in a Directed Graph and Its Application. Automation and Remote Control, 2018, vol. 79, no. 12, pp. 2217–2236.