En mathématiques, dans le cadre de la théorie des graphes, un tournoi est un graphe orienté et complet, ce qui signifie que chaque paire de sommets distincts est reliée par une arête orientée (ou arc) et une seule. Le nom tournoi provient de l'interprétation de tels graphes comme le résultat d'un tournoi toutes rondes, dans lequel chaque participant rencontre chaque autre participant une fois et une seule, et dans lequel il n'y a pas égalité. Dans le graphe, les sommets correspondent aux participants et les arêtes correspondent aux résultats des parties jouées, l'arête allant du vainqueur au perdant. Si le participant bat le participant , on dit que domine , noté .

En pratique, on étudie généralement les tournois finis. Si son nombre de sommets est , ce que l'on appelle ordre du tournoi, il contient arcs.

Du point de vue de la théorie des ensembles, un tournoi est une relation binaire entre et qui est irréflexive et asymétrique et complète. Sa fermeture réflexive est totale et antisymétrique.

On peut également considérer les tournois comme des cas particuliers d'algèbre, c'est-à-dire de magma commutatif, une correspondance apparaissant dans ainsi que , ou encore d'applications de antisymétriques à valeurs dans .

Pour tout tournoi et toute partie , on peut définir un sous-tournoi en considérant comme la trace de sur . En particulier, on peut former des sous-tournois de en considérant pour tout sommet les parties et qui désignent respectivement les sommets qui dominent et les sommets qui sont dominés par .

Applications De nombreuses propriétés importantes des tournois ont été explorées par H. G. Landau afin de modéliser des relations de dominations dans des groupes de poulets. Les applications actuelles des tournois concernent la théorie des systèmes électoraux ainsi que la théorie du choix en société, entre autres.

Les tournois permettent de modéliser les jeux à sélection de choix, qui sont des jeux dans lesquels deux joueurs choisissent simultanément un choix parmi un ensemble déterminé et confrontent leurs choix, avec un gagnant et un perdant pour toute configuration dans laquelle les deux choix sont différents. Le cas le plus connu est le pierre-feuille-ciseaux.

Chemins et circuits Chaque tournoi sur un nombre fini de sommets contient un chemin hamiltonien, c'est-à-dire un chemin orienté passant par les sommets une fois et une seule. Ce résultat est dû à László Rédei en 1934., qui a prouvé en fait un résultat plus fort : le nombre de chemins hamiltoniens d'un tournoi est toujours impair.

Cette démonstration est constructive : elle fournit un algorithme permettant de trouver un chemin hamiltonien. Des algorithmes plus efficaces, qui ne supposent d'examiner qu'un nombre d'arêtes de l'ordre de , sont connus..

Cela a pour conséquence qu'un tournoi fortement connexe, c'est-à-dire tel qu'il existe un chemin entre n'importe quelle paire de sommets, possède un circuit hamiltonien, c'est-à-dire un cycle fermé et orienté passant par tous les sommets une fois et une seule (résultat dû à Paul Camion en 1959).. Les tournois fortement connexes sont appelés tournois irréductibles.

Un résultat plus puissant est que tout tournoi fortement connexe est sommet-pancyclique : pour tout sommet et pour tout où est le nombre de sommets, il y a un circuit de longueur passant par , Théorème 1..

Transitivité et tournois paradoxaux thumb|upright=1.5|Un tournoi transitif à 8 sommets. Dans ce graphe, si et seulement si . Dans les tournois de la vie réelle, on s'attend à ce que, si une personne domine une personne , et si domine à son tour une troisième personne , alors domine . Cela correspond au concept habituel de transitivité pour une relation binaire.

Étant donné un tournoi à sommets, les énoncés suivants sont équivalents : est transitif ; est acyclique ; ne contient pas de circuit de longueur 3 ; La suite des scores de (voir plus bas) est ; possède exactement un chemin hamiltonien.

Les tournois transitifs sont très particuliers parmi les tournois : ce sont des ordres stricts. Un tournoi qui n'est pas transitif est dit paradoxal.

