68
правок
Изменения
Нет описания правки
*Последовательность числа выигрышей (множество полуисходов) <tex>T</tex> есть <tex> 0, 1, 2,..., n - 1 </tex>.
*<tex>T</tex> содержит ровно один гамильтонов путь.
Транзитивные турниры играют существенную роль в теории Рамсея, изучающей условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. В частности, любой турнир с <tex>n</tex> вершинами содержит транзитивный подтурнир с <tex>1+\lfloor\log_2 n\rfloor</tex> вершинами. Для его построения выберем любую вершину <tex>v</tex> как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины <tex>v</tex>, либо на множестве исходящих соседей, в зависимости от того, какое множество больше.
<br clear="all">
