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

Материал из WEGA

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

Литература

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