Турниры — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 5: Строка 5:
 
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
 
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
  
[[Файл:Tournament_1_2.png|155px|thumb|left|Турнир из двух вершин]] [[Файл:Tournament_1_3.png|415px|thumb|left|Турниры из трех вершин]]
+
[[Файл:Tournament_1_3.png|415px|thumb|left|Турниры из трех вершин]]
  
  

Версия 21:38, 6 июня 2012

Определение:
Турнирориентированный граф, между любой парой различных вершин которого есть ровно одно ориентированное ребро.


Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.

Турниры из трех вершин



Сильно связные турниры

Определение:
Турнир называется сильно связным, если из любой вершины существуют пути до всех других.


Определение:
Турнир называется гамильтоновым, если он содержит гамильтонов цикл.


Негамильтонов турнир


Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).

Теорема Редеи-Камиона устанавливает 2 следующих факта:

  1. Все турниры полугамильтоновы.
  2. Турнир гамильтонов тогда и только тогда, когда он сильно связен.


См. также

Литература

  • Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — ISBN 5-93972-076-5