Laboratoire Leibniz, Equipe Graphes

[ Accueil | Membres | Aperçu | Références | Nos sujets | Nos logiciels ]

[ Français | English ]

Un aperçu de la théorie des graphes

Un graphe est une structure très simple puisqu'il est constitué d'un ensemble de sommets et d'une famille de liens (orientés ou non), appelés arêtes ou arcs, entre certains couples de sommets. Un graphe non-orienté peut-être utilisé pour modéliser des relations de conflits entre individus ou objets. Un graphe orienté représente typiquement un réseau de communication, ou encore des relations de domination non-réciproque entre personnes, etc.

On considère généralement que le problème des ponts de Königsberg, résolu par Euler, est le premier résultat formel de la théorie des graphes. Elle s'est surtout développée depuis la deuxième moitié du 19ème siècle (avec Hamilton, Heawood, Kempe, Kirchhoff, Petersen, Tait), et connait un grand boom depuis les années 30 (avec König, Hall, Kuratowski, Whitney, Erdös, Tutte, Edmonds, Berge, Lovász, Seymour, et beaucoup d'autres). Elle présente des liens évidents avec l'algèbre, la topologie, et d'autres domaines de la combinatoire. On trouve des applications de la théorie des graphes -- et souvent aussi la motivation de nouveaux problèmes -- en informatique, recherche opérationnelle, théorie des jeux, théorie de la décision.

La quantité de notions que l'on peut définir sur un graphe est très grande, et plusieurs d'entre elles sont à l'origine de problèmes ou conjectures célèbres (par exemple le problème des quatre couleurs). En fait, un certain nombre de ces notions et questions "théoriques" sont issues non pas de l'imagination des mathématiciens mais de problèmes pratiques qui se modélisent en termes de graphes. De plus, les chercheurs en théorie des graphes s'attachent souvent à trouver des algorithmes efficaces pour résoudre un problème donné.

Les grands problèmes classiques de la théorie des graphes sont : flots et connectivité ("fiabilité" d'un réseau), couplage (affectation), parcours eulérien (qui traverse chaque arête : problème du "postier chinois"), parcours hamiltonien (qui traverse chaque sommet : problème du "voyageur de commerce"), coloration, ensemble stable, ensemble absorbant. Certains de ces problèmes (flot maximum, couplage maximum, parcours eulérien) peuvent être résolus "efficacement", mais la plupart sont très difficiles ("NP-complets").

Une généralisation récente du concept de graphe, introduite par Claude Berge dans les années 60, est celle d'hypergraphe, où les arêtes peuvent être de taille arbitraire et non plus seulement de taille deux.

Nous proposons en annexe une petite bibliographie de références sur la théorie des graphes, et une description plus précise de nos thèmes de recherche.

Quelques adresses à consulter :

Retour à la page de l'équipe