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}}}$
modifier

En mathématiques, dans le cadre de la théorie des graphes, un tournoi est un graphe orienté obtenu en orientant chaque arête d'un graphe complet non orienté. On peut aussi le voir comme une orientation (en) d'un graphe complet, ou comme un graphe orienté où chaque paire de sommets est reliée par une arête orientée et une seule.

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.

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}$.

Chemins et circuits

Chaque tournoi sur un nombre fini de ${\displaystyle n}$ 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^[1].

Démonstration

${\displaystyle a}$ est inséré entre ${\displaystyle v_{2}}$ et ${\displaystyle v_{3}}$.

Procédons par récurrence sur le nombre de sommets ${\displaystyle n}$.

Supposons que ce soit vrai pour ${\displaystyle n}$. Soit ${\displaystyle T=(V,E)}$ un tournoi sur ${\displaystyle n+1}$ sommets. Choisissons un sommet ${\displaystyle a}$ de ${\displaystyle V}$. Par hypothèse de récurrence, ${\displaystyle V\setminus \{a\}}$ possède au moins un chemin orienté ${\displaystyle (v_{1},v_{2},\cdots ,v_{n})}$. Soit ${\displaystyle i\in [0,n]}$ l'indice maximal tel que tous les ${\displaystyle v_{j}}$ (${\displaystyle j\leq i}$) vérifient qu'il existe une arête orientée de ${\displaystyle v_{j}}$ en ${\displaystyle a}$. Sur la figure d'exemple, ${\displaystyle i=2}$, car il y a des arêtes de ${\displaystyle v_{1}}$ et de ${\displaystyle v_{2}}$ en ${\displaystyle a}$, mais pas de ${\displaystyle v_{3}}$ en ${\displaystyle a}$.

On remarque que le chemin ${\displaystyle (v_{1},\cdots ,v_{i},a,v_{i+1},\cdots ,v_{n})}$ est un chemin orienté passant par tous les sommets du graphe. La propriété est donc aussi vraie pour ${\displaystyle n+1}$. Comme de plus elle est vraie pour un tournoi à deux sommets, par récurrence, elle est vraie pour tout ${\displaystyle n}$ à partir de deux.

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

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

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}$^[4].

Relations binaires

Un tournoi est parfois aussi défini comme une relation binaire ${\displaystyle {\mathcal {R}}}$ entre ${\displaystyle E}$ et ${\displaystyle E}$ irréflexive dont la fermeture réflexive est totale et antisymétrique. Par définition, si ${\displaystyle a}$ domine ${\displaystyle b}$, alors ${\displaystyle b}$ ne domine pas ${\displaystyle a}$ (antisymétrie); l'un des deux doit être vrai si ${\displaystyle a}$ est différent de ${\displaystyle b}$ (totalité). On peut noter l'antisymétrie de deux manières :

• ${\displaystyle a\rightarrow b\Rightarrow b{\cancel {\mathcal {\rightarrow }}}a}$
• ${\displaystyle \forall (x,y)\in E^{2},x{\mathcal {R}}y\Rightarrow y{\cancel {\mathcal {R}}}x}$ où ${\displaystyle {\mathcal {R}}}$ est la relation de domination.

Avec cette définition, on peut facilement vérifier que cette relation binaire est irréflexive :

• ${\displaystyle \forall x\in E\quad x{\cancel {\mathcal {R}}}x}$ : Aucun élément ne peut être en relation avec lui-même. En effet, un participant ne peut pas se dominer lui-même.

Démonstration

Raisonnons par l'absurde.

Prenons deux participants ${\displaystyle x}$ et ${\displaystyle y}$ tels que ${\displaystyle x=y}$ et ${\displaystyle x{\mathcal {R}}y}$.

Par hypothèse, ${\displaystyle x=y}$, donc cela implique ${\displaystyle x{\mathcal {R}}y\Rightarrow y{\mathcal {R}}x}$.

