par Alain Bretto, Alain Faisant, François Henecart

Éditions Springer, 2012
392 pages 15,5 × 23,5, prix 55 €, ISBN : 978-2-8178-0280-0

Les dix chapitres de ce cours recouvrent l’ensemble de la théorie des graphes, des notions de base jusqu’aux développements les plus récents, y compris des conjectures encore ouvertes ; ils ont pour titres :

• Concepts fondamentaux
• Quelques graphes remarquables
• (Di)graphes et structures de données
• Connexité et flots dans les réseaux
• Graphes planaires
• Théorie algébrique
• Coloration
• Couplage et factorisation
• Automorphismes — Théorie spectrale
• Autres perspectives.

Ils sont complétés par une bibliographie, un index et une liste de symboles, très complets.

La plupart des notions sont introduites par le problème « concret » qui est à leur source (ponts de Königsberg, problème des mariages, coloration de cartes, …) ; mention est faite de leurs domaines d’application (télécommunications, recherche opérationnelle, informatique parallèle, algorithmique, physique statistique, …) mais la théorie est ensuite développée abstraitement, et classiquement : définitions, propriétés et théorèmes, démonstrations rigoureuses (sauf les plus faciles, laissées au lecteur, et celles de quelques résultats récents, trop difficiles). on trouve, chaque fois que c’est utile, des rappels relatifs aux autres domaines mathématiques qui interfèrent avec les graphes : topologie, algèbre matricielle, théorie des groupes, … L’aspect algorithmique est omniprésent.

Des exercices sont inclus au fil du texte ; il s’agit d’applications directes du cours, ou de démonstrations simples de propriétés ; ils ne présentent guère de difficulté. on peut regretter l’absence de problèmes globaux, avec modélisation d’une situation concrète.

L’ouvrage, rédigé de façon claire, vivante et imagée, est accessible aux étudiants en licence ou master de mathématiques ou d’informatique, même en début de cursus ; il pourra également intéresser les chercheurs et les ingénieurs, mais aussi les enseignants du secondaire qui, ayant maintenant à enseigner les premières notions de cette théorie, voudraient aller plus loin, dominer le sujet, prendre du recul.