Encadrement de l'indice de slater d'un tournoi à l'aide de ses scores

Charon-Fournier, Irène  ; Germa, Anne  ; Hudry, Olivier 

Mathématiques informatique et sciences humaines, Tome 118 (1992), pp. 53-68

Résumé (VO)

Dans cet article, nous définissons un paramètre $\sigma \left(T\right)$ à partir des scores d’un tournoi $T$. Ce paramètre évalue un éloignement entre le tournoi $T$ et les tournois transitifs de même ordre. Appelant $i\left(T\right)$ le nombre minimum d’arcs à inverser pour rendre $T$ transitif, nous montrons que l’on a $\sigma \left(T\right)\le i\left(T\right)$. Nous déterminons ensuite des bornes sur la valeur maximum de $i\left(T\right)$ pour les tournois $T$ à $\sigma$ donné. Nous en déduisons enfin, en fonction du nombre de sommets de $T$ et de $\sigma \left(T\right)$, un encadrement de l’indice de Slater d’un tournoi quelconque.

Abstract

In this paper, we define a parameter $\sigma \left(T\right)$ from the scores of a tournament $T$. This parameter measures a remoteness between the tournament $T$ and the transitive tournaments of same order. Calling $i\left(T\right)$ the minimum number of arcs to reverse to make $T$ transitive, we show the relation $\sigma \left(T\right)\le i\left(T\right)$. Then we give bounds on the maximum value of i$\left(T\right)$ for tournaments $T$ with given value of $\sigma$. Last, according to $\sigma \left(T\right)$ and the number of vertices of $T$, we deduce bounds of $i\left(T\right)$ for any tournament $T$.