Algorithmique de graphes

Après une brève introduction des graphes, ce cours présente des problèmes sur les graphes admettant une solution algorithmique efficace. L'étude de ces solutions sera l'occasion d'exhiber des propriétés classiques en Théorie des Graphes.

Introduction

Exemples de problèmes
Définitions générales
Chemins et arbres


Problèmes de parcours

Une solution gloutonne pour l'arbre couvrant minimal
Parcours en largeur
Le problème du plus court chemin
Parcours en profondeur


Autres problèmes

Le problème du flot maximal
Le problème du couplage maximum

Modules [[m:IF101]] et [[m:IF102]]

I. Introduction - Exemples de problèmes - Définitions générales - Chemins et arbres II. Problèmes de parcours - Une solution gloutonne pour l'arbre couvrant minimal - Parcours en largeur - Le problème du plus court chemin - Parcours en profondeur III. Autres problèmes - Le problème du flot maximal - Le problème du couplage maximum

Des notes de cours imprimés et en ligne.
Introduction à l'algorithmique, T. Cormen et al., Dunod~(1994).