Return to search

Polyèdres et structures combinatoires

On établit la dimension de l'enveloppe convexe des couplages maximums d'un graphe, avec un résultat sur le cas des couplages parfaits. On étudie le squelette des polytopes. On démontre que si chaque sommet du polytope peut être représenté par un vecteur à valeurs 0 ou 1 alors ce squelette est soit un hypercube soit Hamilton connexe. On considère le polyèdre associé au problème du voyageur de commerce. Une méthode de décomposition permet de décrire entièrement ce polyèdre dans un cas particulier. Pour une version dite graphique de ce problème, on donne un ensemble d'inéquations nécessaires a la description du polyèdre associé.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00307745
Date02 December 1983
CreatorsNaddef, Denis
Source SetsCCSD theses-EN-ligne, France
Languagefra
Detected LanguageFrench
Typehabilitation ࠤiriger des recherches

Page generated in 0.0019 seconds