5.8. Турниры

Полный ориентированный граф называется турниром. Этот термин получил свое название от соревнований по круговой системе, графическое представление которых имеет структуру полного ориентированного графа. В турнирах по круговой системе играют несколько команд, каждая со всеми остальными по одному разу. Игра по правилам не может закончиться вничью. В представлении турнира по круговой системе ориентированным графом командам соответствуют вершины и дуга присутствует в графе, если соответствующая команда победила команду, представленную вершиной Очевидно, что в таком ориентированном графе нет параллельных дуг и петель и между каждыми двумя вершинами имеется точно одна дуга. Таким образом, граф является полным, а следовательно, и турниром. Пример турнира приведен на рис. 5.17. Участвующие в турнире команды можно ранжировать в соответствии с количеством очков. Количество очков команды соответствует

числу побежденных ею противников. Введем определение последовательности очков турнира.

Последовательностью очков турнира на вершинах называется последовательность в которой каждое является полустепенью исхода вершины турнира.

В следующей теореме дается интересная характеризация турниров, исходя из последовательности очков.

Рис. 5.17. Турнир.

Теорема 5.14. Последовательность неотрицательных целых чисел является последовательностью очков турнира G тогда и

только тогда, когда для всех

Доказательство.

Необходимость. Заметим, что сумма равна числу дуг турнира G (теорема 5.1). Поскольку турнир — это полный граф, он имеет дуг, где — число вершин. Таким образом, Для доказательства условия 2 рассмотрим подтурнир из любых k вершин содержит дуг. Поэтому в целом турнире поскольку в нем могут присутствовать дуги, исходящие из вершин подтурнира и направленные в вершины, не принадлежащие подтурниру.

Достаточность доказывается в работе [5.5].

Предположим, что команды турнира по круговой системе можно упорядочить таким образом, что за каждой командой идет побежденная ею. Тогда для фиксации порядка можно будет присвоить командам целые числа п. Такое ранжирование всегда возможно, поскольку в турнире имеется ориентированный гамильтонов путь (теорема 5.12). Оно называется ранжированием гамильтоновым путем.

Заметим, что ранжирование гамильтоновым путем может отличаться от ранжирования по очкам. Более того, турнир может иметь не один ориентированный гамильтонов путь. В таком случае возможно более одного ранжирования гамильтоновым путем. Однако в транзитивном турнире существует точно один ориентированный гамильтонов путь. Это устанавливается в следующей легко доказываемой теореме:

Теорема 5.15. В транзитивном турнире имеется точно один ориентированный гамильтонов путь.

Другие процедуры ранжирования рассматриваются в работах [5.6-5.8],