Généralités sur les graphes⚓︎
Intentions⚓︎
Introduction
Les graphes ont été introduits pour la première fois en 1735 par le mathématicien suisse Leonhard Euler (Bâle, 1707 – Saint-Pétersbourg, 1783) afin de répondre au problème des sept ponts de Königsberg.
A partir de cette date, une théorie des graphes a été progressivement construite afin de répondre à des problèmes de plus en plus complexes. Plusieurs grands noms des mathématiques y sont associés ; par exemple : Alexandre-Théophile Vandermonde, Pierre Rémond de Montmort, Abraham de Moivre, Thomas Kirkman, William Rowan Hamilton, Julius Petersen, etc.
Au milieu du XIXème siècle, le mathématicien britannique Arthur Cayley (Richmond, 1821 – Cambridge, 1895) s’intéressa à une classe particulière des graphes : les arbres. Celle-ci fut abondamment étudiée ensuite à partir de 1937 grâce aux travaux du mathématicien hongrois George Polya (Budapest, 1887 – Palo Alto, 1985).
Aujourd’hui, les graphes font partie des objets fondamentaux en algorithmique, en informatique et en mathématiques. En effet, leur structure relationnelle intrinsèque leur permettent de modéliser naturellement de très nombreux problèmes dans des domaines variés comme, par exemple :
- les réseaux de communications ;
- la gestion de stocks et/ou de production ;
- la logistique ;
- la bio-informatique ;
- le web ;
- le routage sur internet ;
- etc.
Déroulé
On propose le déroulé suivant :
- un point de cours interactif introduisant les notions de base sur les graphes ;
- des exercices d'entraînement pour manipuler ces différentes notions.
Cours⚓︎
Cours
Exercices
Ressources⚓︎
Il n'y a pas de ressources associées à ce chapitre.