tournoi - graphe -

Imaginez quatre joueuses qui s'affrontent deux à deux, une seule fois, sans match nul. Une flèche relie chaque paire : elle part de la gagnante et pointe vers la perdante. Quand toutes les rencontres ont eu lieu, le dessin obtenu est un tournoi.

La règle décisive tient en peu de mots : entre deux sommets différents, il y a toujours une flèche, et une seule. Le dessin peut changer de forme sans changer les résultats qu'il représente.

Un tournoi est un graphe orienté sans boucle. Ses sommets forment un ensemble de participants ou d'objets. Pour toute paire de sommets distincts nommés x et y, exactement l'un des deux arcs (x, y) et (y, x) appartient au graphe. Il n'y a donc ni paire sans arc, ni paire munie de deux arcs opposés.

On peut le construire en partant d'un graphe complet non orienté, puis en choisissant un sens pour chaque arête. Si le nombre de sommets est noté n, le nombre d'arcs est alors fixé : $\frac{n(n-1)}{2}\backslash frac\{n(n-1)\}\{2\}$. Chaque arc encode le résultat unique d'une rencontre entre deux participants ; son origine représente le vainqueur et son extrémité le perdant.

Le mot « tournoi » désigne la structure orientée, non la manière de dessiner ses sommets. Déplacer les points ou courber les flèches ne modifie pas le tournoi tant que les mêmes paires et les mêmes sens sont conservés.

Un tournoi réunit quatre éléments indispensables. Les sommets représentent les participants. Les paires de sommets recensent toutes les rencontres possibles. Un arc est associé à chaque paire, et son sens enregistre lequel des deux sommets l'emporte. Une boucle n'a aucune place, puisqu'un participant ne se rencontre pas lui-même.

Le choix des sommets détermine les paires à couvrir ; chaque paire impose ensuite exactement un choix entre deux sens. Ces données suffisent à reconstruire tous les résultats et à compter, pour chaque sommet, ses arcs sortants et entrants. La position, la couleur et la courbure des traits servent seulement à rendre le dessin lisible.

Quatre joueuses A, B, C et D disputent toutes les rencontres possibles. Les résultats sont les suivants : A bat B et C ; B bat C et D ; C bat D ; D bat A. La figure matérialise ces six résultats et met en évidence le cycle A, B, D, A.

1. Avec quatre joueuses, il faut couvrir six paires : AB, AC, AD, BC, BD et CD.
2. Pour chaque paire, on trace la flèche de la gagnante vers la perdante.
3. Les nombres de victoires, égaux aux nombres d'arcs sortants, sont A : 2, B : 2, C : 1 et D : 1.
4. Le total vaut 2 + 2 + 1 + 1 = 6, soit exactement une victoire par rencontre.

Le contrôle est direct : chacune des six paires apparaît une fois et aucune paire ne porte deux flèches opposées. Le graphe est donc bien un tournoi. Le cycle rouge montre aussi que les résultats collectifs ne donnent pas nécessairement un classement sans retour : A bat B, B bat D, mais D bat A.

Pour enregistrer une compétition toutes rondes sans match nul, on crée un sommet par participant et on oriente chaque rencontre du vainqueur vers le perdant. Si des matchs n'ont pas encore été joués, un graphe orienté incomplet convient mieux.

Pour vérifier un tableau de résultats, on examine chaque paire. Une case vide signale une rencontre manquante ; deux résultats opposés signalent une répétition ou une incohérence. Dans les deux cas, la structure obtenue n'est pas un tournoi.

Pour comparer les performances, on compte les arcs sortants de chaque sommet. Ce compte donne le nombre de victoires, mais il ne remplace pas l'ensemble du graphe : deux participantes peuvent avoir le même total tout en ayant des résultats directs différents.

Un graphe complet non orienté relie aussi chaque paire de sommets, mais ses arêtes n'ont pas de sens. Dès que chaque arête reçoit une orientation unique, on obtient un tournoi.

Un graphe orienté quelconque peut laisser deux sommets sans arc ou accepter deux arcs opposés. Dans l'exemple, supprimer la rencontre entre C et D suffit à conserver un graphe orienté, mais détruit la propriété de tournoi.

Un tournoi sportif au sens courant peut comporter des éliminations, plusieurs rencontres entre les mêmes personnes ou des matchs nuls. Il ne correspond au tournoi de la théorie des graphes que si chaque paire se rencontre exactement une fois et produit un vainqueur unique.

Avec zéro ou un sommet, la condition portant sur les paires distinctes est automatiquement satisfaite : il n'existe aucune paire à vérifier. Ces cas dégénérés sont des tournois selon la définition formelle, même s'ils ne décrivent aucune rencontre.

Un match nul ne peut pas être représenté par l'absence d'arc sans sortir de la définition. Le symptôme est une paire non orientée. Il faut alors employer un autre modèle de graphe qui code explicitement les résultats nuls.

Deux matchs en sens contraires entre la même paire ne forment pas davantage un tournoi. La présence simultanée de (x, y) et (y, x) révèle le problème ; il faut conserver une seule rencontre ou choisir une structure autorisant plusieurs résultats.

Le nombre de victoires ne produit pas toujours un ordre strict. Dans l'exemple, A et B ont chacune deux victoires, tandis que le cycle A, B, D, A interdit de lire toutes les flèches comme un classement linéaire cohérent.

Le glossaire Graphe orienté et non-orienté précise le rôle du sens des arcs, indispensable pour lire gagnants et perdants.

La fiche Graphe complet présente la structure non orientée dont on choisit le sens de chaque arête pour former un tournoi.

Le chemin hamiltonien fournit ensuite un autre angle de lecture : chercher un parcours qui visite chaque sommet une fois.