Path

Материал из WikiGrapp

Path --- путь.

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

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