Path

Материал из WikiGrapp
Версия от 13:53, 9 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''Path''' --- путь. '''1.''' Given a digraph <math>G = (V,A)</math>, a ''' path''' is a sequence of vertices <math>(v_{0}, \ldots, v_{k})</math> such that <ma…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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