INFO526 : Graphes et algorithmes

Cours du semestre 5 de la licence STIC INFO.

• Responsable pour 2012--2013: Xavier Provençal.
• Xavier Provençal (C/TD/TP), Pierre-Étienne Meunier (TP).

TD et TP

TD1 : Première feuille de TD

TD2 : Deuxième feuille de TD

TD3 : Troisième feuille de TD

TP : Énoncé des TP

Compléments de cours / TD / TP

Algorithme du parcours en largeur

Algorithme du parcours en profondeur

Quelques algorithmes de minimisation Prim, Dijkstra, Floyd-Warshall.

Références

La partie « Algorithmes sur les graphes » du livre « Introduction à l'algorithmique » de Cormen, Leiserson et Rivest est un bon complément. Il contient des exemples, applications et preuves de certaines propriétés des algorithmes étudiés en cours...

Déroulement (2012-2013)

• (Cours 1): 12 septembre. Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.
• (Cours 2): 18 septembre. Lemme des poignées de mains, représentations de graphes (listes VS matrice), composantes connexes.
• (TD 1): 19 septembre. Représentation de graphes, propriétés élémentaires de graphes, modélisation par des graphes.
• (Cours 3): 25 septembre. Arbres, forêts et arbres couvrants. Parcours en largeur.
• (TD 2): 26 septembre. Parcours en largeur : connexité, graphes bipartis, détection de cycles.
• (Cours 4): 2 octobre. Parcours en profondeur, graphes valués, arbres couvrants de poids minimal (I).
• (TD 3): 9 octobre. Parcours en profonder : détection de cycles, tri topologique. Algorithmes de Kruskal (I).
• (Cours 5): 16 octobre. Algorithmes de Prim, Dijkstra et Floyd-Warshall.
• (TP 1): 24 octobre. Familiarisation avec Sagemath et sa bibliothèque de graphes. Conversion de représentations, graphe de dépendances.