Research ArticleOpen AccessGoogle Scholar indexed
The Software for Constructing Trails with Local Restrictions in Graphs
Department of Mathematical Methods in Economics and Statistics, South Ural State University, Chelyabinsk, Russian Federation
Department of Mathematical Methods in Economics and Statistics, South Ural State University, Chelyabinsk, Russian Federation
- 1 Department of Mathematical Methods in Economics and Statistics, South Ural State University, Chelyabinsk, Russian Federation
- 2 Department of Mathematical Methods in Economics and Statistics, South Ural State University, Chelyabinsk, Russian Federation
Open Journal of Discrete Mathematics·Volume 03 (2013)·Pages 86–92·Published 24 April 2013·DOI10.4236/ojdm.2013.32017
Copy link · social · email
Abstract
The present research considers the problem of covering a graph with minimal number of trails satisfying the pre-defined local restrictions. The research is devoted to the problem of graph covering by minimal number of trails satisfying some local restrictions. Algotithm of allowed Eulerian cycle construction is considered. The authors showed that it is possible to recognize the system of transitions and solve the problem of constructing the allowable path by linear time. It ’ s also possible to find allowable Eulerian cycle for Eulerian graph or to proclaim that such a cycle does not exist by the time O(｜V(G) ｜ . ｜E(G) ｜) . All presented algorithms have the software realization.
KeywordsEulerian GraphTrailTransitionCompatible PathAlgorithm
- T. Panyukova, “Cover with Ordered Enclosing for Flat Graphs,” Electronic Notes in Discrete Mathematics, Vol. 28, 2007, pp. 17-24. doi:10.1016/j.endm.2007.01.004
- T. Pisanski, T. W. Tucker and A. Zitnik, “Straight-Ahead walks in Eulerian Graphs,” Discrete Mathematics, Vol. 281, No. 1-3, 2004, pp. 237-246. doi:10.1016/j.disc.2003.09.011
- H. Fleischner, “Eulerian Graphs and Related Topics,” Part 1, Vol. 1, Elsevier, Amsterdam, 1990.
- H. Fleischner, “Eulerian Graphs and Related Topics,” Part 1, Vol. 2, Elsevier, Amsterdam, 1991.
- H. Fleischner, L. W. Beineke and R. J. Wilson, “Eulerian Graphs, Selected Topics in Graph Theory 2,” Academic Press, London, New York, 1983, pp. 17-53.
- D. Chebikin, “On k-Edge-Ordered Graphs,” Discrete Mathematics, Vol. 281, No. 1-3, 2004, pp. 115-128. doi:10.1016/j.disc.2003.09.004
- S. Szeider, “Finding Paths in Graphs Avoiding Forbidden Transitions,” Discrete Applied Mathematics, Vol. 126, No. 2-3, 2003, pp. 261-273. doi:10.1016/S0166-218X(02)00251-2
- A. Kotzig, “Moves without Forbidden Transitions in a Graph,” Matematicky Casopis, Vol. 18, No. 1, 1968, pp. 76-80.
- T. A. Panyukova, “The Paths with Local Restrictions,” Reports of South Ural State University. Section: Mathematical Modelling and Programming, Vol. 5, No. 16, 2010, pp. 58-67 (in Russian).