The Software for Constructing Trails with Local Restrictions in Graphs

• 作者: Igor Alferov Tatyana Panyukova
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: EULERIAN GRAPH TRAIL Transition Compatible Path Algorithm
• 年，卷（期）: 2013,（2）
• 页码范围: 86-92
• 页数: 7页
• 分类号: O1

摘要

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.