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

Путь (в теории графов) - цепь, все ребра которого ориентированы в направлении движения от начальной до конечной вершины цепи.

Путь обозначают символом μ (x 0, x l) = (u 1, u 2,..., u l), где дуга u i инциндентна вершинам x i-1 и x i. Путь, в котором любая вершина не встречается дважды, называется элементарным.

Если x i и x j - некоторые вершины графу, для которых существует путь μ (x i, x j) то вершина x j достижима из вершины x i, а вершина x i - обратно достижима из вершины x j. Множество всех достижимых из x i вершин обозначается символом D (x i), а обратно достижимых - D 1 (x i). Для любой множества A вершин определяется достижима множество

D (A) = \ cup_ {x \ in A} D (x) .

Аналогично определяется обратно достижима множество D -1 (A).

Путь, содержит все дуги ориентированного графа, называется эйлеровых.


Источники информации

См.. также