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