Y-сводимый маршрут

Материал из WikiGrapp
Перейти к:навигация, поиск

Y-Сводимый маршрут (Y-Reduced sequence) — для реберного покрытия Y такой маршрут, у которого концевые ребра принадлежат Y, а концевые вершины инцидентны тем ребрам из Y, которые не являются концевыми ребрами этого маршрута. Очевидно, что любое наименьшее реберное покрытие не содержит сводимых маршрутов.

Литература

  • Харари Ф., Палмер Э. Перечисление графов. — М.: Мир,1977.