Torneo (teoría de grafos)

En teoría de grafos, un torneo é un grafo dirixido con exactamente unha aresta entre cada par de vértices, nunha das dúas direccións posibles. Equivalentemente, un torneo é unha orientación dun grafo completo non dirixido. 

O nome torneo provén de interpretar o grafo como o resultado dun torneo todos-contra-todos, un xogo no que cada xogador se enfronta a todos os demais exactamente unha vez. Nun torneo, os vértices representan os xogadores, e as arestas entre eles apuntan desde o gañador cara ao perdedor.

Un caso particular interesante é o dos «torneos de comparación por pares equilibrada» ou round-robin, nos que cada actor compite contra todos os demais unha única vez, nun sistema de todos contra todos. Neste último caso, o grafo coincide co que se obtería asignándolle unha dirección a cada aresta dun grafo completo non dirixido, de modo que cada par de vértices está conectado exactamente por unha aresta.

Moitas das propiedades importantes dos torneos foron investigadas por H. G. Landau en 1953 para modelar relacións de dominancia en bandos de galiñas.  Os torneos tamén se estudan amplamente na teoría da elección social, onde poden representar información parcial sobre as preferencias dos votantes entre múltiples candidatos, e son fundamentais para a definición dos métodos de Condorcet.

Se cada xogador vence ao mesmo número de opoñentes (é dicir, grao de entrada − grao de saída = 0), o torneo chámase regular.

 Notas 

Categoría:Teoría de grafos