Турниры — различия между версиями
| Строка 1: | Строка 1: | ||
| − | + | [[Файл:тур.png|thumb|right|турниры из 2, 3 и 4 вершин]] | |
{{Определение | {{Определение | ||
|definition = Турниром называется [[ориентированный граф]], между любой парой вершин которого есть ровно одно ориентированное ребро | |definition = Турниром называется [[ориентированный граф]], между любой парой вершин которого есть ровно одно ориентированное ребро | ||
}} | }} | ||
| + | Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта. | ||
| − | |||
{{Определение | {{Определение | ||
| − | |definition = Турнир | + | |definition = Турнир называется гамильтоновым, если он содержит гамильтонов цикл. |
}} | }} | ||
| − | + | [[Файл:тур.png|thumb|right|Негамильтонов турнир]] | |
| − | + | Не все турниры гамильтоновы: определение не исключает существование вершины с полустепенью исхода или захода равной нулю: в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа). | |
| − | |||
| − | |||
По [[Теорема Редеи-Камиона| теореме Редеи-Камиона]] турнир является сильно связанным тогда и только тогда, когда он гамильтонов. | По [[Теорема Редеи-Камиона| теореме Редеи-Камиона]] турнир является сильно связанным тогда и только тогда, когда он гамильтонов. | ||
Версия 04:57, 6 декабря 2011
| Определение: |
| Турниром называется ориентированный граф, между любой парой вершин которого есть ровно одно ориентированное ребро |
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
| Определение: |
| Турнир называется гамильтоновым, если он содержит гамильтонов цикл. |
Не все турниры гамильтоновы: определение не исключает существование вершины с полустепенью исхода или захода равной нулю: в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
По теореме Редеи-Камиона турнир является сильно связанным тогда и только тогда, когда он гамильтонов.
