Algorithmique des graphes

Plan du cours

7 Jan 2022: Introduction: Notions de bases, présentations des graphes, caractérisation des arbres.
21 Jan 2022: Parcours en largeur et en profondeur. Applications: composantes connexes, calcul des distances, tris topologiques.
4 Fev 2022: Les plus courts chemins. Algorithmes de Dijkstra (structures avec des tas) et de Bellman-Ford.
18 Fev 2022: Les arbres couvrants de poids minimal. Algorithmes de Kruskal et de Prim.
11 + 25 Mars 2022: Min Coupe - Max Flot. Algorithmes de Ford-Fulkerson et Edmonds-Karps
1 Avril 2022: Marriages stables. Algorithme de Gale-Shapley et applications.

Le sujet du devoir maison. La dernière question consiste d'implémenter l'algorithme de Djikstra.

Format des fichiers de test: Un fichier de test contient une représentation en forme de liste d'adjacents d'un graphe de \(n\) sommets de 1 à \(n\). Chaque ligne indique le sommet, les sommets adjacents à ce sommet et les longueurs des arêtes correspondantes. Par exemple, dans ce fichier, dans la 1ère ligne \[1 \qquad 2,1 \quad 8,2 \] indique que:
- la ligne correspond au sommet \(1\);
- \(2,1\) indique qu'il y a une arête entre le sommet \(1\) et sommet \(2\) et la longueur de cette arête est \(1\);
- \(8,2\) indique qu'il y a une arête entre le sommet \(1\) et sommet \(8\) et la longueur de cette arête est \(2\).
Test simple: Ce fichier décrit un graphe de 8 sommets. Quelles sont les distances du sommet 1 à tous les autres sommets? (Réponse: les distances vers les sommets de 1 à 8 sont 0, 1, 2, 3, 4, 4, 3, 2).
Test: Ce fichier décrit un graphe de 200 sommets. Quelles sont les distances du sommet 1 aux sommets suivants: 7, 37, 59, 82, 99, 115, 133, 165, 188, 197 ?

Ces références (optionnelles) sont pour approfondir les connaissances du cours.

Algorithms Illuminated par Tim Roughgarden. Vous pouvez regarder certains vidéos en lien avec les sujets du cours.
Algorithm Design par Jon Kleinberg et Eva Tardos.
Algorithms par Jeff Erickson.