Locally k-connected graph

Материал из WikiGrapp
Версия от 16:37, 31 мая 2011; Glk (обсуждение | вклад) (Новая страница: «'''Locally <math>k</math>-connected graph''' --- локально <math>k</math>-связный граф. Let <math>M</math> and <math>H</math> be two subgraphs of…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Locally [math]\displaystyle{ k }[/math]-connected graph --- локально [math]\displaystyle{ k }[/math]-связный граф.

Let [math]\displaystyle{ M }[/math] and [math]\displaystyle{ H }[/math] be two subgraphs of [math]\displaystyle{ G }[/math] with [math]\displaystyle{ V(H) \cap V(M) = \emptyset }[/math]. We say that [math]\displaystyle{ H }[/math] is locally [math]\displaystyle{ k }[/math]-connected to [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math] if [math]\displaystyle{ G }[/math] contains [math]\displaystyle{ k }[/math] pairwise disjoint [math]\displaystyle{ (x,V(M)) }[/math] paths for every vertex [math]\displaystyle{ x \in H }[/math]. Let now [math]\displaystyle{ M }[/math] be a cycle in [math]\displaystyle{ G }[/math], and let [math]\displaystyle{ H }[/math] be a subgraph of [math]\displaystyle{ G - V(M) }[/math]. We say that [math]\displaystyle{ M }[/math] is locally longest with respect to [math]\displaystyle{ H }[/math] in [math]\displaystyle{ G }[/math] if we cannot obtain a cycle longer than [math]\displaystyle{ M }[/math] by replacing a segment [math]\displaystyle{ M[u,v] }[/math] by a [math]\displaystyle{ (u,v) }[/math]-path of [math]\displaystyle{ G }[/math] through [math]\displaystyle{ H }[/math].