Tournoi (graphe)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Tournoi.
Tournoi
Image illustrative de l'article Tournoi (graphe)
Un tournoi à 4 sommets. Ce tournoi est 1-paradoxal. Sa suite de scores est (1, 1, 2, 2).

Nombre de sommets n
Nombre d'arêtes \frac{n (n-1)}{2}

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.

Un tournoi est parfois aussi défini comme une relation binaire R sur un ensemble E qui est irréflexive, antisymétrique et totale, c'est-à-dire que pour toute paire (x, y) d'éléments de E, on a soit x = y, soit x\ R\ y, soit y\ R\ x.

Applications[modifier | modifier le code]

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é (en), 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 a bat le participant b, on dit que a domine b.

Chemins et circuits[modifier | modifier le code]

Chaque tournoi sur un nombre fini de n sommets contient un chemin Hamiltonien, c'est-à-dire un chemin orienté passant par les n sommets une fois et une seule (résultat dû à László Rédei en 1934)[1].

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 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 (en) : pour tout sommet v et pour tout k \in [3, n]n est le nombre de sommets, il y a un circuit de longueur k passant par v[4].

Transitivité et tournois paradoxaux[modifier | modifier le code]

Un tournoi transitif à 8 sommets. Dans ce graphe, v_a \rightarrow v_b si et seulement si a < b.

Dans les tournois de la vie réelle, on s'attend à ce que, si une personne a domine une personne b, et si b domine à son tour une troisième personne c, alors a domine 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 T = (V, E) dans lequel :

\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 (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 T=(V, E) est appelé k-paradoxal si, pour tout sous-ensemble S à k éléments de V, il existe un sommet v_0 dans V \setminus S tel que v_0 \rightarrow v pour tous les sommets v de S.

Suite des scores et ensemble de scores[modifier | modifier le code]

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 (s_1, s_2, \cdots, s_n) est une suite de scores si et seulement si :

  1. 0 \le s_1 \le s_2 \le \cdots \le s_n
  2. s_1 + s_2 + \cdots + s_i \ge C^2_i, \mbox{pour }i = 1, 2, \cdots, n - 1
  3. s_1 + s_2 + \cdots + s_n = C^2_n.

Par exemple, (1, 1, 2, 2) est bien une suite de scores, car :

  1. 0 \le 1 \le 1 \le 2 \le 2
  2. 1 \ge C^2_1 car 1 \ge 0 ; 1 + 1 \ge C^2_2 car 2 \ge 1 ; 1 + 1 + 2 \ge C^2_3 car 4 \ge 3
  3. 1 + 1 + 2 + 2 = C^2_4 car 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[modifier | modifier le code]

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 A dont le éléments a_{ij} valent :

  • 1 si v_i \rightarrow v_j
  • -1 si v_j \rightarrow v_i
  • 0 si i = j.

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

Notes et références[modifier | modifier le code]

  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, no 1,‎ 1990, p. 7–20 (DOI 10.1137/0403002).
  3. Paul Camion, « Chemins et circuits hamiltoniens des graphes complets », Comptes Rendus de l'Académie des Sciences de Paris, vol. 249,‎ 1959, p. 2151−2152.
  4. J. W. Moon, « On subtournaments of a tournament », Canadian Mathematical Bulletin, vol. 9, no 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, no 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[modifier | modifier le code]

Sources[modifier | modifier le code]

Lien externe[modifier | modifier le code]