Un participant à un tournoi qui gagne toutes les parties est appelé vainqueur de Condorcet (s'il perd toutes les parties, un perdant de Condorcet). Dans la plupart des tournois, il n'y a ni gagnant ni perdant de Condorcet.

Un tournoi lors duquel chaque participant perd au moins une partie est appelé tournoi 1-paradoxal. De façon plus générale, un tournoi est dit -paradoxal si, pour tout sous-ensemble à éléments de , il existe un sommet dans tel que pour tous les sommets de .

On trouve dans Moon la preuve du résultat suivant : pour tout entier , tout tournoi d'ordre admet un sous-tournoi transitif d'ordre .

Il avait été conjecturé par Erdős et Moser que la borne était optimale, cependant il a été prouvé par et que ce n'est pas le cas ; par exemple tout tournoi d'ordre 14 contient un sous-tournoi transitif d'ordre 5.

Représentation linéaire d'un tournoi La donnée d'un tournoi à sommets nécessite de tracer arcs, ce qui même pour de petites valeurs de entraîne très rapidement des problèmes de lisibilité. On peut remédier partiellement à cette problématique en plaçant l'ensemble des sommets en ligne et en décidant d'un sens implicite entre sommets (par exemple, de la droite vers la gauche) ; il reste alors à tracer uniquement les relations qui contredisent ce sens.

Par exemple, si l'on se réfère au tournoi à 4 sommets présenté en début d'article, on voit que si l'on définit l'ordre , alors la seule relation de ce tournoi qui contredit cet ordre est que le sommet gagne contre le sommet . Il suffit donc de placer à la suite les sommets puis puis puis , puis tracer le seul arc allant du sommet vers le sommet pour représenter ce tournoi, au lieu des 6 arcs nécessaires.

La problématique de savoir comment ordonner les sommets afin de minimiser le nombre d'arcs restant à tracer est à rapprocher du calcul de la distance d'un tournoi au tournoi transitif ayant le même nombre de sommets, la distance étant déterminée par le nombre de relations entre deux sommets à inverser (voir pour quelques exemples et valeurs de cet indice).

Suite des scores et ensemble de scores La suite des scores d'un tournoi est la suite ordonnée par ordre croissant des degrés sortants des sommets d'un tournoi.

L'ensemble des scores d'un tournoi est l'ensemble des degrés sortants des sommets du tournoi.

Le théorème de Landau (1953). affirme qu'une suite d'entiers est une suite de scores si et seulement si :

.

Par exemple, est bien une suite de scores, car :

car ; car ; car car De fait, cela correspond à la suite des scores du tournoi tout en haut de l'article.

En ce qui concerne les ensembles de scores, T. X. Yao a prouvé que n'importe quel ensemble non vide d'entiers positifs ou nuls est l'ensemble de scores d'un certain tournoi.

On appelle tournoi régulier un tournoi pour lequel tous les sommets ont même score. Les tournois réguliers n'existent qu'avec un nombre impair de sommets.

Rois d'un tournoi Dans un tournoi, un roi est un sommet à partir duquel tout autre sommet peut être atteint en un chemin de longueur au plus deux. Formellement, est un roi si et seulement si pour tout autre sommet , ou bien , ou bien il existe un autre sommet tel que et . Cela revient à dire que, si ne gagne pas contre , alors on peut trouver un sommet tel que , et forment un cycle.

Dans le contexte d'un jeu à sélection de choix, dire qu'un sommet n'est pas un roi signifie qu'il existe un sommet qui est toujours un meilleur choix que . En effet, et pour tout choix , implique . Ainsi, un sommet qui n'est pas un roi n'est pas un choix pertinent dans un jeu à sélection de choix.

Maurera montré plusieurs propriétés importantes concernant les rois d'un tournoi, dont :

tout tournoi possède au moins un roi, tout choix de score maximal est un roi (la réciproque étant fausse), si un tournoi possède un unique roi, alors ce roi est un vainqueur de Condorcet, un tournoi ne peut pas comporter exactement deux rois, lorsque le nombre de sommets est , le nombre de rois d'un tournoi à n sommets peut prendre n'importe quelle valeur entre 3 et , à la seule exception pour un tournoi d'ordre 4 qui ne peut pas contenir 4 rois.

Voici quelques démonstrations courtes de ces assertions (à l'exception de la dernière qui nécessite un peu plus de travail)

Matrices de tournoi Il est naturel de noter les résultats d'un tournoi dans un tableau qui indique le résultat de chaque confrontation entre choix.

On appelle matrice de tournoi une matrice carrée dont les éléments valent : si , si , si .

Une matrice de tournoi est égale à l'opposé de sa transposée (elle est antisymétrique).

Il faut noter que définir une matrice de tournoi nécessite d'avoir étiqueté les sommets ; un tournoi possède plusieurs matrices qui se trouvent dans une même classe à permutation près.

Aussi, il faut faire attention au fait que dans la littérature (par exemple), la notion de matrice de tournoi peut désigner les matrices dans lesquelles les coefficients ne prennent que les valeurs 0 et 1, en notant

si , sinon.

Bien évidemment, ce choix change fortement les propriétés et résultats obtenus, par exemple en étudiant les polynômes caractéristiques de ces matrices (qui ne dépendent pas de l'étiquetage des sommets).

Dans le contexte de la théorie des jeux, la matrice définie en premier est appelé matrice de gain. Le deuxième type de matrice correspond plus généralement en théorie des graphes à une matrice d'adjacence.

Si et désignent respectivement une matrice de gain et une matrice d'adjacence pour un même tournoi avec un même étiquetage des sommets, la relation implique que deux tournois ayant (à permutation près) même matrice d'adjacence ont également même matrice de gain (mais la réciproque est fausse).

Comme le plus petit cycle dans un tournoi est d'ordre 3, le polynôme caractéristique d'une matrice d'adjacence associée à un tournoi, qui est de la forme , est tel que pour compris entre 1 et 5, le coefficient compte le nombre de circuits de longueur exactement , avec en particulier .

On distingue selon la parité de deux cas pour le polynôme caractéristique d'une matrice de gain associée à un tournoi d'ordre :

lorsque , le polynôme est une fonction paire et le rang de la matrice est égal à , lorsque , le polynôme est une fonction impaire et le rang de la matrice est égal à .

On peut déduire ces résultats en étudiant la parité du déterminant de ces matrices, qui peuvent être exprimées en fonction des dérangements (i.e. les permutations sans point fixe), le nombre de dérangements sur éléments étant toujours de même parité que .

Endomorphismes et automorphismes d'un tournoi Tout tournoi possède un groupe d'automorphismes ainsi qu'un monoïde d'endomorphismes. On constate par exemple pour le tournoi à 4 sommets initialement présenté que : le sommet 3 gagne contre les sommets 1 et 2, et ces deux sommets 1 et 2 gagnent contre le sommet 4. Ainsi, les sommets 1 et 2 se comportent de la même façon vis-à-vis des autres sommets de ce tournoi : cela revient à dire que l'on peut définir une composante (différents noms ont été utilisés dans la littérature sur ce sujet, il n'y a pas de standardisation du terme) qui contient les sommets 1 et 2, et cela se traduit par l'existence d'un endomorphisme qui envoie 1 et 2 sur la même image (qui peut être n'importe lequel de ces deux sommets) et qui laisse inchangé les autres sommets.