Tournoi (théorie des graphes)

Tournoi
Un tournoi à 4 sommets. Ce tournoi est 1-paradoxal. Sa suite de scores est (1, 1, 2, 2).
Nombre de sommets	${\displaystyle n}$
Nombre d'arêtes	${\displaystyle {\frac {n(n-1)}{2}}}$

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 ${\displaystyle a}$ bat le participant ${\displaystyle b}$, on dit que ${\displaystyle a}$ domine ${\displaystyle b}$, noté ${\displaystyle a\rightarrow b}$.

En pratique, on étudie généralement les tournois finis. Si son nombre de sommets est ${\displaystyle n}$, ce que l'on appelle ordre du tournoi, il contient ${\displaystyle {\frac {n(n-1)}{2}}}$ arcs.

Du point de vue de la théorie des ensembles, un tournoi est une relation binaire entre ${\displaystyle E}$ et ${\displaystyle E}$ qui est irréflexive et asymétrique. 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^[1] ainsi que [1], ou encore d'applications de ${\displaystyle E\times E}$ antisymétriques à valeurs dans ${\displaystyle \{-1,1\}}$.

Pour tout tournoi ${\displaystyle T=(V,E)}$ et toute partie ${\displaystyle V'\subset V}$, on peut définir un sous-tournoi ${\displaystyle T'=(V',E')}$ en considérant ${\displaystyle E'}$ comme la trace de ${\displaystyle E}$ sur ${\displaystyle V'\times V'}$. En particulier, on peut former des sous-tournois de ${\displaystyle T}$ en considérant pour tout sommet ${\displaystyle x}$ les parties ${\displaystyle T_{.\rightarrow x}}$ et ${\displaystyle T_{x\rightarrow .}}$ qui désignent respectivement les sommets qui dominent ${\displaystyle x}$ et les sommets qui sont dominés par ${\displaystyle x}$.

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.

Chaque tournoi sur un nombre fini de ${\displaystyle n>1}$ sommets contient un chemin hamiltonien, c'est-à-dire un chemin orienté passant par les ${\displaystyle n}$ sommets une fois et une seule. Ce résultat est dû à László Rédei en 1934^[2].

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 ${\displaystyle O(n\log n)}$, sont connus^[3].

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)^[4]. 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 ${\displaystyle v}$ et pour tout ${\displaystyle k\in [3,n]}$ où ${\displaystyle n}$ est le nombre de sommets, il y a un circuit de longueur ${\displaystyle k}$ passant par ${\displaystyle v}$^[5].

Dans les tournois de la vie réelle, on s'attend à ce que, si une personne ${\displaystyle a}$ domine une personne ${\displaystyle b}$, et si ${\displaystyle b}$ domine à son tour une troisième personne ${\displaystyle c}$, alors ${\displaystyle a}$ domine ${\displaystyle c}$. Cela correspond au concept habituel de transitivité pour une relation binaire.

Étant donné un tournoi ${\displaystyle T}$ à ${\displaystyle n}$ sommets, les énoncés suivants sont équivalents :

• ${\displaystyle T}$ est transitif ;
• ${\displaystyle T}$ est acyclique ;
• ${\displaystyle T}$ ne contient pas de circuit de longueur 3 ;
• La suite des scores de ${\displaystyle T}$ (voir plus bas) est ${\displaystyle (0,1,2,\cdots ,n-1)}$ ;
• ${\displaystyle T}$ 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 ${\displaystyle k}$-paradoxal si, pour tout sous-ensemble ${\displaystyle S}$ à ${\displaystyle k}$ éléments de ${\displaystyle V}$, il existe un sommet ${\displaystyle v_{0}}$ dans ${\displaystyle V\setminus S}$ tel que ${\displaystyle v_{0}\rightarrow v}$ pour tous les sommets ${\displaystyle v}$ de ${\displaystyle S}$.

On trouve dans Moon ^[6] la preuve du résultat suivant : pour tout entier ${\displaystyle n>1}$, tout tournoi d'ordre ${\displaystyle 2^{n-1}}$ admet un sous-tournoi transitif d'ordre ${\displaystyle n}$.

Il avait été conjecturé^[7] que la borne ${\displaystyle 2^{n-1}}$ était optimale, cependant il a été prouvé par Reid et Parker^[8] que ce n'est pas le cas ; par exemple tout tournoi d'ordre 14 contient un sous-tournoi transitif d'ordre 5.

