Étude polyédrale de quelques problèmes de partionnement dans les graphes

Sous sa forme générale, le problème de partitionnement dans un graphe consiste à partitionner l’ensemble des sommets du graphe en k classes, où k est donné, la cardinalité de chaque classe devant être comprise dans un intervalle donné, tout en minimisant le coût d’une certaine fonction définie sur le graphe. Parfois, on a aussi des contraintes sur la cardinalité de l’ensemble des arêtes entre deux classes de la partition. Ce problème a des applications importantes, entre autres, dans les domaines des télécommunications, du calcul parallèle, des algorithmes du type “divide-and-conquer”. Dans cet exposé, nous considérons, d’un point de vue polyédral, trois cas particuliers de cette classe de problèmes : le problème de la multicoupe, le problème du séparateur et le problème de la coupe séparatrice.