Théorie des graphes

Ce cours est enseigné aux étudiants de 4ème année "Génie Informatique" de l'Institut National des Sciences Appliquées de Toulouse (INSAT).
Il constitue une introduction à la théorie des graphes.

Le contenu est composé de quatre chapitres. Le premier « Eléments de théorie des graphes » présente les concepts généraux. Le deuxième « Le problème du plus court chemin » aborde certainement l'un des plus fameux sujets de la théorie des graphes, en présentant les principaux algorithmes de recherche de chemins de longueur minimale dans un graphe. Le troisième, « Chemins, parcours hamiltoniens, arbres », propose des méthodes générales concernant l'énumération et l'existence de chemins, de circuits hamiltoniens et d'arbres à coût minimum. Le quatrième « Flots dans les réseaux » parle plus particulièrement des réseaux de transport et introduit les méthodes fondamentales de recherche d'un flot maximum.

La théorie des graphes est née en 1736 quand Euler démontra qu'il était impossible de traverser chacun des sept ponts de la ville de Königsberg une fois exactement et de revenir au point de départ.
La théorie des graphes constitue un domaine des mathématiques qui, historiquement, s'est aussi développé au sein de disciplines diverses telles que la chimie (modélisation de structures), la biologie (génome), les sciences sociales (modélisation des relations) ou en vue d'applications industrielles (problème du voyageur de commerce).
Un graphe permet de représenter simplement la structure, les connexions, les cheminements possibles d'un ensemble complexe comprenant un grand nombre de situations, en exprimant les relations, les dépendances entre ses éléments (eg, réseau de communication, réseaux ferroviaire ou routier, arbre généalogique, diagramme de succession de tâches en gestion de projet, etc).
En plus de son existence purement mathématique, le graphe est aussi une structure de données puissante pour l'informatique.

Suite à vos demandes, également une version PDF avec une page par feuille GraphesPDF-1page.pdf (866 k).