Ориентированный маршрут

Материал из WEGA
Перейти к навигации Перейти к поиску

Ориентированный маршрут (Directed sequence) — такая последовательность [math]\displaystyle{ S = (v_{0}, e_{1}, v_{1}, e_{2}, \ldots , e_{n}, v_{n}) }[/math] его чередующихся вершин [math]\displaystyle{ \,v_{i} }[/math] и дуг [math]\displaystyle{ \,e_{j} }[/math] что [math]\displaystyle{ \,e_{i} = (v_{i-1}, v_{i}), }[/math] [math]\displaystyle{ 1 \leq i \leq n. }[/math] Такой маршрут называется [math]\displaystyle{ \,(v_{0}, v_{n}) }[/math]-маршрутом. Вершины [math]\displaystyle{ \,v_{0} }[/math] и [math]\displaystyle{ \,v_{n} }[/math] называются крайними, а остальные — промежуточными или внутренними.

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
  • Оре О. Теория графов. — М.: Наука, 1968.