(a,b)-Separator

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

[math]\displaystyle{ (a,b) }[/math]-Separator --- [math]\displaystyle{ (a,b) }[/math]-сепаратор.

Let [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] be nonadjacent vertices. A set [math]\displaystyle{ S }[/math] of vertices is a minimal [math]\displaystyle{ (a,b) }[/math]-separator if [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] are in different connected components of [math]\displaystyle{ G - S }[/math] and there is no proper subset of [math]\displaystyle{ S }[/math] with the same property. A minimal separator is a set [math]\displaystyle{ S }[/math] of vertices for which there exist nonadjacent vertices [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] such that [math]\displaystyle{ S }[/math] is a minimal [math]\displaystyle{ (a,b) }[/math]-separaror.