Or, par définition, ${\displaystyle x{\mathcal {R}}y\Rightarrow y{\cancel {\mathcal {R}}}x}$.

Ce résultat est donc absurde et la relation binaire d'un tournoi est donc irréflexive.

On peut noter qu'un tournoi :

• Peut être transitif. Dans le cas où il ne l'est pas on dit que c'est un tournoi paradoxal.
• Ne peut pas être une relation totale car il n'est pas réflexif.
• Ne peut pas être une relation d'ordre (non stricte) car il n'est pas réflexif, mais c'est un ordre strict s'il n'est pas paradoxal.
• Ne peut pas être une relation d'équivalence car il n'est ni réflexif, ni symétrique.

Les relations binaires de tournoi ne sont pas des matrices de tournoi, on a donc :

• 1 si ${\displaystyle x{\mathcal {R}}y}$
• 0 si ${\displaystyle x{\cancel {\mathcal {R}}}y}$
• 0 si ${\displaystyle x=y}$

Transitivité et tournois paradoxaux

Un tournoi transitif à 8 sommets. Dans ce graphe, ${\displaystyle v_{a}\rightarrow v_{b}}$ si et seulement si ${\displaystyle a<b}$.

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 à la transitivité de la relation binaire de domination.

Énoncé de façon formelle, cela donne la définition suivante :

On appelle transitif un tournoi ${\displaystyle T=(V,E)}$ dans lequel :

${\displaystyle \forall (a,b,c)\in V^{3},(a\rightarrow b{\text{ et }}b\rightarrow c)\Rightarrow a\rightarrow c}$

Étant donné un tournoi T à n sommets, les énoncés suivants sont équivalents :

• T est transitif ;
• T est acyclique ;
• T ne contient pas de circuit de longueur 3 ;
• La suite des scores de T (voir plus bas) est ${\displaystyle (0,1,2,\cdots ,n-1)}$ ;
• T possède exactement un chemin hamiltonien.

Un participant à un tournoi qui gagne toutes les parties est naturellement le gagnant du tournoi. Néanmoins, comme la figure tout en haut de cet article le montre, il est possible qu'un tel gagnant n'existe pas. 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 ${\displaystyle T=(V,E)}$ est appelé 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}$.

Suite des scores et ensemble de scores

Dans un tournoi de la vie de tous les jours, s'il n'y a pas de vainqueur net (quelqu'un qui bat tous les autres), on peut essayer de départager les candidats en calculant leur score, c'est-à-dire le nombre de parties gagnées.

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)^[5] 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^[6].

Matrice de tournoi

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

On appelle matrice de tournoi une matrice carrée ${\displaystyle A}$ dont le é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).

Notes et références

1. (de) Lázló Rédei, « Ein kombinatorischer Satz », Acta Litteraria Szeged, vol. 7,‎ 1934, p. 39−43.
2. (en) A. Bar-Noy et J. Naor, « Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments », SIAM Journal on Discrete Mathematics, vol. 3, n^o 1,‎ 1990, p. 7–20 (DOI 10.1137/0403002).
3. Paul Camion, « Chemins et circuits hamiltoniens des graphes complets », C. R. Acad. Sci. Paris, vol. 249,‎ 1959, p. 2151−2152 (lire en ligne).
4. J. W. Moon, « On subtournaments of a tournament », Canadian Mathematical Bulletin, vol. 9, n^o 3,‎ 1966, p. 297–301 (DOI 10.4153/CMB-1966-038-7, lire en ligne), Théorème 1.
5. (en) H. G. Landau, « On dominance relations and the structure of animal societies. III. The condition for a score structure », Bulletin of Mathematical Biophysics, vol. 15, n^o 2,‎ 1953, p. 143–148 (DOI 10.1007/BF02476378).
6. (en) T. X. Yao, « On Reid Conjecture Of Score Sets For Tournaments », Chinese Sci. Bull., vol. 34,‎ 1989, p. 804−808

Voir aussi

Sources

• (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.

Lien externe

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