Critical tournament: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''Critical tournament''' --- критический турнир. Given a tournament <math>T = (V,A)</math>, a subset <math>X</math> of <math>V</math> is an '''in…»)
(нет различий)

Версия от 15:37, 15 марта 2011

Critical tournament --- критический турнир.

Given a tournament [math]\displaystyle{ T = (V,A) }[/math], a subset [math]\displaystyle{ X }[/math] of [math]\displaystyle{ V }[/math] is an interval of [math]\displaystyle{ T }[/math] provided that for every [math]\displaystyle{ a, b \in X }[/math] and [math]\displaystyle{ x \in V - X }[/math], [math]\displaystyle{ (a,x) \in A }[/math] if and only if [math]\displaystyle{ (b,x) \in A }[/math]. For example, [math]\displaystyle{ \emptyset }[/math], [math]\displaystyle{ \{x\} \; (x \in V) }[/math] and [math]\displaystyle{ V }[/math] are intervals, called trivial intervals. A tournament all intervals of which are trivial is called indecomposable; otherwise, it is decomposable. An indecomposable tournament [math]\displaystyle{ T = (V,A) }[/math] is then said to be critical if for each [math]\displaystyle{ x \in V }[/math], [math]\displaystyle{ T(V - \{x\}) }[/math] is decomposable and if there are [math]\displaystyle{ x \neq y \in V }[/math] such that [math]\displaystyle{ T(V - \{x,y\}) }[/math] is indecomposable.