Цепь

Цепь (Chain, Trail) —

1. В неориентированном графе маршрут, все ребра которого различны.

2. В ориентированном графе последовательность вершин [math]\displaystyle{ v_{1}, \, \ldots, \, v_{k} }[/math] в которой соседние вершины [math]\displaystyle{ \,v_{i} }[/math] и [math]\displaystyle{ \,v_{i+1} }[/math] определяют дугу (либо [math]\displaystyle{ \,(v_{i}, v_{i+1}) }[/math], либо [math]\displaystyle{ \,(v_{i+1}, v_{i}) }[/math].

См. также

• Гамильтонова цепь,
• Геодезическая цепь,
• Простая цепь,
• Эйлерова цепь.

Литература

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