Abstract FR:

Dans la premiere partie, nous etudions les graphes induits par les sommets et les facettes de differents polyedres combinatoires ayant des applications en optimisation combinatoire, par exemple: le probleme de la coupe maximale et le probleme du multiflot, notamment le polytope des coupes et le polytope des metriques. Ces deux polytopes convexes de meme dimension sont respectivement engendres par leurs sommets et leurs facettes. En particulier, nous caracterisons localement le squelette du dual du polytope des metriques pour n quelconque, le squelette du dual du polytope des coupes pour les premieres valeurs de n, sa restriction a diverses familles de facettes et la restriction du squelette du polytope des metriques a diverses familles de sommets. Nous donnons egalement differents resultats concernant les sommets a coordonnees entieres du polytope des metriques et les facettes de taille maximale du polytope des coupes. Finalement, ces divers resultats nous permettent de presenter plusieurs conjectures sur la structure de ces polytopes qui soulignent l'importance du role joue par les sommets a coordonnees entieres du polytope des metriques et par les facettes de taille maximale du polytope des coupes. Dans la deuxieme partie, ou l'on considere des polytopes convexes quelconques, nous donnons une borne inferieure pour le nombre de sommets d'un polytope convexe de dimension d ayant m faces de dimension i pour chaque i inferieur a la moitie de la dimension d. En utilisant les conditions de mcmullen, nous demontrons que ces bornes, pour m plus grand qu'une petite constante, sont atteintes par des polytopes simpliciaux et i-amicaux