La donnée d'un tournoi à ${\displaystyle n}$ sommets nécessite de tracer ${\displaystyle {\frac {n(n-1)}{2}}}$ arcs, ce qui même pour de petites valeurs de ${\displaystyle n}$ 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 ${\displaystyle 3>1>2>4}$, alors la seule relation de ce tournoi qui contredit cet ordre est que le sommet ${\displaystyle 4}$ gagne contre le sommet ${\displaystyle 3}$. Il suffit donc de placer à la suite les sommets ${\displaystyle 3}$ puis ${\displaystyle 1}$ puis ${\displaystyle 2}$ puis ${\displaystyle 4}$, puis tracer le seul arc allant du sommet ${\displaystyle 4}$ vers le sommet ${\displaystyle 3}$ 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.

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)^[9] affirme qu'une suite d'entiers ${\displaystyle (s_{1},s_{2},\cdots ,s_{n})}$ est une suite de scores si et seulement si :

1. ${\displaystyle 0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}}$
2. ${\displaystyle s_{1}+s_{2}+\cdots +s_{i}\geq C_{i}^{2},{\mbox{pour }}i=1,2,\cdots ,n-1}$
3. ${\displaystyle s_{1}+s_{2}+\cdots +s_{n}=C_{n}^{2}}$.

Par exemple, ${\displaystyle (1,1,2,2)}$ est bien une suite de scores, car :

1. ${\displaystyle 0\leq 1\leq 1\leq 2\leq 2}$
2. ${\displaystyle 1\geq C_{1}^{2}}$ car ${\displaystyle 1\geq 0}$ ; ${\displaystyle 1+1\geq C_{2}^{2}}$ car ${\displaystyle 2\geq 1}$ ; ${\displaystyle 1+1+2\geq C_{3}^{2}}$ car ${\displaystyle 4\geq 3}$
3. ${\displaystyle 1+1+2+2=C_{4}^{2}}$ car ${\displaystyle 6=6}$

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^[10].

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.

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, ${\displaystyle x}$ est un roi si et seulement si pour tout autre sommet ${\displaystyle y}$, ou bien ${\displaystyle x\rightarrow y}$, ou bien il existe un autre sommet ${\displaystyle z}$ tel que ${\displaystyle x\rightarrow z}$ et ${\displaystyle z\rightarrow y}$. Cela revient à dire que, si ${\displaystyle x}$ ne gagne pas contre ${\displaystyle y}$, alors on peut trouver un sommet ${\displaystyle z}$ tel que ${\displaystyle x}$, ${\displaystyle y}$ et ${\displaystyle z}$ forment un cycle.

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

Maurer^[11]a 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 ${\displaystyle n}$ est ${\displaystyle >2}$, le nombre de rois d'un tournoi à n sommets peut prendre n'importe quelle valeur entre 3 et ${\displaystyle n}$, à 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)

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 ${\displaystyle A}$ dont les éléments ${\displaystyle a_{ij}}$ valent :

• ${\displaystyle 1}$ si ${\displaystyle v_{i}\rightarrow v_{j}}$,
• ${\displaystyle -1}$ si ${\displaystyle v_{j}\rightarrow v_{i}}$,
• ${\displaystyle 0}$ si ${\displaystyle i=j}$.

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^[12]), la notion de matrice de tournoi peut désigner les matrices dans lesquelles les coefficients ${\displaystyle a_{ij}}$ ne prennent que les valeurs 0 et 1, en notant

• ${\displaystyle 1}$ si ${\displaystyle v_{i}\rightarrow v_{j}}$,
• ${\displaystyle 0}$ 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 ${\displaystyle M_{g}}$ et ${\displaystyle M_{adj}}$ 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 ${\displaystyle M_{g}=M_{adj}-M_{adj}^{t}}$ 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 ${\displaystyle X^{n}-{\underset {i=1}{\overset {n}{\sum }}}a_{i}X^{n-i}}$, est tel que pour ${\displaystyle i}$ compris entre 1 et 5, le coefficient ${\displaystyle a_{i}}$ compte le nombre de circuits de longueur exactement ${\displaystyle n}$, avec en particulier ${\displaystyle a_{1}=a_{2}=0}$.

