Inversion dans les tournois - 29/07/10
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
Vol 348 - N° 13-14
P. 703-707 - juillet 2010 Retour au numéroBienvenue 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 ?