Путь

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

Путь (Path) — в орграфе такая последовательность вершин и дуг

S = (v_{0}, e_{1}, v_{1}, \ldots, e_{n}, v_{n}),

что \,e_{i} = (v_{i-1},v_{i}) для i = 1, \ldots, n; данный путь называется путем из \,v_{0} в \,v_{n} длины \,n с начальной вершиной \,v_{0}, конечной вершиной \,v_{n} и внутренними вершинами v_{1}, \ldots, v_{n-1}.

Литература

  • Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.