Path

Материал из WikiGrapp
Перейти к:навигация, поиск

Path --- путь.

1. Given a digraph G = (V,A), a path is a sequence of vertices (v_{0}, \ldots, v_{k}) such that (v_{i}, v_{i+1}) \in A for i =
0, \ldots, k-1; its length is k. The path is simple if all its vertices are pairwise distinct. A path (v_{0}, \ldots,
v_{s}) is a cycle if s > 1 and v_{0} = v_{s}, and a simple cycle if in addition v_{1}, \ldots, v_{s-1} are pairwise distinct.

2. Given a hypergraph {\mathcal H}, a path from a vertex u to a vertex v is a sequence of edges (e_{1}, \ldots, e_{k}), k \geq
1, such that u \in e_{1}, \; v \in e_{k} and , if k > 1, \; e_{h}
\cap e_{h+1} \neq emptyset for h = 1, \ldots, k-1; furthermore, we say that this path passes through a subset X of V({\mathcal H}), if e_{h} \cap e_{h+1} is a subset of X for some h < k.