Abstract FR:

Soient G=(V,E) un graphe et r appartient N IVI un vecteur de types de connexité associés aux sommets. Un sous-graphe est dit arête-fiable si entre chaque paire de sommets u, v de V, il existe au moins min {r(u), r(v)} chaînes arête-disjointes. Si les arêtes sont munies de poids, le problème de conception de réseaux fiables consiste à déterminer un sous-graphe arête-fiable de G de poids minimum. Ce problème a des applications dans les domaines des télécommunications et des transports. Dans cette thèse, nous étudions une approche polyèdrale pour ce problème. Tout d'abord, nous décrivons certaines facettes pour le polyèdre associé, lorsque les types de connexités sont sont tous égaux à k, où k est un entier supérieur ou égal à 3. Nous nous intéressons ensuite aux contraintes dites de partition. Nous montrons que dans un graphe décomposable par des 1- et 2-sommets d'articulations, les contraintes de partition peuvent être séparées en temps polynomial si elles le peuvent dans les pièces du graphe. Comme conséquence, nous obtenons un algorithme de séparation de ces contraintes dans les graphes série-parallèles. Nous étudions également le polyèdre des solutions du problème du sous-graphe (1,k)-connexe, ou k est un entier supérieur ou égal à 2, qui correspond au problème quand r appartient {1,k} lvl. Nous donnons la description exacte du polyèdre pour une classe particulière de graphes et nous introduisons une nouvelle classe de contraintes valides. Enfin nous considérons le problème du sous-graphe (1,2,3)-arête connexe et nous développons un algorithme de coupes et branchements