# Path

(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Path --- путь.

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

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