Chapitre 6 - Partie 1 : Repère historique - Euler et les sept ponts de Königsberg

La théorie des graphes naît d'un casse-tête : peut-on traverser chacun des sept ponts de la ville de Königsberg une seule fois ?

Chronologie

Date	Événement	Personnalité
1735-1736	Les sept ponts de Königsberg : Euler montre qu'un tel parcours est impossible en modélisant la ville par un graphe (publication en 1741). C'est le point de départ de la théorie des graphes.	Leonhard Euler
vers 1882	Parcours d'un labyrinthe par exploration, ancêtre du parcours en profondeur.	Charles Pierre Trémaux
1959	Plus court chemin : algorithme de Dijkstra, et parcours en largeur pour trouver la sortie d'un labyrinthe.	Edsger Dijkstra ; Edward Moore
1998	PageRank : le Web est vu comme un graphe de pages reliées par des liens, ce qui permet de classer les résultats d'un moteur de recherche.	Sergey Brin et Larry Page

Modéliser un problème par un graphe permet de le résoudre avec des algorithmes généraux.
Réseaux routiers, réseaux sociaux, Internet ou labyrinthes sont tous des graphes.