On distingue selon la parité de ${\displaystyle n}$ deux cas pour le polynôme caractéristique d'une matrice de gain associée à un tournoi d'ordre ${\displaystyle n}$^[13], ^[14] :

• lorsque ${\displaystyle n=2k}$, le polynôme est une fonction paire et le rang de la matrice est égal à ${\displaystyle n}$,
• lorsque ${\displaystyle n=2k+1}$, le polynôme est une fonction impaire et le rang de la matrice est égal à ${\displaystyle n-1}$.

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 ${\displaystyle n}$ éléments étant toujours de même parité que ${\displaystyle n-1}$.

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.

Dit autrement, une composante d'un tournoi est une partie ${\displaystyle C}$ telle que le tournoi peut être partitionné en trois : ${\displaystyle C}$, ${\displaystyle T_{.\rightarrow C}}$ et ${\displaystyle T_{C\rightarrow .}}$, où ${\displaystyle T_{.\rightarrow C}}$ et ${\displaystyle T_{C\rightarrow .}}$ désignent respectivement les choix qui gagnent contre n'importe quel choix de ${\displaystyle C}$ et les choix qui perdent contre n'importe quel choix de ${\displaystyle C}$. Les composantes triviales d'un tournoi sont les singletons et l'ensemble de tous les choix ; lorsque ce sont les seules composantes du tournoi, on dit que le tournoi est simple (ici aussi, la terminologie n'est pas unique ; il ne faut pas confondre cela avec la notion de graphe simple, i.e. un graphe sans boucle ni arêtes multiples).

Lorsqu'un tournoi n'est pas simple, on peut former un tournoi simple appelé sommaire du tournoi en remplaçant chaque composante non triviale par un représentant. En particulier, si un tournoi n'est pas irréductible, on peut considérer les composantes connexes de ce tournoi, et le sommaire correspondant est un tournoi transitif d'ordre égal à ce nombre de composantes.

