par Jean-Claude Fournier

Hermès – Lavoisier, 2011
336 pages en 15,5 × 23, ISBN : 978-2-7462-3215-0

Par rapport à l’édition originale de 2006, cet ouvrage a été notablement enrichi d’un chapitre et demi, d’un appendice et d’un index plus développé. Il contient maintenant :

• Introduction
• Chapitre 1. Généralités.
• Chapitre 2. Arbres.
• Chapitre 3. Colorations.
• Chapitre 4. Graphes orientés.
• Chapitre 5. Recherche arborescente.
• Chapitre 6. Chemins optimaux.
• Chapitre 7. Parcours en largeur lexicographique.
• Chapitre 8. Couplages.
• Chapitre 9. Flots.
• Chapitre 10. Tournées eulériennes.
• Chapitre 11. Tournées hamiltonniennes.
• Chapitre 12 Représentations planes.
• Chapitre 13. Problèmes commentés.
• Appendice. Algorithmes randomisés de graphes.
• Annexe A. Expression des algorithmes.
• Annexe B. Bases de la théorie de la complexité.
• Bibliographie
• Index

Les chapitres 1 à 12 constituent un cours, de niveau licence/master, structuré classiquement en définitions, théorèmes, démonstrations (certaines, quasi-immédiates, sont laissées au lecteur, d’autres intégrées à des exercices, quelques propriétés sont admises), exemples, et exercices. Le plus souvent, à chaque notion est associée la construction d’algorithmes pour la résolution informatique de problèmes ; ces algorithmes sont fréquemment calqués sur la démonstration, constructive, de résultats théoriques. Les prérequis mathématiques sont légers : programmes du secondaire, un peu de calcul matriciel… ; par contre il est nécessaire pour le lecteur d’avoir eu au moins une initiation à l’algorithmique. Les exercices, même ceux signalés par une étoile comme plus difficiles, sont accessibles dès lors qu’on a assimilé le cours.

Les sept problèmes présentés dans le chapitre 13 sont généralement abstraits, internes à la théorie, mais les deux derniers partent d’une question concrète. L’aspect algorithmique y est présent, mais non central. Leur difficulté me semble raisonnable, avec des questions franchement faciles. On y trouve quelques définitions non rencontrées dans le cours.

L’appendice présente des connaissances récentes sur la synergie graphes/probabilités.

L’annexe A précise le pseudo-langage utilisé par l’auteur pour présenter les algorithmes.

L’annexe B apporte des notions indispensables sur la complexité des algorithmes. Ces notions intervenant souvent dans le cours et dans l’appendice, il est, en fait, nécessaire de lire cette annexe en premier !

Ce livre est plein de qualités : clarté, rigueur, précision, sens de la pédagogie, pointes d’humour, bon dosage de la difficulté des exercices, bon équilibre théorie/applications, mise en relief des résultats les plus fondamentaux. On peut regretter qu’aucun des problèmes ne corresponde à l’étude complète d’une situation réelle, avec modélisation par un graphe, construction (ou choix) d’un algorithme, application de l’algorithme et conclusion. Quoi qu’en dise l’avant-propos, il subsiste quelques rares erreurs. Mais le regret principal que j’exprimerai est que les exercices et problèmes ne soient pas corrigés. C’est d’autant plus fâcheux que, s’agissant d’une branche des mathématiques bien distincte, le débutant manque de repères et de modèles pour rédiger les solutions, pour savoir ce que l’on peut considérer comme évident, etc. Certes, à l’université les enseignants répondent à ces questions ; mais, complété par ces corrigés (pourquoi pas sur un site Internet ?), ce livre serait, de plus, parfaitement adapté à une auto-formation.