Текст. Урок 14. Степень (валентность) вершины. Цепь и цикл. Ориентированные графы

3. Понятие цепи (пути)

В графе часто нужно найти маршрут из одной вершины в другую.

Определение:
Цепь (путь) — последовательность рёбер, в которой каждые два соседних ребра имеют общую вершину, и вершины не повторяются (кроме, возможно, концов).

Длина цепи — количество рёбер в ней.

Пример 3.
В графе из примера 1:
A – B – D — это цепь длины 2 из A в D.
A – C – B – A — это цепь? Нет, потому что A повторяется (кроме случая, когда это замкнутая цепь — см. цикл).

Цепь можно задавать списком вершин: (A, B, D).