On trouve toujours parmi les automorphismes d'un tournoi l'identité. S'il s'agit du seul automorphisme, le tournoi est dit asymétrique (à ne pas confondre avec la propriété d'asymétrie du tournoi vu comme une relation binaire, voir plus haut).

Le groupe d'automorphismes d'un tournoi est toujours d'ordre impair. En effet, s'il était d'ordre pair, alors il contiendrait un élément d'ordre 2 ; en posant ${\displaystyle \phi }$ un tel automorphisme, il reste à considérer deux possibilités : ou bien il existe un sommet ${\displaystyle x}$ qui n'est pas fixé par ${\displaystyle \phi }$, ce qui implique par définition que l'on aurait à la fois ${\displaystyle x\rightarrow \phi (x)}$ et ${\displaystyle \phi (x)\rightarrow x}$ (puisque ${\displaystyle \phi (\phi (x))=x}$), ce qui est absurde, soit ${\displaystyle \phi }$ fixe tous les sommets, mais alors ce n'est pas un automorphisme d'ordre 2 puisque c'est alors l'identité. Moon^[15] a montré que tout groupe d'ordre impair est le groupe d'automorphisme d'un tournoi irréductible.

On trouve toujours parmi les endomorphismes d'un tournoi l'identité ainsi que les applications constantes. S'il n'y a pas d'autre endomorphisme, le tournoi est dit rigide.

Ainsi, un tournoi est rigide si et seulement s'il est à la fois simple et asymétrique.

A l'exception du tournoi transitif à deux sommets, tout tournoi simple est irréductible.

Si un tournoi est sommet-transitif, c'est-à-dire tel que pour tout couple de sommets ${\displaystyle (x,y)}$, il existe un automorphisme qui envoie ${\displaystyle x}$ sur ${\displaystyle y}$, alors ce tournoi est régulier (la réciproque est fausse).

On peut définir pour tout tournoi son dual, qui est le tournoi obtenu en inversant toutes les relations entre sommets. Si le dual d'un tournoi est isomorphe à ce tournoi, on parle de tournoi auto-dual.

On trouve parmi les tournois non asymétriques les tournois à rotation, qui sont définis en étiquetant les sommets ${\displaystyle (x_{i})_{1\leq i\leq n}}$ de sorte que la relation entre ${\displaystyle x_{i}}$ et ${\displaystyle x_{j}}$ ne dépend que de la valeur de ${\displaystyle j-i}$ modulo ${\displaystyle n}$ (autrement dit, toutes les relations entre ${\displaystyle x_{i+k}}$ et ${\displaystyle x_{j+k}}$ sont identiques, en considérant des indices modulo ${\displaystyle n}$). Ils sont étudiés avec les tournois sommet-transitifs dans^[16]. Les matrices associées à ces tournois sont circulantes.

Les tournois-intervalle désignent des tournois pour lesquels il est possible d'obtenir un tournoi transitif en enlevant un sommet. Ils ont été étudiés dans^[17].

Les tournois doublement réguliers sont les tournois réguliers pour lesquels pour tout couple de sommets différents ${\displaystyle (x,y)}$, ${\displaystyle T_{.\rightarrow x}\cap T_{.\rightarrow y}}$ est de cardinal constant. Il est prouvé dans ^[18] que ces tournois sont d'ordre ${\displaystyle 4n+3}$ et qu'ils correspondent aux tournois homogènes, c'est-à-dire les tournois pour lesquels tout arc permet de définir un nombre constant de cycles d'ordre 3. Un lien est également établi avec les matrices de Hadamard.

Un jeu à sélection de choix étant probabiliste, on l'étudie en considérant l'espérance obtenue sous la forme ${\displaystyle v_{1}^{t}M_{g}v_{2}}$, où ${\displaystyle M_{g}}$ est une matrice de gain du tournoi et ${\displaystyle v_{1}}$, ${\displaystyle v_{2}}$ des probabilités pour les choix selon l'étiquetage considéré. La théorie associée à l'étude de ce cadre est celle des jeux à somme nulle.

Dans le contexte des jeux à sélection de choix comme le pierre-feuille-ciseaux, ce sont les coordonnées associées d'un vecteur unitaire utilisées comme probabilités qui définissent quelle stratégie adopter pour ne pas perdre en moyenne.

Les tournois positifs sont les tournois pour lesquels l'unique stratégie gagnante (un vecteur ${\displaystyle v_{2}}$ tel que ${\displaystyle M_{g}v_{2}}$ est à coordonnées positives ou nulle, ce qui signifie que ${\displaystyle v_{1}^{t}M_{g}v_{2}\geq 0}$ pour toute stratégie ${\displaystyle v_{1}}$) est telle que chaque sommet possède une probabilité non nulle. Ils ont nécessairement un ordre impair ; ils ont été étudiés entre autres dans plusieurs travaux de Fisher et Ryan^{[19],[20],[13]}, qui ont mis en évidence quelques propriétés contre-intuitives : par exemple, on peut trouver dans un tournoi positif deux choix ${\displaystyle x}$ et ${\displaystyle y}$ tels que le score de ${\displaystyle x}$ est strictement supérieur au score de ${\displaystyle y}$, mais la probabilité du choix ${\displaystyle x}$ est strictement inférieure à la probabilité du choix ${\displaystyle y}$, ou encore on peut trouver un tournoi positif ${\displaystyle T}$ avec deux choix ${\displaystyle x}$ et ${\displaystyle y}$ tels que ${\displaystyle x}$ gagne contre ${\displaystyle y}$, et le fait d'inverser la relation entre ces deux choix (ce qui rend intuitivement ${\displaystyle x}$ "moins bon") crée un nouveau tournoi qui est également positif, avec une probabilité associée au choix ${\displaystyle x}$ supérieure à sa probabilité précédente.

• Un tournoi positif est un tournoi dont tous les sommets sont des rois, la réciproque étant fausse.
• Un tournoi dont tous les sommets sont des rois est irréductible, la réciproque étant fausse.
• A la seule exception du tournoi transitif à 2 sommets, un tournoi simple est irréductible, la réciproque étant fausse.

Les tournois étant des graphes particuliers, ils sont concernés par les problématiques de dénombrement. On peut notamment citer parmi ces questions :

• Combien y a-t-il de tournois d'ordre ${\displaystyle n}$ vérifiant une certaine propriété ? (irréductible, simple, rigide, etc.)
• Combien y a-t-il de tableaux des scores possibles ? (pour tous les tournois, pour les tournois particuliers, etc.)
• Combien faut-il modifier de relations entre deux sommets pour qu'un tournoi vérifie (ou ne vérifie plus) une certaine propriété ?

De nombreuses suites liées à ces questions sont référencées dans l'Encyclopédie en ligne des suites de nombres entiers (OEIS). On peut citer par exemple A000568 qui dénombre tous les tournois d'ordre donné à isomorphisme près ; A051337 pour les tournois irréductibles ; A002785 pour les tournois auto-duaux, ou encore A000571 pour le dénombrement des tableaux de scores.

Une autre problématique importante concerne le nombre d'opérations nécessaires afin de savoir si un tournoi donné vérifie ou non une propriété particulière, ce qui peut revenir à calculer explicitement un objet spécifique associé (par exemple, son groupe d'automorphisme).

