Torneo (teoría de grafos)
Un torneo es un grafo dirigido (dígrafo) que se obtiene asignando una dirección a cada arista en un grafo completo no dirigido . Es decir, es una orientación de un gráfico completo o, de manera equivalente, un gráfico dirigido en el que cada par de vértices distintos está conectado por un borde dirigido (a menudo llamado arco ) con cualquiera de las dos orientaciones posibles.
Muchas de las propiedades importantes de los torneos fueron investigadas por primera vez por HG Landau en Landau (1953) para modelar las relaciones de dominancia en bandadas de pollos. Las aplicaciones actuales de los torneos incluyen el estudio de la teoría del voto y la teoría de la elección social, entre otras cosas.
El nombre torneo se origina a partir de la interpretación de dicho gráfico como el resultado de un torneo de todos contra todos en el que cada jugador se encuentra con todos los demás jugadores exactamente una vez y en el que no se producen empates. En el dígrafo del torneo, los vértices corresponden a los jugadores. La ventaja entre cada par de jugadores se orienta del ganador al perdedor. Si jugador le gana a jugador , entonces se dice que domina . Si cada jugador vence al mismo número de otros jugadores ( grado interior = grado exterior ), el torneo se llama regular .
Teorema : cualquier torneo en un número finito de vértices contiene un camino hamiltoniano , es decir, un camino dirigido en todos los vértices ( Rédei 1934).
