Adhérer ou faire un don

Les graphes par l’exemple

par F. Droeske, M. Hallin, Ci. LeFebvre, Ed. Ellipses.

288 pages en 17.5 $\times$ 26.

Le contenu de l’ouvrage contient les enseignements donnés en école de commerce, en section économique de l’Université libre de Bruxelles et à l’Institut d’enseignement Supérieur Lucien Cooremans de la Ville de Bruxelles. Les exemples et les exercices jouent un rôle essentiel dans l’ouvrage.

Chacun des huit chapitres est ainsi composé : les définitions, les concepts et les résultats mis en jeu, l’exposé d’un ou plusieurs algorithmes en rapport avec le problème fondamental considéré, les organigrammes associés, suivis d’exemples simples en illustrant l’emploi très en détail, enfin une série d’exercices proposés dont les solutions ou les réponses sont regroupées en fin de chapitre.

Le premier chapitre présente les généralités sur les graphes. Il ne faut pas se laisser décourager par le premier exemple qualifié de simple, par humour peut-être ; la suite fait parcourir de nombreux exercices de traduction sous forme de graphe d’un grand nombre de situations concrètes très variées .
On y retrouve le problème connu « du loup, de la chèvre et du chou », rendu visuellement limpide par un graphe, les ponts de Koenigsberg, et d’autres de ce genre. Mais il y a aussi bien des illustrations inspirées par la vie de tous les jours, du simple au plus complexe, qui, la dernière, fait sentir la nécessité d’algorithmes et d’organigrammes.

Dans les chapitres suivants on trouve successivement : quelques problèmes importants relatifs aux graphes orientés (fermeture transitive, recherche de circuit, de noyau), les méthodes « Électre » dans l’emploi des graphes pour la décision multicritère, des aspects de la théorie des graphes non orientés (coloration des sommets, des arêtes, coupla- ge maximum, arbre partiel de poids minimum), les chemins de longueur minimale ou maximale, les problèmes de flot (chap. VI), ceux de transport et d’affectation (chap. VII), enfin les problèmes d’ordonnancement (chap. VIII).

Le livre comporte au début une table des matières et une liste des organigrammes, et à la fin un index.

L’ensemble est très clair, d’une bonne présentation typographique. _ Cet ouvrage paraît bien adapté à l’apprentissage professionnel de l’emploi des graphes, avec possibilité d’aborder tel ou tel chapitre directement, en possédant une bonne pratique des organigrammes, et de leur traduction informatique (non abordée).

À un niveau plus pédagogique, sans être exhaustif, il dégage bien les notions et les problèmes essentiels de la théorie des graphes, sans démonstration, et donne beaucoup d’exemples très variés adaptables, à petite échelle, à une première familiarisation avec la richesse des applications des graphes.

(Article mis en ligne par Armelle BOURGAIN)