Турниры — различия между версиями
(→См. также) |
|||
| Строка 2: | Строка 2: | ||
|definition = '''Турнир''' — [[ориентированный граф]], между любой парой различных вершин которого есть ровно одно ориентированное ребро. | |definition = '''Турнир''' — [[ориентированный граф]], между любой парой различных вершин которого есть ровно одно ориентированное ребро. | ||
}} | }} | ||
| + | |||
| + | {| class="wikitable" style="float:right; border-spacing: 10px;" | ||
| + | |<center>[[Файл:Tournament_1_2.png|100px]]</center> || <center>[[Файл:Tournament_1_3.png|240px]]</center> | ||
| + | |- | ||
| + | |colspan="2" |[[Файл:Tournament_1_4.png|400px]] | ||
| + | |- | ||
| + | !colspan="2" |<center>Турниры из 2,3 и 4 вершин</center> | ||
| + | |} | ||
| + | |||
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта. | Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта. | ||
| − | + | ||
| + | <br clear="all"> | ||
==Сильно связные турниры== | ==Сильно связные турниры== | ||
| Строка 11: | Строка 21: | ||
}} | }} | ||
| − | [[Файл: | + | [[Файл:Tournament_2.png|300px|thumb|right|Негамильтонов турнир]] |
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа). | Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа). | ||
| Строка 17: | Строка 27: | ||
# Все турниры полугамильтоновы. | # Все турниры полугамильтоновы. | ||
# Турнир гамильтонов тогда и только тогда, когда он сильно связен. | # Турнир гамильтонов тогда и только тогда, когда он сильно связен. | ||
| + | <br clear="all"> | ||
==См. также== | ==См. также== | ||
Версия 23:43, 11 марта 2012
| Определение: |
| Турнир — ориентированный граф, между любой парой различных вершин которого есть ровно одно ориентированное ребро. |
 |
 |
| |
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
Сильно связные турниры
| Определение: |
| Турнир называется сильно связным, если из любой вершины существуют пути до всех других. |
| Определение: |
| Турнир называется гамильтоновым, если он содержит гамильтонов цикл. |
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
Теорема Редеи-Камиона устанавливает 2 следующих факта:
- Все турниры полугамильтоновы.
- Турнир гамильтонов тогда и только тогда, когда он сильно связен.
См. также
Литература
- Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — ISBN 5-93972-076-5
