Critical tournament: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Critical tournament''' --- критический турнир. Given a tournament <math>T = (V,A)</math>, a subset <math>X</math> of <math>V</math> is an '''in…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''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 - | 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 | ||
X</math>, <math>(a,x) \in A</math> if and only if <math>(b,x) \in A</math>. For example, | 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. | ||
<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'''; otherwise, it is '''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 | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
Текущая версия от 12:24, 22 февраля 2018
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.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.