Maille cyclique des digraphes.

Pierre Charbit
Université Lyon I


Résumé:

En 2003, Stéphane Bessy et Stéphan Thomassé ont donné une preuve d'une conjecture de Tibor Gallai selon laquelle le nombre minimal de circuits nécessaires pour recouvrir les sommets d'un digraphe est inférieur à la taille maximale d'un stable. Leur démonstration mettait en lumière l'intéret de considerer des plongements circulaires de digraphes lorsque l'on s'intéresse aux circuits. Dans cet exposé, je montrerai comment l'utilisation de méthodes de dualitmé en programmation linméaire peut permettre de mieux comprendre certaines proprimétés de ces plongements, ainsi que de donner des preuves très simples de leurs résultats ou d'autres théorrèmes de type min-max. En particulier, je m'interesserai à la notion de maille cyclique d'un digraphe, qui est le pendant de la notion de maille (longueur minimale d'un circuit) dans le contexte des plongements circulaires. Cette notion fait aussi l'objet d'un théorrème min-max dont je montrerai une application à un résultat de partitionnement des sommets d'un digraphe en sous digraphes acycliques.

Retour au séminaire