INFO631 : Graphes et algorithmes

Cours du semestre 6 de la licence STIC INFO.

• Responsable pour 2014--2015: Xavier Provençal.
• Xavier Provençal (CM/TD/TP).

Présentation d'introduction présentée au premier cours : Présentation

TD

TD1 : Première feuille de TD

TD2 : Deuxième feuille de TD

TD3 : Troisième feuille de TD

TD4 : Quatrième feuille de TD

TD5 : Cinquième feuille de TD

TD6 : Sixième feuille de TD

TP

Lien vers la page 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.

Ouvrage de référence

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...

Logiciel utilisé lors des TP

http://sagemath.org

Documents remis en classe

Parcours de graphes, en largeur et en profondeur.

Algorithmes de minimisation ( Prim, Dijkstra, Floyd-Warshall ).

Déroulement (2014-2015)

• (Cours 1): Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.
• (Cours 2): Chemin, chemin simple, cycle, composante (fortement) connexe. Arbre. Représentation de graphes ( matrice vs listes ).
• (TD 1): Représentation de graphes, propriétés élmentaires de graphes, modélisation par des graphes.
• (Cours 3): Forêt couvrante, parcours de graphes, parcours en largeur, parcours en profondeur.
• (TD 2): Parcours en largeur : connexité, graphes bipartis, détection de cycles.
• (Cours 4): Graphes valués, arbre courvrant de poids minimum et algorithme de Kruskal.
• (TD 3): Parcours en profondeur : tri topologique, implémentation sans récursivité. Algorithme pour le calcul d'un ACM : Prim vs Kruskal.
• (Cours 5): Calcul des chemins de longueur minimale. Algorithme de calcul de chemins de longueur minimale : Dijkstra et Floyd-Warshall.
• (TD 4): Chemins de longueur minimales.
• (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.
• (TD 5): Réseaux de tarnsport et flot maximal.

Déroulement (2013-2014)

• (Cours 1): Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.
• (Cours 2): Chemin, chemin simple, cycle, composante (fortement) connexe. Arbre et forêt. Représentation de graphes ( matrice vs listes ).
• (TD 1): Représentation de graphes, propriétés élmentaires de graphes, modélisation par des graphes.
• (Cours 3): Représentation de graphes (suite et fin). Parcours de graphes, parcours en largeur, parcours en profondeur.
• (TD 2): Parcours en largeur : connexité, graphes bipartis, détection de cycles.
• (Cours 4): Graphes valués, arbre courvrant de poids minimum et algorithme de Prim.
• (TD 3): Parcours en profondeur : tri topologique, implémentation sans récursivité. Algorithme pour le calcul d'un ACM : Prim vs Kruskal.
• (Cours 5): Calcul des chemins de longueur minimale. Algorithme de calcul de chemins de longueur minimale : Dijkstra et Floyd-Warshall.
• (TD 4): Chemins de longueur minimales.
• (Cours 6): Réseaux de transport et calcul du flot maximal. Algorithme de Ford-Fulkerson.
• (TD 5): Réseaux de tarnsport et flot maximal.

Quelques ressources additionnelles (vidéos)

Parcourt en Profondeur (DFS) 1/2

Parcourt en Profondeur (DFS) 2/2

Parcourt en Largeur (BFS) 1/2

Parcourt en Largeur (BFS) 2/2

Arbres Couvrants Minimum (Prim)

Algorithme Ford-Fulkerson (avec capacités aux noeuds)

A* (un algorithme pour super mario); excerpt

Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 1/2

Graphes et Algorithmes/ Ford-Fulkerson (Graphe Résiduel) 2/2

Flot maximum en Réseau/ Algorithme Edmonds-Karp