# Path

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

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$.