| Cours | Date | Sujet | Matériel supplémentaire |
| 1 |
|
Introduction
premières définitions
les graphes sont partout
représentation des graphes
parcours en profondeur recursif
|
notes de cours
un parcours récursif en profondeur animé (sous Acrobat Reader) du labyrinthe.
Les sommets déjà vus sont noirs ou bleus. Les sommets bleus représentent
des sommets i dont l'appel récursif VISITE(i) n'est pas encore terminé.
Pour les sommets noirs, la date de fin a été déjà choisie.
|
| 2 |
|
définitions : arbres et forêts
calcul du nombre de composantes connexes d’un graphe non-orienté
déterminer si un graphe est bipartie, 2-colorabilité
parcours en profondeur itératif, piles
Parcours en largeur, files
|
notes de cours
un parcours itératif en profondeur animé (sous Acrobat Reader).
un parcours en largeur animé (sous Acrobat Reader).
|
| 3 |
|
calcul des plus courts chemin d’un graphe par un parcours en largeur
classification des arcs par un parcours en profondeur
detection de cycle
algorithmes de tri topologique
|
notes de cours
|
| 4 |
|
fermeture transitive
calcul de composantes fortement connexes (Kosaraju)
|
notes de cours
|
| 5 |
|
algorithme de Warshall
algorithme de Kosaraju
algorithme de Tarjan
|
notes de cours
|
| 6 |
|
graphes pondérés
arbres couvrants minimaux (ACM)
algorithme glouton abstrait pour les ACM
algorithme de Prim
|
notes de cours
|
| 7 |
|
arbres couvrants minimaux (ACM)
algorithme de Kruskal
Union-find
|
notes de cours
|
| 8 |
|
plus courts chemins
algorithme ordinal
algorithme de Dijkstra
|
notes de cours
|
| 9 |
|
compléments pour l'implémentation des algorithmes précédents avec des files de priorités
algorithme de Bellman-Ford
|
notes de cours
|
| 10 |
|
Problèmes d’ordonnancement
|
notes de cours
|
| 11 |
|
Réseaux de flot
|
notes de cours
|