S'abonner

Inversion dans les tournois - 29/07/10

Doi : 10.1016/j.crma.2010.06.022 
Houmem Belkhechine a , Moncef Bouaziz b , Imed Boudabbous c , Maurice Pouzet d, e
a Faculté des Sciences de Gabès, Gabès, Tunisie 
b Institut des technologies médicales, Tunis, Tunisie 
c Institut Préparatoire aux Études d'Ingénieurs de Sfax, Sfax, Tunisie 
d ICJ, mathématiques, Université Claude-Bernard Lyon 1, 69622 Villeurbanne, France 
e Department of Mathematics and Statistics, The University of Calgary, Calgary, Alberta, Canada 

Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.

pages 5
Iconographies 0
Vidéos 0
Autres 0

Résumé

Nous considérons la transformation qui inverse tous les arcs d'une partie X de l'ensemble des sommets d'un tournoi T. L'indice de T, noté  , est le plus petit nombre de parties dont il faut inverser les arcs pour ramener T à un tournoi acyclique. Il apparaît que les tournois critiques et les tournois  -critiques peuvent être définis au moyen d'inversions, les premiers étant d'indice un ou deux, les seconds d'indice au plus quatre. On peut voir   comme le minimum de la distance de T aux tournois acycliques définis sur le même ensemble de sommets ; la distance entre deux tournois T et   peut être également interprétée comme la dimension booléenne d'un graphe, celui-ci étant la somme booléenne de T et  . Sur n sommets, la distance maximale vaut   tandis que  , le maximum des indices des tournois à n sommets, satisfait les inégalités   pour  . Soit   (resp.  ), la classe des tournois finis (resp. au plus dénombrables) T tels que  . La classe   est déterminée par un nombre fini d'obstructions ; nous donnons une description morphologique des éléments de   et décrivons ses obstructions. Nous décrivons aussi un tournoi universel de la classe  .

Le texte complet de cet article est disponible en PDF.

Abstract

We consider the transformation reversing all arcs of a subset X of the vertex set of a tournament T. The index of T, denoted by  , is the smallest number of subsets that must be reversed to make T acyclic. It turns out that critical tournaments and  -critical tournaments can be defined in terms of inversions (at most two for the former, at most four for the latter). We interpret   as the minimum distance of T to the transitive tournaments on the same vertex set, and we interpret the distance between two tournaments T and   as the Boolean dimension of a graph, namely the Boolean sum of T and  . On n vertices, the maximum distance is at most  , whereas  , the maximum of   over the tournaments on n vertices, satisfies  , for  . Let   (resp.  ) be the class of finite (resp. at most countable) tournaments T such that  . The class   is determined by finitely many obstructions. We give a morphological description of the members of   and a description of the critical obstructions. We give an explicit description of a universal tournament of the class  .

Le texte complet de cet article est disponible en PDF.

Plan

Plan indisponible

© 2010  Publié par Elsevier Masson SAS de la part de Académie des sciences.
Ajouter à ma bibliothèque Retirer de ma bibliothèque Imprimer
Export

    Export citations

  • Fichier

  • Contenu

Vol 348 - N° 13-14

P. 703-707 - juillet 2010 Retour au numéro
Article précédent Article précédent
  • Editorial Board
| Article suivant Article suivant
  • Type-definable groups in C-minimal structures
  • Fares Maalouf

Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.

Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’achat d’article à l’unité est indisponible à l’heure actuelle.

Déjà abonné à cette revue ?

Mon compte


Plateformes Elsevier Masson

Déclaration CNIL

EM-CONSULTE.COM est déclaré à la CNIL, déclaration n° 1286925.

En application de la loi nº78-17 du 6 janvier 1978 relative à l'informatique, aux fichiers et aux libertés, vous disposez des droits d'opposition (art.26 de la loi), d'accès (art.34 à 38 de la loi), et de rectification (art.36 de la loi) des données vous concernant. Ainsi, vous pouvez exiger que soient rectifiées, complétées, clarifiées, mises à jour ou effacées les informations vous concernant qui sont inexactes, incomplètes, équivoques, périmées ou dont la collecte ou l'utilisation ou la conservation est interdite.
Les informations personnelles concernant les visiteurs de notre site, y compris leur identité, sont confidentielles.
Le responsable du site s'engage sur l'honneur à respecter les conditions légales de confidentialité applicables en France et à ne pas divulguer ces informations à des tiers.


Tout le contenu de ce site: Copyright © 2024 Elsevier, ses concédants de licence et ses contributeurs. Tout les droits sont réservés, y compris ceux relatifs à l'exploration de textes et de données, a la formation en IA et aux technologies similaires. Pour tout contenu en libre accès, les conditions de licence Creative Commons s'appliquent.