Routages optimaux : tours, flots et chemins.

The study of cycles, flows and paths in graphs is closely related to the development of combinatorial optimization. In the introduction, we explicit this relationship by using classical results, and the two next parts develops new results in two distinct directions. First, we look at problems of existence of integer multiflow. Many parameters can naturally be applied to them. By combination they yield a hundred distinct cases. We present the state of the art in a synthetic way, and then prove some new results. We prove the NP-completeness of finding two disjoint flows in planar graphs. We also give an algorithm for solving multiflow problems in acyclic digraphs with Euler condition, when the number of classes of demand is bounded. Then, we consider the problem of finding a shortest spanning closed walk. More precisely, when does this problem admit a good characterisation based on packing of scattering sets ? We give some polyhedral results, and investigate the case of cographs and interval graphs.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éciquement, 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