Download Graphes

2
CONTENTS
7 Quelques algorithmes dans les graphes
7.1 Problèmes de cheminement. Plus court chemin . . . . . . . .
7.2 Algorithme de Ford-Bellman . . . . . . . . . . . . . . . . . .
7.2.1 Principe de l’algorithme . . . . . . . . . . . . . . . . .
7.2.2 Complexité . . . . . . . . . . . . . . . . . . . . . . . .
7.2.3 Enoncé formel de l’algorithme . . . . . . . . . . . . . .
7.3 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . .
7.3.1 Principe de l’algorithme . . . . . . . . . . . . . . . . .
7.3.2 Enoncé formel de l’algorithme . . . . . . . . . . . . . .
7.4 Chemin de capacité maximale . . . . . . . . . . . . . . . . . .
7.4.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.2 Remarques . . . . . . . . . . . . . . . . . . . . . . . .
7.4.3 Enoncé formel de l’algorithme . . . . . . . . . . . . . .
7.5 Plus court chemin entre toutes les paires de sommets : Floyd
7.5.1 Principe de l’algorithme . . . . . . . . . . . . . . . . .
7.5.2 Enoncé formel de l’algorithme . . . . . . . . . . . . . .
7.6 Arbre de poids minimal – Test de connexité . . . . . . . . . .
7.6.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . .
7.6.2 Principe de l’algorithme de Prim . . . . . . . . . . . .
7.6.3 Enoncé formel de l’algorithme de Prim . . . . . . . . .
7.7 Problème de flot . . . . . . . . . . . . . . . . . . . . . . . . .
7.7.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . .
7.7.2 Problème du flot maximum . . . . . . . . . . . . . . .
7.7.3 Graphe d’écart et algorithme de Ford-Fulkerson . . . .
7.7.4 Algorithme de Ford-Fulkerson . . . . . . . . . . . . . .
7.7.5 Enoncé formel de l’algorithme . . . . . . . . . . . . . .
7.8 K-coloration de graphe . . . . . . . . . . . . . . . . . . . . . .
7.8.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . .
7.8.2 Principe de l’algorithme par énumération . . . . . . .
7.8.3 Ennoncé formel de l’algorithme . . . . . . . . . . . . .
7.8.4 Une application : Emploi du temps . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
31
31
31
32
32
33
33
33
34
34
34
35
35
35
36
37
37
37
37
38
38
38
39
39
40
40
40
41
42
43
8 Ordonnancement
8.1 Introduction . . . . . . . . . . . . . . . . . . . . .
8.1.1 Les contraintes . . . . . . . . . . . . . . .
8.1.2 Les tâches . . . . . . . . . . . . . . . . . .
8.1.3 Les ressources . . . . . . . . . . . . . . . .
8.1.4 Les fonctions économiques . . . . . . . . .
8.1.5 Notations . . . . . . . . . . . . . . . . . .
8.2 Représentation des problèmes d’ordonnancement
8.2.1 Le diagramme de Gantt . . . . . . . . . .
8.2.2 Les graphes . . . . . . . . . . . . . . . . .
8.3 Méthode du chemin critique . . . . . . . . . . . .
8.3.1 Description de la méthode . . . . . . . . .
8.4 Méthodes sérielles . . . . . . . . . . . . . . . . .
8.4.1 Algorithme de liste. . . . . . . . . . . . .
8.4.2 Exemple. . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
45
45
45
46
46
46
47
47
47
48
53
53
55
56
56
A Le Langage algorithmique C’,
Manuel d’utilisation.
A.1 Les structures de contrôle. . .
A.2 Les fonctions et procédures. .
A.3 Types et opérateurs. . . . . .
A.3.1 Les types primitifs. . .
A.3.2 Les types abstraits. . .
A.3.3 Les tableaux. . . . . .
A.3.4 Les opérateurs. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
57
57
58
58
58
58
59
59
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.