Abstract FR:

Cette these est composee de deux parties: la premiere partie porte sur le probleme des absorbants de poids minimum. Nous nous interessons au polytope des solutions de ce probleme. Dans un premier temps, nous decrivons certaines facettes de base et nous discutons de certaines proprietes structurales de ce polytope. Par la suite, nous considerons ce polytope dans les graphes decomposables par des sommets d'articulation. Si g est un graphe qui se decompose en deux graphes g#1 et g#2, alors on montre que le polytope des absorbants dans g peut etre decrit a partir de deux systemes lineaires lies a g#1 et g#2. Ceci donne lieu a une technique permettant de caracteriser le polytope des absorbants dans les classes de graphes qui sont recursivement decomposables. Nous obtenons egalement une procedure de composition de facettes dans ce type de graphes. Nous montrons que le probleme de l'absorbant peut etre aussi decompose. Des applications de cette technique sont discutees pour la classe des cactus. Nous etudions aussi des procedures generales de construction de facettes. Dans la deuxieme partie, nous etudions le probleme du flot quand les couts fixes et des couts variables sont associes aux arcs du graphe. Nous developpons une approche polyedrale pour ce probleme. Nous introduisons des nouvelles contraintes valides pour le polyedre associe, appelees contraintes de coupes. Ces contraintes sont utilisees par la suite dans une methode de coupes pour resoudre des instances du probleme. Les resultats experimentaux montrent que ces contraintes peuvent etre utiles pour la resolution du probleme dans les graphes peu denses