Турниры

Турнир- это направленный полный граф.

В турнире состязаний данный состав игроков или команд ведет такую игру, правилами которой запрещен ничейный исход. Каждый игрок встречается с каждым другим игроком по одному разу и точно один из них одерживает победу. Игроки изображаются вершинами, и для каждой пары вершин дуга идет от победителя к побежденному; так строится турнир.

Из всех полученных когда-либо теорем о турнирах первая принадлежит Редеи для турниров с малым количеством вершин

Теорема.Каждый турнир имеет остовный путь.

Теорема.Каждый сильный турнир с р вершинами имеет контур длины n для n=3, 4, ..., р.

Следствие(а).Турнир является сильным тогда и только тогда, когда он имеет остовный контур.

Используя терминологию турниров состязаний, назовем количеством очков вершины ее полустепень исхода. Следующая теорема, доказанная Ландау, появилась в результате эмпирического изучения специальных турниров (так называемых «pecking orders»), в которых вершины представляют кур, а дуги — клевки.

Теорема.Расстояние от вершины с наибольшим количеством очков до любой другой равно 1 или 2.

Число транзитивных троек можно выразить через количества очков вершин; см. Харари и Мозер. Как следствие отсюда немедленно получается хорошо известная формула Кендалла и Смита, имеющая большое значение в статистическом анализе. Она была также получена Байнеке и Харари с помощью перехода от циклических троек к сильным подтурнирам большего размера.

Теорема. Число транзитивных троек в турнире с набором количеств очков (S1,S2,....Sp) равноsi(si-l)/2.