← Retour
Les Fondements de la Théorie des Graphes
Disponible
Pages 442
Dimensions 16*23,5
Publication 2024-01-04
Éditeur —
Papier : 1 950.00 DA
Numérique: 975.00 DA
Cet ouvrage est un recueil de cours et d’exercices et le fruit de presque dix (10) ans d’enseignement du module « Fondements de la Théorie des Graphes » pour les classes : 3ième année ingénieurs et Licence LMD, 2ème année Licence LMD, Master LMD, ainsi qu’une lecture qualitative de dizaine d’ouvrages de recherche opérationnelle RO et de théorie des graphes. L’ouvrage contient l’essentiel des concepts de la théorie des graphes, présentés d’une manière très simple avec des exemples illustratifs clairs. En plus, chaque chapitre est clôturé par une collection d’exercices avec leurs solutions. A la fin de l’ouvrage, deux annexes très importantes sont ajoutées, la première comporte des prototypes d’examens avec leurs corrigés-type, la deuxième comporte tous les algorithmes de l’ouvrage avec des pseudo- codes plus ou moins détaillés.
Afficher la table des matières
Dédicace 03
Avant propos 05
Table de matières 07
Introduction 15
Chapitre 1: Notions et concepts de bases 19
1.1. Définition d'un Graphe 20
1.2. Propriétés d'un graphe7 20
1.3. Quelques exemples de graphes
1.4. Graphe orienté et graphe non orienté
1.5. Définition d'un graphe valué 23
1.6. Types de graphes 24
1.6.1. Graphe symétrique 24
1.6.2. Graphe complet 25
1.6.3. Graphe simple 25
1.6.4. Graphe vide 26
1.6.5. Graphe trivial 26
1.6.6. Graphe réflexif 26
1.6.7. Graphe anti-symétrique 27
1.6.8. Graphe transitif 27
1.6.9. Inverse d'un graphe 27
1.6.10. Graphe complémentaire 28
1.6.11. Multigraphe 28
1.6.12. Graphe biparti (bipartite graph) 29
1.6.13. Graphe planaire 30
1.6.14. Graphes isomorphes 30
1.7. Degré d'un sommet 32
1.8. Distribution des degrés 32
1.9. Degré moyen 33
1.10. Densité d'un graphe 34
1.10. Densité d'un graphe
1.11. Définition d'un chemin 35
1.12. Définition d'un chemin simple
1.13. Définition d'un chemin élémentaire
1.14. Définition d'un circuit 35
1.15. Chemins et circuits particuliers
1.16. Définition de fermeture transitive
1.17. Définition d'une chaîne 38
1.18. Définition d'une chaîne simple
1.19. Définition d'une chaîne élémentaire 35
1.21. Chaînes et cycles particuliers 39
1.22. Exercices et Solutions : 42
1.23. Définition d'un sous graphe
1.24. Définition d'un graphe partiel
1.25. Définition d'un sous graphe partiel
1.26. Exemple pratique 43
1.27. Définition d'un graphe connexe
1.28. Définition d'une composante simplement connexe CSC
1.29. Définition d'un graphe fortement connexe
1.30. Définition d'une composante fortement connexe CFC
1.31. Définition d’un graphe quasi-fortement connexe
1.32. Définition d'un point d'articulation 42
1.33. Définition d'un isthme : 47
1.34. Algorithme de recherche d'une composante CSC d'un sommet S 47
1.35. Algorithme de recherche d'une composante CFC d'un sommet S 48
1.36. Le plus court chemin / La distance 49
1.37. Diamètre d'un réseau et distance moyenne 49
1.38. Détection d'une Communauté 50
1.39. Composantes Géantes et composantes isolées 51
1.40. K-Cores 51
1.41. Cliques et sous graphes complets 52
1.42. Equivalence structurelle entre sommets 53
1.43. Similarité entre sommets 53
1.44. Centralité (sommet central 54
1.45. Prestige (sommet prestigieux) 54
1.46. Degré de centralité 55
1.47. Centralisation d’un graphe 56
1.48. Centralité entre deux sommets (Betweenness Centrality) 58
1.49. Centralité de proximité 59
1.50. Centralité de proximité normalisée
1.51. Prestige 60
1.52. Domaine d'entrée (d'influence) 61
1.53. Rang du Prestige 61
Exercices 62
Correction des exercices 69
Chapitre 2 : Méthodes de représentation des graphes 83
2.1. Classes de Méthodes 84
2.1.1. Méthodes statiques 84
2.1.1.1. Matrice d'adjacence (sommets – sommets)
2.1.1.2. Matrice d'incidence (sommets – arcs
2.1.1.3. Liste des arcs triés (selon l'extrémité initiale)
2.1.1.4. Liste des arcs non triés (pris arbitrairement)
2.1.1.5. Liste des successeurs 87
2.1.1.6. Liste des prédécesseurs 87
2.1.1.7. Liste linéaire des successeurs
2.1.1.8. Liste linéaire des successeurs avec fin de liste (EOL)
2.1.1.9. Liste linéaire des successeurs avec début de liste (BOL)
2.1.2. Méthodes dynamiques 88
2.1.2.1. Liste dynamique des sommets
2.1.2.2. Liste dynamique des arcs
2.1.3. Méthodes pour représenter des graphes particuliers
2.1.3.1. Graphe non valué/Simple (non orienté)
2.1.3.2. Graphe valué/Simple (non orienté) 84
2.1.3.3. Multigraphe (non orienté) 91
2.1.4. Matrice d’adjacence et matrice de longueur de chemins 91
2.1.5. Matrice de distance d’un graphe 93
2.1.6. Graphes d'intervalles 94
2.1.7. Graphes Triangulés 95
2.1.8. Graphes planaires 96
2.2. Graphes eulériens et graphes hamiltoniens 96
2.3. Chemins et circuits eulériens 97
2.4. Cycles hamiltoniens 98
Exercices 99
Correction des exercices 104
Chapitre 3 : Arbres et Arborescences 115
3.1. Définition d’un arbre, Co-arbre
3.2. Définition d’une forêt : 116
3.3. Quelques propriétés d’un arbre 118
3.4. Définition d’une arborescence 118
3.5. Propriétés d’une arborescence 119
3.6. Représentation d’une arborescence 122
3.7. Parcours d’une arborescence : 123
3.8. Cycles et vecteurs associés 123
3.9. Cycles indépendants : 124
3.10. Définition d’une base de cycles : 124
3.11. Définition d’une base de cocycles 125
3.12. Algorithme de recherche d’une base de cycles d’un graphe connexe 126
3.13. Recherche d’une base de cocycles 128
3.14. Algorithme de recherche d’un arbre maximal 128
3.15. Algorithme de recherche d’un arbre maximal de poids minimum (Kruskal 1) 129
3.16. Algorithme de Kruskal 2 131
3.17. Algorithme de Prim 132
Exercices 133
Correction des exercices 136
Chapitre 4 : Problème de plus court chemin 147
4.1. Description du problème 148
4.2. Quelques propriétés de plus court chemin 149
4.3. Algorithmes de recherche de plus court chemin 151
4.3.1. Algorithme de Ford 151
4.3.2. Algorithme de Dijkstra 154
4.3.3. Algorithme de Bellman 157
Exercices 159
Correction des exercices 162
Chapitre 5 : Réseaux de transport et problèmes de flots 173
5.1. Définition d’un réseau 174
5.2. Définition d’un nœud 174
5.3. Définition d’un réseau de transport 174
5.4. Définition d’un flot dans un graphe 174
5.5. Recherche d’un flot maximal (problème classique)
5.6. Définition d’un arc saturé
5.7. Définition d’un flot complet
5.8. Algorithme de recherche d’un flot complet
5.9. Amélioration ou maximisation du flot (Algorithme de Ford-Fulkerson)
5.9.1. Méthode de marquage
5.9.2. Méthode de graphe d’écart (graphe résiduel)
5.9.2.1. Définition d’un graphe d’écart ou réseau résiduel
5.9.2.2. Recherche de flot maximal en utilisant un graphe d’écart Exercices Correction des exercices Chapitre
6 : Problème de coloriage dans les graphes
6.1. Avant-propos
6.2. Définition
6.3. Coloriage des sommets
6.4. Algorithme de coloriage (Welsh et Pawell)
6.5. Algorithme de Welsh et Powell (une variante basée sur la matrice d'adjacence)
6.6. Exemples de coloriage
6.7. Coloriage des arêtes
6.8. Coloriage des faces Exercices Correction des exercices Chapitre
7: Couplages et affectations dans les graphes
7.1. Définition d'un couplage
7.2. Intérêt du couplage
7.3. Propriétés d'un couplage
7.4. Définition d'une chaîne alternée
7.5. Transfert de couplage le long d'une chaîne alternée
7.6. Définition d'un couplage maximum
7.7. Algorithme de construction d'un couplage maximum
7.8. Une méthode simple pour trouver une chaîne alternée pour un couplage
7.9. Algorithme de construction d'un arbre alterné Talt
7.10. Problème d'affectation 267
7.10.1. Exposition du problème 267
7.10.2. Algorithme Hongrois 268
Exercices 274
Correction des exercices 279
Chapitre 8 : Problèmes d’ordonnancement 297
8.1. Présentation du problème 298
8.2. Types de contraintes dans un problème d’ordonnancement 300
8.3. Dates et Marges 301
8.4. Taches critiques, taches non critiques et chemin critique 302
8.5. Modélisation d’un problème d’ordonnancement par un graphe 302
8.5.1. Un graphe M.P.M 302
8.5.2. Un graphe P.E.R.T : 304
8.6. Méthodes de résolution d’un problème d’ordonnancement 304
8.6.1. La méthode M.P.M (Méthode des Potentiels Metra) 304
8.6.1.1. Calcul des dates 305
8.6.1.2. Taches critiques et chemin critique 306
8.6.1.3. Calcul des marges 306
8.6.1.4. Passage d’un graphe MPM vers un tableau 306
8.6.1.5. Démarche de construction du graphe M.P.M 311
8.6.2. La méthode P.E.R.T (Project Evaluation and Review Technique) 314
8.6.2.1. Calcul des dates 318
8.6.2.2. Détermination du chemin critique 318
8.6.2.3. Calcul des marges MT, ML, MC 318
8.7. Comparaison entre les méthodes M.P.M et P.E.R.T 318
8.8. Graphe de Gantt 319
8.8.1. Principe de construction du graphe (diagramme) de Gantt 319
8.8.2. Avantages d'utiliser des diagrammes de Gantt 320
8.8.3. Inconvénients des diagrammes de Gantt 321
Exercices 322
Correction des exercices
Chapitre 9 : Hypergraphes et Matroïdes
9.1. Hypergraphes : extensions des graphes
9.2. Définition d’un hypergraphe
9.3. Domaines d’utilisation d’un hypergraphe
9.4. Représentation d’un hypergraphe
9.5. Définition d’un hypergraphe simple
9.6. Définition du dual d’un hypergraphe
9.7. Propriétés d’un hypergraphe
9.8. Définition d’un hypergraphe partiel
9.9. Définition d’un Sous hypergraphe8
9.10. Définition d’un Sous hypergraphe partiel
9.11. Définition de degré dans un hypergraphe
9.12. Définition des familles croisées
9.13. Propriété d’une arête colorée
9.14. Graphes représentatifs d’un hypergraphe
9.15. Définition d’un hypergraphe uniforme
9.16. Définition d’un hypergraphe complet
9.17. Définition de k-section
9.18. Les matroïdes
9.19. Définition d’une famille héréditaire
9.20. Définition d’un système héréditaire
9.21. Définition d’un matroïde
9.22. Quelques propriétés d’un matroïde
9.23. Matroïde transversal
9.24. Matroïde graphique
9.25. Matroïde uniforme
9.26. Matroïde de cycle et matroïde graphique
9.27. Matroïde de partition
9.28. Dual d’un matroïde
9.29. Définition de rang
9.30. Définition de sous-modularité
9.31. Définition de restriction et contractions
9.32. Intersection des matroïdes
Exercices 364
Correction des exercices 367
Annexes 373
Références bibliographiques
Livres dans la même catégorie
Avis des lecteurs
Aucun avis pour le moment.