Page associée au cours d'Algorithmique sur les graphes
Programme du cours
Le problème fondateur : les sept ponts de Könisberg

Graphes : définitions et exemples

Représentations des graphes.

Problèmes de cheminement dans un graphe orienté :

[-] Accessibilité : l'algorithme de Roy-Warshall
[-] Plus courts chemins et plus courtes distance : l'algorithme de Floyd-Warshall et de Bellman-Ford
[-] Plus courts chemins depuis un sommet : l'algorithme de Dijkstra

Graphes sans cycles : arbres et arborescences

Gestion des partitions d'un ensemble : recherche des composantes connexes par la méthode
de l'union et de la recherche

Arbres couvrants minimum : les algorithmes de Kruskal et Prim

Parcours de graphes orientés :
[-] L'algorithme d'exploration des graphes
[-] Les différentes stratégies d'exploration
[-] Implantation du parcours en profondeur dans la version avec retour en arrière
[-] Propriétés du parcours en profondeur
Les applications du parcours en profondeur

Flux et réseaux de transport :
[-] La méthode de Ford-Fulferson
[-] L'algorithme de Ford-Fulkerson
[-] Couplage maximal dans un graphe biparti

Introduction au langage de programmation Python :
Programmation impérative et orientée objets de quelques algorithmes sur les graphes.