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

'''Critical tournament''' — ''[[критический турнир]].''

Given a tournament <math>\,T = (V,A)</math>, a subset <math>\,X</math> of <math>\,V</math> is an '''[[interval]]''' of <math>\,T</math> provided that for every <math>\,a, b \in X</math> and <math>\,x \in V - X</math>, <math>\,(a,x) \in A</math> if and only if <math>\,(b,x) \in A</math>. For example, <math>\,\emptyset</math>, <math>\,\{x\} \; (x \in V)</math> and <math>\,V</math> are intervals, called '''[[trivial intervals]]'''. A tournament all intervals of which are trivial is

called ''' [[indecomposable intervals|indecomposable]]'''; otherwise, it is '''[[decomposable intervals|decomposable]]'''. An indecomposable tournament <math>\,T = (V,A)</math> is then said to be '''[[critical]]''' if for each <math>\,x \in V</math>, <math>\,T(V - \{x\})</math> is decomposable and if there are <math>\,x \neq y \in V</math> such that <math>\,T(V - \{x,y\})</math> is indecomposable.

 

 

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