Enveloppes Convexes Des Plans Projectifs Fini

Le probleme fondamental de l'approche polyedrale est le suivant: Etant donne un ensemble X de points de l'espace Euclidien, determiner un systeme d'inegalites lineaire decrivant l'enveloppe convexe de X. Generalement X est un ensemble de points a coordonnees entieres (voire en 0-1) qui represente les solutions realisables d'un programme lineaire en nombres entiers. A l'origine cette approche a ete introduite par Jack Edmonds qui donna la premiere caracterisation du polytope des couplages d'un graphe, c'est-a-dire de l'enveloppe convexe des vecteurs caracteristiques (dans {0,1}E) des couplages d'un graphe G = (V, E).