68
правок
Изменения
Нет описания правки
{{Определение
|definition = '''Турнир''' (англ. ''Tournament'') — [[ориентированный граф]], между любой парой различных вершин которого есть ровно одно ориентированное ребро.
}}
[[Файл:Tournament_1_3.png|415px|thumb|left|Турниры из трех вершин]]
<br clear="all">
==Оценка количества турниров в графе==
Если в турнире опустить ориентацию ребер, то мы получим полный граф. А так как существует два варианта ориентации каждого ребра, то количество турниров в графе из <tex>n</tex> вершин равно <tex dpi=150>2^{\frac{n\cdot(n-1)}{2}}</tex>.
==Сильно связные турниры==
{{Определение|definition = Турнир называется [[Отношение связности, компоненты связности#sc_def |сильно связным]], если из любой вершины существуют пути до всех других.}}
* [[Теорема Редеи-Камиона]]
==ЛитератураИсточники информации==
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — ISBN 5-93972-076-5
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
