À la découverte des graphes et des algorithmes de graphes

À la découverte des graphes et des algorithmes de graphes

Un graphe est un objet abstrait très simple, composé d’éléments (les sommets) et de relations entre ces éléments (les arêtes). Un graphe permet de représenter des liens d’amitié entre des gens, des lignes aériennes entre des villes, des câbles entre des ordinateurs, des références entre des pages web, etc. Ce concept est utilisé dans l’industrie (informatique, recherche opérationnelle) mais il intéresse aussi les chercheurs (étude des réseaux sociaux, biologie, mathématiques…).
En s’appuyant sur de multiples exemples et illustrations, ce livre propose une initiation aux graphes et à certaines de leurs propriétés (représentation planaire, cycles eulériens, hamiltoniens…). En évitant tout jargon technique, il décrit des algorithmes classiques (parcours en largeur, en profondeur, Prim, tri topologique, flots…) et d’autres, plus avancés, permettant de traiter les problèmes de coloration, de couverture, d’arbre de Steiner, du voyageur de commerce etc. Cet ouvrage, tout en couleurs, est une invitation à la découverte, sans prérequis, d’un sujet que nul ne devrait ignorer, situé entre les mathématiques discrètes et l’informatique.

Table des matières

Table des matières
À la découverte des graphes et des algorithmes de graphes 1
À LA DÉCOUVERTE DES GRAPHES ET DES ALGORITHMES DE GRAPHES 2
Table des matières 4
1. Présentation 8
2. Un graphe. Qu'est-ce que c'est ? 14
3. Parcourons un graphe en largeur 24
4. Parcourons un graphe en profondeur 42
5. Un arbre très léger 48
6. Construisons un arbre à partir d'une suite de degrés 56
7. Dessinons un graphe dans le plan sans croiser les arêtes 62
8. Passons une seule fois par chaque arête 72
9. Passons une seule fois par chaque sommet 80
10. Travaillons ensemble 90
11. Les flots : un problème de plomberie informatique 98
12. Fabriquons une notice de montage 114
13. À vous de jouer ! 122
14. Des problèmes très difficiles à résoudre 138
15. Colorions les graphes 144
16. Des couplages 154
17. Une petite couverture 158
18. Le problème du voyageur de commerce 174
19. Retour sur l'arbre léger 186
20. Un arbre couvrant minimisant la somme des distances 198
21. Découper un graphe en deux grâce à une pièce de monnaie 202
22. Un avenir incertain 208
23. Autres problèmes et autres approches 218
24. Quelques références et compléments 226
Index 230

Compléments