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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 3: Строка 3:
 
}}  
 
}}  
  
{| class="wikitable" style="float:right; border-spacing: 10px;"
+
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
|<center>[[Файл:Tournament_1_2.png|100px]]</center> || <center>[[Файл:Tournament_1_3.png|240px]]</center>  
+
 
 +
{| class="wikitable" style="border-spacing: 10px;"
 +
|<center>[[Файл:Tournament_1_2.png|150px]]</center> || <center>[[Файл:Tournament_1_3.png|360px]]</center>  
 
|-
 
|-
|colspan="2" |[[Файл:Tournament_1_4.png|400px]]
+
|colspan="2" |[[Файл:Tournament_1_4.png|600px]]
 
|-
 
|-
!colspan="2" |<center>Турниры из 2,3 и 4 вершин</center>
+
!colspan="2" |<center>Турниры из 2, 3 и 4 вершин</center>
 
|}
 
|}
  
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
 
  
 
<br clear="all">
 
<br clear="all">
Строка 21: Строка 22:
 
}}
 
}}
  
[[Файл:Tournament_2.png|300px|thumb|right|Негамильтонов турнир]]
+
 
 +
{| class="wikitable" style="float:right; border-spacing: 10px;"
 +
|<center>[[Файл:Tournament_2.png|400px]]</center>
 +
|-
 +
!|<center>Негамильтонов турнир</center>
 +
|}
 +
 
 +
 
 
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
 
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
  

Версия 02:42, 15 марта 2012

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


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

Tournament 1 2.png
Tournament 1 3.png
Tournament 1 4.png
Турниры из 2, 3 и 4 вершин



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

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


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


Tournament 2.png
Негамильтонов турнир


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

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

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


См. также

Литература

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