Путь (теория графов)

Путь (Цепь) в графе $G = (V, E)$ — последовательность вершин $v_i \in V$ при $i = 1, \dots , k$, таких, что две любые последовательные вершины соединены хотя бы одной дугой из $E$.

Число $k$ рёбер в пути называется его длиной. Каждая из пар двух последовательных вершин называется его звеном.

Иногда различают понятие пути и цепи, называя термином "путь" ориентированную цепь в орграфе, в которой у каждого из звеньев дуга идёт от вершины с меньшим номером к вершине с бо́льшим.

См. также

• Маршрут
• Транспортная логистика
• Волновой алгоритм
• Алгоритм Дейкстры