Les graphes par l'exemple
F. Droesbeke/M. Hallin/Ci. Lefevre
Ellipses
Avant-Propos3
Liste des organigrammes9
Chapitre I Généralités sur les graphes11
1.1. Introduction11
1.2. Quelques définitions concernant les graphes orientés11
1.3. Exemple simple17
1.4. Quelques concepts non orientés19
1.5. Exemple simple20
1.6. Exercices proposés22
1.7. Solution des exercices proposés33
Chapitre II Quelques problèmes importants de l'étude d'un graphe orienté53
2.1. Introduction53
2.2. Quelques catégories de graphes53
2.2.1. Graphe symétrique54
2.2.2. Graphe antisymétrique54
2.2.3. Graphe transitif54
2.2.4. Graphe complet55
2.3. Fermeture transitive d'un graphe55
2.3.1. Définition55
2.3.2. Organigramme de l'algorithme d'obtention de la fermeture transitive d'un graphe56
2.4. Graphes sans circuit56
2.4.1. Propriétés d'un graphe sans circuit56
2.4.2. Organigramme de l'algorithme permettant de tester l'absence de circuit58
2.4.3. Organigramme de l'algorithme d'obtention d'un circuit59
2.4.4. Organigramme de l'algorithme d'obtention des niveaux d'un graphe sans circuit60
2.5. Noyau d'un graphe61
2.5.1. Définition et propriétés61
2.5.2. Importance du concept de noyau62
2.5.3. Organigramme de l'algorithme d'obtention d'un noyau d'un graphe sans circuit63
2.6. Exemples résolus64
2.7. Exercices proposés70
2.8. Solution des exercices proposés73
Chapitre III Les méthodes électre79
3.1. Introduction : Des atrides a la décision multicritère79
3.2. L'analyse multicritere79
3.2.1. Présentation générale79
3.2.2. Relation binaire81
3.2.3. Principales méthodes83
3.3. Electre I85
3.3.1. Indices de concordance et de discordance85
3.3.2. Relation de surclassement. Graphe de surclassement87
3.3.3. Noyau du graphe de surclassement88
3.4. Exemples résolus90
3.5. Les autres méthodes electre104
3.6. Exercices proposés104
3.7. Solution des exercices proposés110
Chapitre IV Quelques aspects de la théorie des graphes non orientés115
4.1. Introduction115
4.2. Stabilité-Transversalité116
4.3. Coloration des sommets118
4.3.1. Définitions118
4.3.2. Organigramme de l'algorithme de coloration de Welsh et Powell119
4.3.3. Bornes pour le nombre chromatique120
4.3.4. Exemples résolus121
4.4. Couplage maximum123
4.4.1. Définitions123
4.4.2. Organigramme de l'algorithme d'obtention d'un couplage maximum dans un graphe biparti124
4.4.3. Exemple résolu126
4.5. Coloration des arêtes128
4.5.1. Définitions128
4.5.2. Organigramme de l'algorithme de coloration des arêtes128
4.5.3. Exemples résolus129
4.6. Arbre partiel de poids minimum132
4.6.1. Définitions132
4.6.2. Organigramme de l'algorithme de Kruskal132
4.6.3. Exemple résolu134
4.7. Exercices proposés135
4.8. Solution des exercices proposés139
Chapitre V Chemins de longueur minimale ou maximale157
5.1. Introduction157
5.2. Formulation du problème157
5.3. Algorithmes de résolution158
5.3.1. Organigramme de l'algorithme de Ford : obtention de chemins de longueur minimale (de longueur maximale)158
5.3.2. Organigramme de l'algorithme d'identification d'un chemin de longueur minimale (de longueur maximale)159
5.3.3. Organigramme de l'algorithme de Bellman-Kalaba : obtention de chemins de longueur minimale (de longueur maximale)160
5.3.4. Organigramme de l'algorithme de Bellman-Kalaba simplifié dans le cas d'un partage en niveaux de G : obtention de longueur minimale (de longueur maximale)162
5.3.5. Organigramme de l'algorithme de Dijkstra : obtention de chemins de longueur minimale163
5.4. Exemples résolus165
5.5. Exercices proposés171
5.6. Solution des exercices proposés176
Chapitre VI Problèmes de flot, I flots de valeur maximale ou de coût minimum179
6.1. Introduction179
6.2. Flot de valeur maximale180
6.2.1. Formulation du problème180
6.2.2. Organigramme de l'algorithme de Ford et Fulkerson (première formulation)181
6.2.3. Organigramme de l'algorithme de Ford et Fulkerson (seconde formulation)185
6.2.4. Exemple résolu187
6.3. Flot de coût minimum197
6.3.1. Formulation du problème197
6.3.2. Organigramme de l'algorithme d'obtention d'un flot, de valeur Phio donnée, de coût minimum197
6.3.3. Exemple résolu199
6.4. Exercices proposés204
6.5. Solution des exercices proposés212
Chapitre VII Problèmes de flot, II problèmes de transport et d'affectation221
7.1. Introduction221
7.2. Problème de transport221
7.2.1. Formulation du problème221
7.2.2. Organigramme de l'algorithme primal-dual223
7.3. Problème d'affectation228
7.3.1. Formulation du problème228
7.3.2. Organigramme de l'algorithme de Kuhn228
7.4. Exemples résolus230
7.5. Exercices proposés238
7.6. Solution des exercices proposés248
Chapitre VIII Problèmes d'ordonancement255
8.1. Introduction255
8.2. Critère temporel256
8.2.1. Mise sous forme de graphe256
8.2.2. Résolution258
8.2.3. Organigramme de l'algorithme d'obtention d'un ordonnancement de durée minimale259
8.2.4. Tâches de durée aléatoire261
8.3. Critère de coût262
8.3.1. Formulation263
8.3.2. Organigramme d'un algorithme heuristique d'obtention d'un ordonnancement de coût minimum264
8.4. Exemples résolus266
8.5. Exercices proposés274
8.6. Solution des exercices proposés280
Bibliographie282
Index285