Цепь

Материал из WEGA
Версия от 14:53, 16 февраля 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Цепь''' (''Chain, Trail'') - 1. В неориентированном графе ''маршрут'', все ребра котор...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Цепь (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].

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

Литература

[Лекции]