Deux tournois de même ordre étant donnés, il est toujours possible d'appliquer un nombre fini d'inversions de relations (i.e. on modifie ${\displaystyle x\rightarrow y}$ en ${\displaystyle y\rightarrow x}$) pour que le premier devienne isomorphe au deuxième. Il faut au minimum ${\displaystyle {\frac {k(k+1)}{2}}={\frac {n^{2}-1}{8}}}$ inversions de relations pour modifier un tournoi régulier à ${\displaystyle n=2k+1}$ sommets en un tournoi transitif, toutefois cette borne n'est pas optimale ; il existe 2 tournois d'ordre 7 pour lesquels 7 inversions de relations sont nécessaires pour transformer l'un en l'autre à isomorphisme près.

Les inversions par rapport à un sommet désignent l'ensemble des inversions qui impliquent l'un des sommets. Deux tournois de même ordre étant donnés, il est possible qu'ils ne soient pas dans la même classe en utilisant uniquement des inversions de sommets, c'est déjà le cas pour les tournois d'ordre 4 pour lesquels il y a exactement 2 classes. Le fait d'appliquer une inversion relative à un sommet revient sur une matrice d'incidence associée au tournoi à changer tous les signes sur une ligne et une colonne de même rang, aussi cette opération ne modifie pas le polynôme caractéristique.

Il est prouvé dans ^[13] que pour les tournois d'ordre impair, il existe exactement un tournoi positif dans chaque classe définie par les inversions de sommets.

Lorsqu'il n'existe pas de vainqueur de Condorcet, une problématique importante de l'étude des tournois est de pouvoir désigner parmi l'ensemble des sommets du tournoi une partie de ces sommets qui représentent les "gagnants" (un ou plusieurs). Il n'existe pas une unique réponse à cette problématique, et il existe même un grand nombre de possibilités de définir ces éléments d'un tournoi.

On appelle solution^[21], ou fonction de choix, toute fonction ${\displaystyle S}$ définie sur l'ensemble des tournois qui satisfait les trois propriétés suivantes :

• la solution est définie à isomorphisme près : si ${\displaystyle \phi }$ est un isomorphisme entre deux tournois ${\displaystyle T_{1}}$ et ${\displaystyle T_{2}}$, alors ${\displaystyle \phi (S(T_{1}))=S(T_{2})}$,
• pour tout tournoi ${\displaystyle T}$, ${\displaystyle S(T)}$ est non vide (une solution doit toujours désigner au moins un gagnant),
• si un tournoi possède un vainqueur de Condorcet, il doit figurer dans l'ensemble des vainqueurs du tournoi pour ${\displaystyle S}$.

Lorsque ${\displaystyle S_{1}}$ et ${\displaystyle S_{2}}$ sont deux solutions, on dit que ${\displaystyle S_{1}}$ est plus fine que ${\displaystyle S_{2}}$ (ou que ${\displaystyle S_{2}}$ est plus grossière que ${\displaystyle S_{1}}$) lorsque pour tout tournoi ${\displaystyle T}$, ${\displaystyle S_{1}(T)}$ est toujours une partie de ${\displaystyle S_{2}(T)}$. Un enjeu est de rechercher des solutions sélectives, dans le sens où elles désignent le moins de gagnants possibles.

D'autres propriétés peuvent être souhaitables pour des solutions. On peut citer par exemple :

