Théorie des graphes

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.

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Téléchargement

Vous pouvez accèder au cours au format PDFThéorie des graphes (en cas de problème : Lien mirroirThéorie des graphes).

II. Sommaire

  1. Exemples de problèmes
  2. Définitions générales
  3. Chemins et arbres
  4. Représentation des graphes
  5. Algorithmes de parcours
  6. Parcours en largeur
  7. Parcours en profondeur
  8. Le problème de l'arbre couvrant minimal
  9. Le problème du plus court chemin
  10. Le problème du flot maximal
  11. Couplage

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

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