Ce cours traite principalement de la théorie des graphes et des algorithmes les plus connus qui leur sont associés. Une premier partie introductive expliquera d'où est venu l'idée de créer et de formaliser la notion de graphe (coloration de carte, les ponts de Königsberg, planification de travaux, parcours). Ensuite une partie formalisera la notion de graphe, de chemin et d'arbre. La suite expliquera les algorithmes : de parcours en largeur, de parcours en profondeur, et les algorithmes résolvant le problème de l'arbre couvrant minimal, le problème du plus court chemin, le problème du flot maximal et enfin, le problème du couplage maximum.
Article lu fois.
Publié le 28 mars 2007 - Mis à jour le 28 mars 2007
Vous pouvez accèder au cours au format PDFThéorie des graphes (en cas de problème : Lien mirroirThéorie des graphes).
Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants :
Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2007 Denis Lapoire. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.
