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.