Abstract FR:

En 1963, T. Gallai conjectura que les sommets de tout digraphe fortement connexe D peuvent être couverts par au plus alpha(D) circuits, où alpha(D) désigne la stabilité de D. Cette thèse présente une preuve de cette conjecture obtenue conjointement avec S. Thomassé et pour laquelle de nouvelles structures combinatoires sont introduites: les ordres cycliques pour digraphes fortement connexes. Un second résultat est présenté: pour un digraphe fortement connexe D, il existe au plus 2. Alpha(D)-1 circuits couvrant le digraphe D et dont l'union est fortement connexe et possède au plus |D|+2. Alpha(D)-2 arcs. De ce résultat dérive un algorithme d'approximation polynomial pour trouver le sous digraphe couvrant fortement connexe de D ayant un nombre minimal d'arcs. L'aspect algorithmique des décompositions est traité. De plus, deux conjectures sont étudiées sur le rôle que la connectivité du digraphe D pourrait jouer dans l'existence de différentes décompositions en chemins ou circuits.