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

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

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

Mathématiques et Sciences humaines, Tome 120 (1992), p. 53-68 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé
Abstract

Dans cet article, nous définissons un paramètre $σ (T)$ à 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 (T)$ le nombre minimum d’arcs à inverser pour rendre $T$ transitif, nous montrons que l’on a $σ (T) \leq i (T)$ . Nous déterminons ensuite des bornes sur la valeur maximum de $i (T)$ pour les tournois $T$ à $σ$ donné. Nous en déduisons enfin, en fonction du nombre de sommets de $T$ et de $σ (T)$ , un encadrement de l’indice de Slater d’un tournoi quelconque.

In this paper, we define a parameter $σ (T)$ 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 (T)$ the minimum number of arcs to reverse to make $T$ transitive, we show the relation $σ (T) \leq i (T)$ . Then we give bounds on the maximum value of i $(T)$ for tournaments $T$ with given value of $σ$ . Last, according to $σ (T)$ and the number of vertices of $T$ , we deduce bounds of $i (T)$ for any tournament $T$ .

Publié le : 1992-01-01

Zbl 0846.05040 | 3 citations dans Numdam

@article{MSH_1992__118__53_0,
     author = {Charon, Ir\`ene and Germa, Anne and Hudry, Olivier},
     title = {Encadrement de l'indice de slater d'un tournoi \`a l'aide de ses scores},
     journal = {Math\'ematiques et Sciences humaines},
     volume = {120},
     year = {1992},
     pages = {53-68},
     zbl = {0846.05040},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/MSH_1992__118__53_0}
}

Charon-Fournier, Irène; Germa, Anne; Hudry, Olivier. Encadrement de l'indice de slater d'un tournoi à l'aide de ses scores. Mathématiques et Sciences humaines, Tome 120 (1992) pp. 53-68. http://gdmltest.u-ga.fr/item/MSH_1992__118__53_0/

Bibliographie

[1] Barthélémy J.-P., Monjardet B., "The median procedure in cluster analysis and social choice theory", Mathematical Social Sciences 1 (1981), 235-267. | MR 616379 | Zbl 0486.62057

[2] Bermond J.-C., "Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux", Mathématiques et Sciences Humaines 37 (1972), 5-25. | Numdam | MR 300927 | Zbl 0239.05122

[3] Chartrand G., Geller D., Hedetniemi S., "Graphs with forbidden subgraphs", Journal of Combinatorial Theory B, vol.10, n°1 (1971), 12-41. | MR 285427 | Zbl 0223.05101

[4] Guénoche A., "Order at minimum distance of a valued tournament" , présenté à la Table Ronde Modélisation, Analyse et Agrégation des Préférences et des Choix (TRAP 3) (1988), Marseille-Luminy.

[5] Landau H.G. "On dominance relations and the structure of animal societies III. The condition for a score structure", Bulletin of Mathematical Biophysics 13 (1953),1-19. | MR 41412

[6] Moon J.W., Topics on tournaments, Holt, New York,1968. | MR 256919 | Zbl 0191.22701

[7] Reid K.B., "On set of arcs containing no cycles in tournaments", Canadian Mathematical Bulletin 12 (1969), 261-264. | MR 250926 | Zbl 0181.51901

[8] Skolem Th., "On certain distributions of integers in pairs with given differences", Math. Scand. 5 (1957), 57-68. | MR 92797 | Zbl 0084.04304

[9] Slater P. "Inconsistencies in a schedule of paired comparisons", Biometrika 53 (1961), 143-149.