Théories des graphes

O Cogis & C Schwartz

Présentation

La théorie des graphes est issue de problèmes ayant l'allure de jeux mathématiques, comme le problème du «voyageur de commerce» : tracer le plus court chemin que pourrait emprunter un représentant pour rendre visite à ses clients dans une série de villes, en ne passant qu'une seule fois dans chaque ville. Elle a d'abord trouvé des applications en théorie des probabilités. Ses applications actuelles sont orientées vers la logistique et l'informatique (optimisation des réseaux de transport de personnes, de marchandises ou de données, optimisation des itinéraires, du stockage, Internet, GPS, architecture des ordinateurs) et elle suscite de ce fait un intérêt grandissant. En retour, on utilise abondamment l'informatique pour donner des solutions pratiques aux problèmes de graphes que l'on se pose, d'où l'importance donnée dans ce livre aux algorithmes. La théorie des graphes a été introduite il y a une quinzaine d'années dans les programmes du secondaire français, et ce livre a été écrit à cette occasion, à l'intention des professeurs.

LE PUBLIC
Étudiants en mathématiques appliquées et en informatique. Enseignants de mathématiques dans le secondaire, CDI des lycées.

LES AUTEURS
Olivier Cogis est professeur d'informatique à l'université de Montpellier.
Claudine Schwartz est professeur de statistique(émérite) à l'université de Grenoble.

LE LIVRE
Un graphe se définit simplement comme un ensemble de points dont certains sont reliés par des lignes. On peut être surpris que des objets aussi pauvres que les graphes puissent donner lieu à une théorie aussi riche. La réponse est certainement dans la variété des problèmes posés par les applications. Le livre de Cogis et Schwartz, qui n'oublie pas l'anecdote et les applications, présente la théorie de graphes comme une théorie mathématique, avec des définitions et des énoncés précis, et des démonstrations complètes, ce qui est nécessaire pour permettre à l'étudiant de comprendre et d'élaborer lui-même les algorithmes de résolution des problèmes qui forment une partie essentielle du livre. La première édition de ce livre a été publiée en 2003. Le texte a été revu pour cette nouvelle édition en «poche».