Critical tournament

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

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

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

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.