Маршруты с локальными ограничениями

В данной работе рассмотрена задача покрытия графа минимальным числом цепей, удовлетворяющих заданным локальным ограничениям. Показана возможность распознавания системы переходов, допускающей линейную сложность задачи построения допустимого пути. Построены алгоритмы отыскания в графе допустимого эйлерова цикла за линейное время, либо, если такого цикла нет, - покрытия графа допустимыми цепями.

Ключевые слова

граф, маршрут, цепь, запрещенный переход, покрытие

Литература

1. Panioukova, T.A. Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs / T.A. Panioukova, A.V. Panyukov // The International Workshop on Computer Science and Information Technologies' 2003, Proceedings of Workshop, Ufa, September 16 - 18, 2003/ Ufa State Technical University. - Ufa, 2003. - Vol. 1. - Р. 134 - 138.
2. Pisanski, Т. Straight-ahead walks in Eulerian graphs / T. Pisanski, T.W. Tucker, A. Zitnik // Discrete Mathematics, 2004. - №. 281. - P. 237 - 246.
3. Фляйшнер, Г. Эйлеровы графы и смежные вопросы / Г. Фляйшнер. - М.: Мир, 2002. - 335 с., ил.
4. Fleischner H. Eulerian Graphs and Related Topics / H. Fleischner. - Part 1, Vol.2 - Ann. Discrete Mathematics, 1991. - № 50.
5. Fleichner, H. Eulerian Graphs / H. Fleischner, L.W. Beineke, R.J. Wilson // Selected Topics in Graph Theory 2, Academic Press, London-NewYork, 1983. - P. 17 - 53.
6. Chebikin, D. On k-edge-ordered graphs / D. Chebikin // Discrete Mathematics, 2004. - № 281. - P. 115 - 128.
7. Szeider, S. Finding Paths in Graphs Avoiding Forbidden Transitions / S. Szeider // Discrete Applied Mathematics, 2003. - № 126. - P. 261 - 273.
8. Kotzig, A. Moves Without Forbidden Transitions in a Graph / A. Kotzig // Mat.-Fiz. Casopis 18, 1968. - № 1. - С. 76 - 80.
9. Панюкова, Т.А. Построение совместимых цепей в графах / Т.А. Панюкова, В.Ф. Мирасов // Проблемы теоретической и прикладной математики: тр. 39-й Регион. молодеж. конф. Екатеринбург, 2008. - С. 38 - 43.