Russian Psychological Issues
JournalsTopicsAuthorsEditor's Choice For AuthorsAbout PsyJournals.ruContact Us

Previous issue (2021. Vol. 11, no. 1)

Modelling and Data Analysis

Publisher: Moscow State University of Psychology and Education

ISSN (printed version): 2219-3758

ISSN (online): 2311-9454


License: CC BY-NC 4.0

Started in 2011

Published 4 times a year

Free of fees
Open Access Journal


An Algorithm for Covering the Vertices of a Directed Graph 13


Knyazyatov M.O.
student, Moscow aviation Institute (MAI), Moscow, Russia

Rasskazova V.A.
PhD in Physics and Matematics, Associate Professor of Department 804 "Probability Theory and Computer Modeling", Moscow Aviation Institute, (NRU MAI), Moscow, Russia

The article presents an algorithm for solving the applied problem of assigning and moving locomotives, based on the solution of the graph–theoretic problem of covering the vertices of a directed graph with a set of oriented paths. A detailed example is given for an algorithm for covering the vertices of a directed graph with a set of maximal paths.

Keywords: covering the vertices of the graph, moving locomotives, set of paths

Column: Optimization Methods


For Reference

  1. Lazarev A.A. Estimates of the absolute error and a scheme for an approximate solution to scheduling problems // Computational Mathematics and Mathematical Physics volume49, p. 373–386 (2009).
  2. Lazarev A.A., Gafarov E.R. Transformation of the network graph of scheduling problems with precedence constraints to a planar graph // Doklady Mathematics. 2009. Т. 79. № 1. С. 1–3.
  3. Burdett O., Kozan E. A Disjunctive Graph Model and Framework for Constructing New Train Schedules // Eur. J. Oper. Res. 2010. V. 200. P. 85–98.
  4. Gholami O., Sotskov Y. N. Mixed Graph Model and Algorithms for Parallel Machine Job shop Scheduling Problems // Int. J. Production Research. 2015. V. 8. P. 1–16.
  5. Lusby R., Ryan D. Railway Track Allocation: Models and Methods // Oper. Res. Spektrum. 2011. V. 33. P. 843–883.
  6. Gainanov D.N., Rasskazova V.A. Mathematical modelling of locomotives’ traffic problem by graph theory and combinatorial optimization methods // Moscow Aviation Institute. 2017. № 92.
  7. Gainanov D.N. Combinatoirial geometry and graphs in an analysis of infeasible systems and pattern recognition. M.: Nauka=M.: Science, 2014, 152 p.
  8. Gainanov D.N., Kibzun A.I., Rasskazova V.A. Theoretical-graph Algorithm in the Problem on the Assignments and Transportations of Locomotives // Vestnik computernykh I informatsionnykh tekhnologiy= Bulletin of Computer and Information Technologies. 2017. № 5. p. 51–56.
  9. Gainanov D.N., Rasskazova V.A.. An inference algorithm for monotone boolean functions associated with undirected graphs // Bulletin of the South Ural State University Series Mathematical Modelling Programming and Computer Software. 2016. T. 9. № 3. p. 17–30.

© 2007–2021 Portal of Russian Psychological Publications. All rights reserved in Russian

Publisher: Moscow State University of Psychology and Education

Catalogue of academic journals in psychology & education MSUPE

Creative Commons License Open Access Repository     Webometrics Ranking of Repositories

RSS Psyjournals at facebook Psyjournals at Twitter Psyjournals at Youtube ??????.???????