• la monotonie : si ${\displaystyle S}$ est une solution du tournoi ${\displaystyle T}$ qui désigne ${\displaystyle x}$ comme gagnant et ${\displaystyle y}$ comme perdant (i.e. ${\displaystyle x}$ est un élément de ${\displaystyle S(T)}$ mais pas ${\displaystyle y}$) et si ${\displaystyle y\rightarrow x}$, alors en modifiant cette relation en ${\displaystyle x\rightarrow y}$, on obtient un tournoi pour lequel ${\displaystyle x}$ est toujours un gagnant pour la solution ${\displaystyle S}$ (on a amélioré ${\displaystyle x}$, donc il gagne "encore plus" que dans le tournoi ${\displaystyle T}$),
• l'indépendance des perdants : si ${\displaystyle S}$ est une solution du tournoi ${\displaystyle T}$ et si ${\displaystyle x}$ et ${\displaystyle y}$ sont deux perdants pour la solution ${\displaystyle S}$, alors en modifiant la relation entre ${\displaystyle x}$ et ${\displaystyle y}$, l'ensemble des gagnants pour la solution ${\displaystyle S}$ reste inchangé,
• l'idempotence : ${\displaystyle S(T)}$ étant un sous-tournoi de ${\displaystyle T}$, la solution ${\displaystyle S}$ est idempotente si ${\displaystyle S(S(T))=S(T)}$,
• la propriété d'Aizerman : si pour tout perdant ${\displaystyle x}$ du tournoi ${\displaystyle T}$ pour la solution ${\displaystyle S}$, ${\displaystyle S(T\setminus \{x\})\subset S(T)}$,
• ce qui est appelé la "strong superset property" dans la littérature anglophone : si ${\displaystyle S}$ est une solution d'un tournoi ${\displaystyle T}$ et si ${\displaystyle x}$ est un perdant de ${\displaystyle S}$, alors en retirant ce sommet du tournoi, on obtient un tournoi dont les gagnants sont exactement les mêmes que ceux de ${\displaystyle T}$ ; cette propriété est équivalente à ce que la solution soit idempotente et vérifie la propriété d'Aizerman,
• la consistance avec la décomposition^[22], qui se comprend ainsi : si un tournoi ${\displaystyle T}$ se décompose selon des composantes ${\displaystyle \{T_{i},1\leq i\leq k\}}$ en un sommaire ${\displaystyle T'}$, alors ${\displaystyle S(T)}$ est obtenu en remplaçant dans ${\displaystyle S(T')}$ chaque représentant du sommaire par ${\displaystyle S(T_{i})}$ ; dit autrement, la solution du tournoi correspond à la solution du sommaire formée avec les solutions des composantes.

Une solution qui vérifie la monotonie et la strong superset property vérifie également l'indépendance des perdants.

Voici quelques exemples parmi les solutions les plus élémentaires pouvant être définies :

• la solution de Copeland : elle consiste à désigner comme gagnant(s) l'ensemble des sommets de score maximal,
• la solution "non-perdants de Condorcet" : on désigne comme gagnant tout sommet qui n'est pas un perdant de Condorcet,
• la solution "top cycle", qui désigne la composante fortement connexe du tournoi à partir de laquelle on peut suivre un chemin permettant d'accéder à tout sommet du tournoi,
• la solution des rois : on désigne l'ensemble des rois du tournoi comme gagnants,
• la solution des rois itérés : lorsque l'on retire les sommets qui ne sont pas des rois d'un tournoi, les sommets restants peuvent ne plus être des rois dans le tournoi restant. Toutefois, en appliquant un nombre fini de fois ce processus (de façon très grossière, au maximum autant de fois que le nombre initial de sommets), on finit toujours par obtenir un ensemble stable de sommets qui sont tous rois, qui forme alors l'ensemble des gagnants pour cette solution,
• la solution BP^[23] (pour Bipartisan Set) qui désigne les sommets associés aux coordonnées strictement positives du vecteur ${\displaystyle M_{g}v_{2}}$, ${\displaystyle v_{2}}$ désignant l'unique stratégie gagnante.

De la plus fine à la plus grossière, on peut ordonner ces solutions de la sorte : BP, rois itérés, rois, top cycle, non perdants de Condorcet.

Une ressource présentant les principaux résultats sur les solutions de tournoi est ^[24].

Un article de synthèse reprenant un grand nombre des éléments présentés ici est ^[25].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Tournament (graph theory) » (voir la liste des auteurs).
• (en) Cet article reprend du contenu de la page Tournament sur PlanetMath sous licence CC_BT-SA.

(en) Eric W. Weisstein, « Tournament », sur MathWorld

• Portail des mathématiques