En teoría de grafos, un torneo es un grafo dirigido cuyos vértices representan un conjunto de actores o competidores en alguna competición o acontecimiento, y cuyas aristas representan el triunfo de un competidor sobre otro.
Un caso particular interesante es el de los «torneos de comparación apareada equilibrada» o round-robin, donde cada actor compite contra los demás una única vez, en un sistema de todos contra todos.
En este último caso, el grafo coincide con lo que se obtendría asignándole una dirección a cada arista de un grafo completo no dirigido, de modo que cada par de vértices está conectado exactamente por una arista.
En el digrafo torneo, los vértices corresponden a los jugadores.
[1] Cualquier torneo con un número finito de vértices contiene un camino hamiltoniano, es decir, un camino dirigido con todos los
: supongamos que el enunciado se cumple para
máximo tal que para todo
Este argumento también provee una forma de encontrar un camino hamiltoniano.
Algoritmos más eficientes, que requieren examinar solo
[4] Esto implica que un torneo fuertemente conexo tiene un ciclo hamiltoniano.
[5] Un resultado más fuerte es que todo torneo fuertemente conexo es vértice pancíclico: para todo vértice v, y todo k en el rango desde tres hasta la cantidad de vértices del torneo, existe un ciclo de longitud k que contiene a v.
[6] Sin embargo, si un torneo es 4-conexo, cada par de vértices puede ser conectado con un camino hamiltoniano.
En un torneo transitivo, los vértices pueden ser totalmente ordenado por alzanzabilidad.
Las siguientes condiciones son equivalentes para un torneo T de n vértices: Los torneos transitivos juegan un rol en la teoría de Ramsey análogo a los cliques en los grafos no diridos.
[8] La demostración es simple: seleccionemos un vértice v para que sea parte de este subtorneo, y formemos el resto del subtorneo recursivamente en el conjunto de vecinos entrantes de v o en el conjunto de los vecinos salientes de v, cual sea el más grande.
Por ejemplo, todo torneo de siete vértices contiene un subtorneo transitivo de tres vértices; el torneo Paley de siete vértices muestra que esto es lo mejor que se puede garantizar.
[8] Sin embargo, demostró que este límite no es justo para algunos valores mayores de n.[9] Existen torneos de n vértices sin un subtorneo transitivo de tamaño
torneos diferentes en el mismo conjunto de n vértices enumerados.
Un jugador que gane todos los juegos es naturalmente el ganador del torneo.
Sin embargo la existencia de torneos no transitivos muestra que puede que no exista tal jugador.
Generalizando, un torneo T=(V,E) es llamado k-paradójico si para todo subconjunto de k elementos S de V existe un vértice v0 en
Mediante el método probabilístico, Paul Erdős demostró que para un valor fijo de k, si |V| ≥ k22kln(2 + o(1)), entonces casi todo torneo en V es k-paradójico.
[10] Por otro lado, un fácil argumento muestra que para cualquier torneo k-paradójico debe tener el menos 2k+1 − 1 jugador, el cual puede ser mejorado a (k + 2)2k−1 − 1.
[11] Existe una construcción explícita de torneos k-paradójicos con k24k−1(1 + o(1)) jugadores llamado torneo Paley.
Por lo tanto, incluso para torneos que no son transitivos, sus componentes fuertemente conexos pueden ser ordenados totalmente.
[2] Una secuencia no decreciente de enteros
es una secuencia de grados si y solo si: Sea
(sucesión A000571 en OEIS): 1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107,... Winston y Kleitman demostraron que para un n suficientemente grande: donde
Posteriormente se demostró que, utilizando algunas asunciones razonables, pero no demostradas, que donde
[14] Juntas, estas ecuaciones muestran evidencia de que: Aquí