La théorie des graphes

Table des matières / Sommaire :

Chapitre 1 : Concepts fondamentaux de la
théorie des graphes 07
1- Définitions 11
2- Structure d’un graphe 20
3- Les graphes particuliers 22
4- Algorithme de K-coloration d’un graphe 29
 Exercices (Enoncés) 31
 Solutions 36
Chapitre 2 : Autres représentations d’un graphe 41
1- Définition d’une matrice 42
2- La représentation matricielle 43
3- Le dictionnaire des successeurs et des prédécesseurs 46
4- La représentation sagittale 47
 Exercices (Enoncés) 49
 Solutions 52
Chapitre 3 : La connexité dans un graphe 59
1- Cheminements dans un graphe 60
2- La connexité 64
3- La forte connexité 70
4- La mise en ordre d’un graphe connexe ou la recherche
d’un circuit 76
 Exercices (Enoncés) 84
 Solutions
Chapitre 4 : Les cheminements remarquables 101
1- Cheminements eulériens 102
2- Les chemins hamiltoniens 106
 Exercices (Enoncés) 116
 Solutions 120
Chapitre 5 : Arbres et Arborescences 123
1- Arbres et Arborescences 124
2- Le problème de recherche d’un arbre de poids
minimum 129
3- Le problème de recherche d’un plus court chemin 133
 Exercices (Enoncés) 147
 Solutions 150
Chapitre 6 : Le problème du flot maximum 165
1- Définitions 166
2- Le problème de la recherche du flot maximum 169
 Exercices (Enoncés) 178
 Solutions 181
Chapitre 7 : Le problème d'affectation 199
1- Position du problème 201
2- La résolution du problème d’affectation par la méthode
hongroise 202
 Exercices (Enoncés) 214
 Solutions
Chapitre 8 : Problème d'Ordonnancement 231
1- La représentation du réseau PERT 233
2- La détermination du calendrier des dates au plus tôt et
des dates au plus tard 236
3- Analyse et identification des tâches critiques 239
 Exercices (Enoncés) 243
 Solutions 246
Bibliographie