Турниры — различия между версиями
(→Гамильтоновы турниры) |
|||
| Строка 5: | Строка 5: | ||
[[Файл:тур.png|thumb|right|турниры из 2, 3 и 4 вершин]] | [[Файл:тур.png|thumb|right|турниры из 2, 3 и 4 вершин]] | ||
| − | == | + | ==Сильно связные турниры== |
| + | {{Определение|definition = Турнир называется [http://neerc.ifmo.ru/mediawiki/index.php/%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8,_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82%D1%8B_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8#.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.81.D0.B2.D1.8F.D0.B7.D0.BD.D0.BE.D1.81.D1.82.D1.8C сильно связным], если из любой вершины существуют пути до всех других.}} | ||
{{Определение | {{Определение | ||
|definition = Турнир называется [[Гамильтоновы графы | гамильтоновым]], если он содержит гамильтонов цикл. | |definition = Турнир называется [[Гамильтоновы графы | гамильтоновым]], если он содержит гамильтонов цикл. | ||
}} | }} | ||
| − | + | ||
| − | [[Файл:негам.png|thumb| | + | [[Файл:негам.png|thumb|right|Негамильтонов турнир]] |
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа). | Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа). | ||
[[Теорема Редеи-Камиона]] устанавливает 2 следующих факта: | [[Теорема Редеи-Камиона]] устанавливает 2 следующих факта: | ||
| − | # Все турниры полугамильтоновы | + | # Все турниры полугамильтоновы. |
# Турнир гамильтонов тогда и только тогда, когда он сильно связен. | # Турнир гамильтонов тогда и только тогда, когда он сильно связен. | ||
Версия 19:30, 13 декабря 2011
| Определение: |
| Турнир — ориентированный граф, между любой парой вершин которого есть ровно одно ориентированное ребро. |
Название этого класса графов связано с тем, что их удобно использовать для описания результатов командных соревнований в некоторых видах спорта.
Сильно связные турниры
| Определение: |
| Турнир называется сильно связным, если из любой вершины существуют пути до всех других. |
| Определение: |
| Турнир называется гамильтоновым, если он содержит гамильтонов цикл. |
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода или захода равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
Теорема Редеи-Камиона устанавливает 2 следующих факта:
- Все турниры полугамильтоновы.
- Турнир гамильтонов тогда и только тогда, когда он сильно связен.
