# Critical tournament

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

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.