Пути и маршруты в графе

Путем ориентированного графа G называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги.

Путь можно задавать последовательностью дуг или последовательностью вершин.

Например, для графа изображенного на рисунке, имеем:

μ₁= а₁, а₇, а₄

μ₂= а₃, а₄

или

μ₁= х₁ , х₂, х₃, х₄

μ₂= х₁ , х₃, х₄

Маршрутом называется последовательность ребер а₁, а₂, …, а_q, в которой каждое ребро а_i, за исключением возможно первого и последнего ребра, связано с ребрами a_i-1 и а_i+1 своими концевыми вершинами.

Если в пути или в маршруте начальная и конечная вершина совпадают, то такой путь называется циклом или циклическим контуром.

Петлей называется дуга, начальная и конечная вершины которой совпадают (например a₄, a₅).