Thèse Guyslain NAVES

L'étude des cycles, flots et chemins des graphes est intimement liée au développement de l'optimisation combinatoire. Dans l'introduction nous mettons en parallèle ces concepts à partir de résultats classiques, et les deux autres parties de la thèse développent les nouveaux résultats dans deux directions différentes. La première porte sur les problèmes d'existence de multiflots entiers. Plusieurs paramètres naturels s'appliquent à ces problèmes, générant plus d'une centaine de cas. Après un rappel des résultats de la littérature sous une forme synthétique, nous résolvons plusieurs problèmes ouverts. En particulier, nous montrons que trouver deux flots disjoints dans les graphes planaires est un problème NP-complet. Nous donnons aussi un algorithme polynomial pour router les digraphes planaires acycliques eulériens, lorsque le nombre de classes d'arcs de demande est fixé. Ensuite, nous nous intéressons au problème consistant à trouver une plus courte marche fermée passant par tous les sommets d'un graphe. Spécifiquement, nous cherchons à caractériser les graphes pour lesquels une bonne caractérisation est donnée par des empilements d'ensembles éclatants. Nous présentons quelques résultats de nature polyédrale, puis étudions le cas des cographes et des graphes d'intervalles.