Aller au menu Aller au contenu
UGA
Optimisation Combinatoire
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Optimisation Combinatoire

Théorie des graphes

Notre équipe est reconnue depuis de nombreuses années dans le domaine de la théorie des graphes. C'est un domaine d'expertise que nous souhaitons continuer de développer. Plus précisément, nous nous intéressons à la coloration des graphes et des hypergraphes. Colorier les sommets d'un graphe consiste à leur affecter des couleurs de sorte qu'il n'y ait pas deux sommets de même couleur reliés par une arête. De plus, on désire généralement utiliser le moins de couleurs possible.
Coloration du graphe de Petersen


De nombreux problèmes de Recherche Opérationnelle, et leurs applications aux systèmes de production, s'expriment par la recherche d'une coloration optimale des sommets d'un graphe. Le problème de coloration est en général difficile (NP-complet), mais il est intéressant de trouver des classes de graphes pour lesquelles on peut le résoudre en temps polynomial. Les graphes « parfaits » ont cette propriété, mais le seul algorithme de coloration connu n'est pas utilisable en pratique, et la recherche d'un algorithme efficace reste un défi pour les années à venir. La détermination de sous-classes de graphes parfaits est l'occasion d'étudier des propriétés particulières (le plus souvent algorithmiques).

Couplages parfaits

Nous nous intéressons également à des problèmes de couplages parfaits dans les graphes : il s'agit d'une partition des sommets en paires de voisins. L'existence d'un couplage parfait dans certains graphes précis (notamment dans les graphes bipartis) est liée à de nombreux problèmes pratiques de Recherche Opérationnelle. Nous nous intéressons également au nombre de couplages parfaits (quand on sait garantir l'existence d'au moins un couplage parfait) : le calcul approché de ce nombre a des applications en physique statistique et en chimie moléculaire.

Rédigé par Louis Esperet

mise à jour le 12 mars 2015

  • Tutelle CNRS
  • Tutelle Grenoble INP
  • Université Joseph Fourier
  • Tutelle UMR
Communauté Université Grenoble Alpes
×
Afin d'améliorer la qualité de ce site et le service rendu à l'utilisateur, nous utilisons des cookies de mesure d’audience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies à cette fin. Pour en savoir plus